Определение Множество натуральных чисел

Доказательство. Пусть d= НОД(а, b), тогда по теореме 1.4 суще­ствуют такие целые числа т,n, что d = ma + nb. Поскольку, а делится на b, то сумма в правой части равенства делится на b, а значит и d делится на b. В то же время b делится на d как на наибольший общий делитель. Таким образом, числа d и b ассоциированы и равны с точностью до зна­ка. □
Лемма 1.6. Для любых целых чисел а, b, с выполняется равен­ство НОД(а + cb, b) = НОД(а, b).
Доказательство. Пусть d=НОД(а, b). Тогда а делится на d, b де­лится на d, значит, по свойству 2 делимости, и сумма а + cb делится на d, то есть d — общий делитель чисел а + cb и b.
Пусть d₁ — произвольный общий делитель чисел а + cb и b. Тогда число а = (а + cb) - cb делится на d₁, то есть d₁ — общий делитель чисел а и b. А так как делитель d наибольший, то d делится на d₁, и d— наи­больший общий делитель чисел а + cb и b. □
Теорема 1.7. Для любых a, b > 0 алгоритм Евклида останавли­вается и выдаваемое им число d является наибольшим общим делителем чисел а и b.
Доказательство. По теореме о делении с остатком для любого i ≥ 1 имеем r_i-1=q_ir_i+r_i+1, где 0≤r_i+1<r_i. Получаем монотонно убы­вающую последовательность неотрицательных целых чисел r₁> r₂> r₃>...≥0, ограниченную снизу. Такая последовательность не может быть бесконечной, следовательно, алгоритм Евклида останавли­вается.
Докажем теперь, что число d — наибольший общий делитель для чисел r₁, r₂,.... r_k, где r_k-1 делится на r_k. С учетом леммы 1.6 можем запи­сать:
НОД(а, b) =НОД(r₀, r₁) = НОД(q₁ r₁+ r₂, r₁) = НОД(r_1, r₂) = =НОД(r₂,r₃) = …=НОД(r_k-1, r_k).
А по лемме 1.5 получаем НОД(r_k-1, r_k) = r_k = d.
Алгоритм 1.2. Бинарный алгоритм Евклида .
Этот вариант алгоритма Евклида оказывается боле быстрым при реализации на компьютере, поскольку использует двоичное представление чисел a и b. Бинарный алгоритм Евклида основан на следующих свойствах наибольшего общего делителя (считаем, что 0<b≤a):

1. 
   Если оба числа a и b четные, то НОД(a,b)=2*НОД( , );
   
2. 
   Если число a нечетное, число b четное, то НОД(a,b)= НОД(a, );
   
3. 
   Если оба числа a и b нечетные, a>b, то НОД(a,b)= НОД(a-b,b);
   
4. 
   Если a=b, то НОД(a, b)=a.
   

Бинарный алгоритм Евклида:
Вход. Целые числа а, b; 0 < b ≤ а.
Выход. d=НОД(а, b).

1. 
   Положить g ←1.
   
2. 
   Пока оба числа а и b четные, выполнять a← , b← , g←2g до
   

получения хотя бы одного нечетного значения а или b.

3. 
   Положить u ←a,v← b.
   
4. 
   Пока u ≠0, выполнять следующие действия.
   

1. 
   Пока и четное, полагать и ←
   

2. 
   Пока v четное, полагать v←
   
3. 
   При u≥v положить u ← u-v. В противном случае положить
   

v ← v-u.

5. 
   Положить d←gv.
   
6. 
   Результат: d.
   
7. 
   Сложность этого алгоритма равна O(log²a).
   

Алгоритм 1.3. Расширенный алгоритм Евклида.
Вход. Целые числа а, b; 0 < b ≤ а.
Выход. d=НОД(a, b); такие целые числа х,у, что ах + by=d.

1. 
   Положить r₀ ←a, r₁ ←b , x₀ ←1, x₁ ←0, y₀ ←0, y₁ ←1, i ←1.
   
2. 
   Разделить с остатком r_i-1на r_i : r_i-1= q_ir_i+r_i+1.
   
3. 
   Если r_i+1 = 0, то положить d ← r_i, x ← x_i , y ← y_i. В противном слу­чае положить x_i+1← x_i-1-q_ix_i, y_i+1← y_i-1- q_iy_i , i ← i+1 и вернуться на шаг 2.
   
4. 
   Результат: d, х, у. □
   

Сложность этого алгоритма равна O(log²a).
Алгоритм 1.4. Расширенный бинарный алгоритм Евклида
Вход, Целые числа а, b; 0 <b≤ а.
Выход, d =НОД(а, b); такие целые числа х, у, что ах + by = d.

1. 
   Положить g ←1.
   
2. 
   Пока оба числа а и b четные, выполнять a← , b← , g←2g до получения хотя бы одного нечетного значения а или b.
   

3. 
   Положить u ←a,v← b, A ←1,B← 0, C ←0,D← 1.
   
4. 
   Пока u ≠0, выполнять следующие действия.
   

4.1. Пока u четное:

1. 
   Положить и ←
   

2. 
   Если оба числа А и В четные, то положить A← , B←
   

В противном случае положить A← , B←
4.2. Пока v четное:

4.2.1. Положить v←

4.2.2. Если оба числа С и D четные, то положить C← , D← , В противном случае положить C← , D←
4.3. При u≥v положить u ←u-v, A ←A-C, B ←B-D. В про­тивном случае положить v←v-u, С←C-A,D←D-B.

5. 
   Положить d←gv, х ← С, у ← D.
   
6. 
   Результат: d, х, у.
   

Сложность этого алгоритма равна O(log²a).

1.4. Простые числа
Определение 1.10. Пусть a — целое число. Числа 1,-1, а, -а называются тривиальными делителями числа а.
Определение 1.11. Целое число p Z\{0} называется про­стым, если оно не является делителем единицы и не имеет других дели­телей, кроме тривиальных. В противном случае число р Z\{-1,0,1} называется составным.


Свойства простых чисел:

1. 
   Если числа р и q простые и р делится на q, то р ~q.
   
2. 
   Если число р простое и число а целое, то либо а делится на р, либо НОД(a, р) = 1.
   

Доказательство. Пусть НОД(a, p)=d>1. Тогда а делится на d и р делится на d, но так как число р простое, то либо d= ±1 (что противоре­чит предположению), либо d = ±p. □

3. 
   Если число р простое и произведение аb делится на р, то либо а делится на р, либо b делится на р.
   

Доказательство. Пусть а не делится на р. Тогда по предыдущему свойству НОД(а, р) = 1. Следовательно, по свойству 2 наибольшего об­щего делителя, b делится на р. □

4. 
   Если число р простое и произведение a₁a₂...a_k делится на р, то хотя бы одно из чисел а₁, а₂, ..., а_k делится на р.
   
5. 
   Если числа р₁, р₂, .... р_k, q₁, q₂, …q_l простые и выполняется ра­венство для произведений р₁р₂…p_k ⁼ q₁q₂…q_l,то l=k и числа q₁,q₂, ...,q_l можно перенумеровать так, что р₁ ~q₁,p₂ ~ q₂, ...,p_k~q_k.
   

Теорема 1.11 (основная теорема арифметики). Вся­кое число n Z\{-l,0,l} можно представить в виде п =ε p₁p₂...p_r где ε = ±1 и p₁p₂...p_r — простые числа (не обязательно различные), r≥1. Это представление единственно с точностью до порядка сомножителей.