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


Download 1.44 Mb.
bet3/9
Sana02.06.2024
Hajmi1.44 Mb.
#1837140
TuriЗакон
1   2   3   4   5   6   7   8   9
Bog'liq
Символ Лежандра

Доказательство. Пусть 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.
Пусть d1 — произвольный общий делитель чисел а + cb и b. Тогда число а = + cb) - cb делится на d1, то есть d1 — общий делитель чисел а и b. А так как делитель d наибольший, то d делится на d1, и d— наи­больший общий делитель чисел а + cb и b. □
Теорема 1.7. Для любых a, b > 0 алгоритм Евклида останавли­вается и выдаваемое им число d является наибольшим общим делителем чисел а и b.
Доказательство. По теореме о делении с остатком для любого i 1 имеем ri-1=qiri+ri+1, где 0≤ri+1<ri. Получаем монотонно убы­вающую последовательность неотрицательных целых чисел r1> r2> r3>...≥0, ограниченную снизу. Такая последовательность не может быть бесконечной, следовательно, алгоритм Евклида останавли­вается.
Докажем теперь, что число d — наибольший общий делитель для чисел r1, r2,.... rk, где rk-1 делится на rk. С учетом леммы 1.6 можем запи­сать:
НОД(а, b) =НОД(r0, r1) = НОД(q1 r1+ r2, r1) = НОД(r1, r2) = =НОД(r2,r3) = …=НОД(rk-1, rk).
А по лемме 1.5 получаем НОД(rk-1, rk) = rk = d.
Алгоритм 1.2. Бинарный алгоритм Евклида .
Этот вариант алгоритма Евклида оказывается боле быстрым при реализации на компьютере, поскольку использует двоичное представление чисел a и b. Бинарный алгоритм Евклида основан на следующих свойствах наибольшего общего делителя (считаем, что 0<ba):

  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← , g2g до

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

  1. Положить ua,v b.

  2. Пока u0, выполнять следующие действия.

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

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

  2. При uv положить uu-v. В противном случае положить

vv-u.

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

  2. Результат: d.

  3. Сложность этого алгоритма равна O(log2a).

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

  1. Положить r0a, r1b , x0 ←1, x1 ←0, y0 ←0, y1 ←1, i ←1.

  2. Разделить с остатком ri-1на ri : ri-1= qiri+ri+1.

  3. Если ri+1 = 0, то положить d ri, x xi , y yi. В противном слу­чае положить xi+1 xi-1-qixi, yi+1 yi-1- qiyi , i i+1 и вернуться на шаг 2.

  4. Результат: d, х, у.

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

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

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

  1. Положить ua,v b, A1,B 0, C0,D 1.

  2. Пока u0, выполнять следующие действия.

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

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

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

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

4.2.1. Положить v


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

  1. Положить dgv, х С, у D.

  2. Результат: d, х, у.

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

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. □

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

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

  1. Если число р простое и произведение a1a2...ak делится на р, то хотя бы одно из чисел а1, а2, ..., аk делится на р.

  2. Если числа р1, р2, .... рk, q1, q2, …ql простые и выполняется ра­венство для произведений р1р2pk = q1q2ql,то l=k и числа q1,q2, ...,ql можно перенумеровать так, что р1 ~q1,p2 ~ q2, ...,pk~qk.

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

Download 1.44 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling