Наибольший общий делитель.

Теория делимости.

 

Открытие натуральных чисел было одним из величайших интеллектуальных достижений человечества. Что общего между тремя мамонтами, тремя звездами и тремя вздохами отвергнутого влюбленного? С точки зрения потребительских качеств ничего. Мамонт – это еда, вот она здесь у входа в пещеру, от нее зависит жизнь племени. Звезды в небе, их не потрогаешь, ночью их видно, а днем нет. Вздох вообще нечто не совсем материальное, отдельно от человека не существующее.

Очень не скоро было замечено, что общее между разными предметами и событиями то, что при их перечислении нужно загнуть одно и то же число пальцев на руке, в нашем примере три. Кстати, и до сих пор, (вспомните золотое детство), обучаясь счету, малыши загибают пальцы. С пальцами же связано и возникновение десятичной системы счисления. Кстати, если бы 400 млн. лет назад на берег из океана выползла не пятипалая двоякодышащая рыба, потомками которой мы являемся, а, например, с четырьмя лучами на плавнике, то победила бы восьмеричная система счисления.

Как бы то ни было, человечеством была освоена главная идея, лежащая в основе понятия о натуральном числе. Идея взаимно-однозначного соответствия или биекции между элементами разных множеств.

Множество натуральных чисел сейчас принято обозначать ажурной заглавной буквой N.Натуральными числами являются {1,2,3,…}. Понятие о нуле возникло гораздо позже, чем об остальных целых числах. Ноль обозначает ничто, однако 0 – вполне осязаемый символ ничем не хуже чем 1 или 5. Ноль – это нечто, а обозначает он ничто. Нечто обозначающее ничто – это уже шаг к раздвоению личности и он нормальным людям дался нелегко. Отрицательные числа (понимаемые как долг, как недостача) вошли в сознание людей гораздо проще, так же как и дроби, понимаемые как часть единого целого.

Основные понятия и теоремы.

Предмет теории чисел – целые числа и их свойства.

Множество целых чисел обозначается символом Z, символом Z+ обозначается множество целых положительных чисел, символом N– множество натуральных чисел. Латинскими малыми буквами здесь и далее будем обозначать целые числа.

Заметим, что

То есть как сумма, так и произведение целых чисел также являются целыми числами. Частное двух целых чисел не всегда является целым числом.

Если , (b≠0) , Тогда говорят, что а делится на b, или b делит а, и пишут b\a. Тогда а называем кратным числа b, а bделителем числа а.

Справедливы следующие

Теоремы:

(1) m\a, b\m b\a.

Доказательство:

m\a a=ma1;

b\m m=bm1 a=bm1a1. Обозначив b1=a1m1, получим a=bb1, причем b\a.

(2) Если в равенстве вида k+l++n=p+q++s относительно всех членов кроме одного известно, что они кратны b, то и один оставшийся член тоже кратен b.

Доказательство:

Не нарушая общности, предположим, что таким членом (относительно кратности которого числу b ничего не известно) является k.

Тогда l1, …, n1, p1, q1, …, s1: l=bl1,…, n=bn1, p=bp1, q=bq1, …, s=bs1.

Тогда k=p+q++s–l––n=bp1+bq1++bs1–bl1–bn1=b(p1+q1++s1–l1–n1)

Обозначим k1= p1+q1++s1–l1–n1. Очевидно, k1 – целое число, причем k=bk1 Тогда, по определению делимости, b\k.

Кроме того, очевидны следующие свойства:

1) a\0, 1\a, a\a.

2) a\b, b\a ab.

3) a\b, a\c a\(bx+cy).

(Доказательство св-ва 3: b=ab1, c=ac1 bx+cy=ab1x+ac1y=a(b1x+c1y))

Теорема деления (теорема о делении с остатком)

единственная пара чисел 0 ≤ r < b: a=bq+r *

Доказательство:

Возьмем q: bqa, b(q+1)>a. Такое целое q, очевидно, существует r=abq является целым положительным числом как разность двух целых чисел, первое из которых больше второго. Причем выполняется . Построением такого r доказано существование разложения (*).

Теперь докажем единственность разложения (*): предположим, что кроме построенного выше, имеется еще одно разложение числа a:

a=bq1+r1, 0≤r1<b.

Вычтем полученное равенство из равенства (*) почленно. Получим

0=b(q–q1)+(rr1). **

Поскольку b\0, b\b(qq1), то по теореме 2, b\(rr1).

С другой стороны, 0≤r<b, 0≤r1<b |r–r1|<b. Отсюда и из того, что b\(rr1), следует, что r–r1=0, и тогда r=r1. Подставляя полученное равенство в (**), получаем 0=b(q–q1).

Но по условию теоремы, b≠0 , тогда q–q1=0 q=q1.

Таким образом, оба построенных разложения числа a совпадают, а значит разложение (*) единственно.

В разложении (*) число q называются неполным частным, rостатком от деления a на b.

 

Наибольший общий делитель.

Далее будем рассматривать лишь положительные делители чисел.

Общим делителем чисел a1, a2,…,an называется число d: d\ai .

Наибольший из всех общих делителей чисел a1, a2,…,an называется их наибольшим общим делителем (НОД) и обозначается НОД(a1, a2,…,an) или (a1, a2,…,an).

Если (a1, a2,…,an)=1, то числа a1, a2,…,an называются взаимно простыми.

Если (ai,aj)=1 , ij , то числа a1, a2,…,an называются попарно простыми.

Утверждение

Если числа a1, a2,…,an – попарно простые, то они взаимно простые. (Очевидно.)

 

Теорема 1

Если b\a совокупность общих делителей a и b совпадает с совокупностью делителей b. В частности, (a,b)=b.

Доказательство:

b\a a=ba1, тогда d: d\b справедливо d\a (т.е. любой делитель b является также делителем a).

Если l\a, но l не делит b, то l не является общим делителем a и b.

То есть совокупность общих делителей a и b совпадает с совокупностью делителей b. А поскольку наибольший делитель b есть b, и b\a , то (a,b)=b.

Теорема 2

Если a=bq+c, то совокупность общих делителей a и b совпадает с совокупностью общих делителей b и c.

В частности, (a,b)=(b,c)

Доказательство:

Пусть m\a, m\b m\c (в силу a=bq+c и теоремы 2 п.1), а значит m – общий делитель b и c.

Пусть l\b, l\c l\a (в силу a=bq+c и теоремы 2 п.1), а значит l - общий делитель a и b.

Получили совпадение совокупности общих делителей a и b и общих делителей b и c.

Пусть теперь d=(a,b) d\a, d\b, а значит, по доказанному выше, d\c. В силу совпадения совокупностей общих делителей и того, что d – наименьший изо всех делителей a и b, не может существовать d1: d1>d, d1\b, d1\c. Поэтому d=(b,c) (a,b)= (b,c).

Алгоритм Евклида (отыскания НОД 2-х чисел)

Пусть a>b. Тогда в силу теоремы делимости находим ряд равенств:

a=bq1+r1, 0<r1<b

b=r1q2+r2, 0<r2<r1

r1=r2q3+r3, 0<r3<r2

...…………………

rn-2=rn-1qn+rn, 0<rn<rn-1

rn1=rnqn+1.

Получение последнего равенства (то есть равенства с разложением без остатка) неизбежно, т.к. ряд b, r1, r2, …. – ряд убывающих целых чисел, который не может содержать более b положительных чисел, а значит рано или поздно в этом ряду возникнет «0».

Видим, что общие делители a и b, b и r1, r1 и r2,..., rn–1 и rn совпадают с делителями числа rn (a,b)=(b,r1)=(r1,r2)=…=(rn-1,rn)= rn.

Таким образом, (a,b)=rn.

Вышеизложенная идея нахождения НОД может быть реализована в виде алгоритма. Ниже приведены несколько вариантов реализации алгоритма Евклида.

Реализация алгоритма Евклида (вариант алгоритма с вычитанием)

Вход: a, b>0.

1.Если a>b Шаг 3

если a<b Шаг 2

если a=b Шаг 5 (выход)

2.Меняем местами a и b.

3.a:=ab

4.Возвращаемся на Шаг 1.

5. Выход: a – НОД

 

Ниже приведен пример использования этой реализации алгоритма.

Пример

a=603, b=108

Преобразования алгоритма записаны в таблицу, верхняя строка которой содержит значение переменной a, нижняя – содержимое переменной b. Каждый столбец таблице соответствует состоянию процесса на отдельном шаге.

a
b

 

Ответ: НОД(603,108)=9.

 

Реализация алгоритма Евклида (вариант алгоритма с делением с остатком)


Вход: a, b >0.

1. Находим разложение a=bq+r, 0≤r<b

2. если r=0 Шаг 5 (выход)

3. a:=b; b:=r.

4. Возвращаемся на Шаг 1

5. Выход: b – НОД.

 

Пример

a=603, b=108

a
b

603=5·108+63

108=1·63+45

63=1∙45+27

45=1∙27+18

27=1∙18+9

18=2∙9+0

 

Ответ: НОД(603,108)=9.

 

Бинарный алгоритм Евклида

Этот вариант создан специально для реализации на ЭВМ. В нем учитывается, что операция деления на число 2 или на любую степень двойки является весьма быстрой и простой операцией (в двоичной системе счисления операция деления на 2 есть всего лишь битовый сдвиг вправо).

Учтем, что (2ka,2sb)=2min(k,s)(a,b).

Алгоритм:

Вход: a, b>0.

1. Представим a и b в виде: ; , где a1, b1 – нечетные числа.

k:=min(k1,k2).

2. Если a1>b1 Шаг 4

a1< b1 Шаг 3

a1= b1 Шаг 6

3. Меняем местами a1 и b1.

4. c:=a1b1=2sc1 (c1 - нечетное число)

(Заметим, что с обязательно будет четным, а значит )

5. a1:= b1 , b1:=c1 . Возвращаемся на Шаг 1.

6. Выход: (a,b)=2ka1 .

 

Пример

a=603, b=108

 

a1
b1
c1

1. a1=603, k1=0; b=108=4∙27=22∙27 k2=2, b1=27, k=0

2. a1=603> b1=27 Ш4

4. c=603-27=56=64∙9, c1=9

5. a1=27; b1=9 Ш1

1. a1=27; b1=9

2. a1> b1 Ш4

4. c=a1b1=18=2∙9, c1=9

5. a1=9, b1=9

1. a1=9, b1=9, k=0

2. a1= b1 Ш6

6. (a,b) = 2º∙9=9

 

Для НОД справедливы следующие свойства:

 

1) (am,bm)=m(a,b)

Доказательство:

Доказательство строится, умножая почленно соотношения алгоритма Евклида на m.

2) d – общий делитель чисел a и b

(в частности, ).

Доказательство:

Учитывая, что и – целые числа, из свойства НОД №1 получаем соотношение , что и требовалось.

3) (a,b)=1 (ac,b)=(c,b)

Доказательство:

a, b, c выполняется (ac,b)\ac, (ac,b)\b (ac,b)\bc (ac,b)\(ac,bc).

По условию теоремы, в силу взаимной простоты a и b (ac,bc)=c, то есть получили (ac,b)\с.

Но (ac,b)\b (ac,b)\(c,b).

С другой стороны, (c,b)\ac, (c,b)\b. (c,b)\(ac,b).

Таким образом, числа (ac,b) и (c,b). взаимно делят друг друга (ac,b)=(c,b).

4) (a,b)=1, b\ac b\c.

Доказательство:

Из теоремы №1 о НОД в силу b\ac, (ac,b)=b.

из свойства НОД № 3 b=(c,b)и тогда из теоремы №1 о НОД b\c.

5) Если (ai, bj)=1 для , ( , )=1.

Доказательство:

имеем ( , ) = ( , ) = ( , ) = … = .

Аналогично, используя полученное соотношение,

( , ) = ( , ) = … = ( , ) = 1.








Дата добавления: 2015-11-28; просмотров: 1961;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.062 сек.