ГЛАВА 1. Основы теории чисел.
§1. Теория делимости.
Открытие натуральных чисел было одним из величайших интеллектуальных достижений человечества. Что общего между тремя мамонтами, тремя звездами и тремя вздохами отвергнутого влюбленного? С точки зрения потребительских качеств ничего. Мамонт – это еда, вот она здесь у входа в пещеру, от нее зависит жизнь племени. Звезды в небе, их не потрогаешь, ночью их видно, а днем нет. Вздох вообще нечто не совсем материальное, отдельно от человека не существующее.
Очень не скоро было замечено, что общее между разными предметами и событиями то, что при их перечислении нужно загнуть одно и то же число пальцев на руке, в нашем примере три. Кстати, и до сих пор, (вспомните золотое детство), обучаясь счету, малыши загибают пальцы. С пальцами же связано и возникновение десятичной системы счисления. Кстати, если бы 400 млн. лет назад на берег из океана выползла не пятипалая двоякодышащая рыба, потомками которой мы являемся, а, например, с четырьмя лучами на плавнике, то победила бы восьмеричная система счисления.
Как бы то ни было, человечеством была освоена главная идея, лежащая в основе понятия о натуральном числе. Идея взаимно-однозначного соответствия или биекции между элементами разных множеств.
Множество натуральных чисел сейчас принято обозначать ажурной заглавной буквой N. Натуральными числами являются {1,2,3,…}. Понятие о нуле возникло гораздо позже, чем об остальных целых числах. Ноль обозначает ничто, однако 0 – вполне осязаемый символ ничем не хуже чем 1 или 5. Ноль – это нечто, а обозначает он ничто. Нечто обозначающее ничто – это уже шаг к раздвоению личности и он нормальным людям дался нелегко. Отрицательные числа (понимаемые как долг, как недостача) вошли в сознание людей гораздо проще, так же как и дроби, понимаемые как часть единого целого.
1.1. Основные понятия и теоремы.
Предмет теории чисел – целые числа и их свойства.
Множество целых чисел обозначается символом 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 a=±b.
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: bq≤a, b(q+1)>a. Такое целое q, очевидно, существует r=a–bq является целым положительным числом как разность двух целых чисел, первое из которых больше второго. Причем выполняется . Построением такого r доказано существование разложения (*).
Теперь докажем единственность разложения (*): предположим, что кроме построенного выше, имеется еще одно разложение числа a:
a=bq1+r1, 0≤r1<b.
Вычтем полученное равенство из равенства (*) почленно. Получим
0=b(q–q1)+(r–r1). **
Поскольку b\0, b\b(q–q1), то по теореме 2, b\(r–r1).
С другой стороны, 0≤r<b, 0≤r1<b |r–r1|<b. Отсюда и из того, что b\(r–r1), следует, что r–r1=0, и тогда r=r1. Подставляя полученное равенство в (**), получаем 0=b(q–q1).
Но по условию теоремы, b≠0 , тогда q–q1=0 q=q1.
Таким образом, оба построенных разложения числа a совпадают, а значит разложение (*) единственно.
В разложении (*) число q называются неполным частным, r – остатком от деления a на b.
1.2. Наибольший общий делитель.
Далее будем рассматривать лишь положительные делители чисел.
Общим делителем чисел 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 , i≠j , то числа 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
rn–1=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.
Если a>b Шаг 3
если a<b Шаг 2
если a=b Шаг 5 (выход)
Меняем местами a и b.
a:=a–b
Возвращаемся на Шаг 1.
5. Выход: a – НОД
Ниже приведен пример использования этой реализации алгоритма.
Пример
a=603, b=108
Преобразования алгоритма записаны в таблицу, верхняя строка которой содержит значение переменной a, нижняя – содержимое переменной b. Каждый столбец таблице соответствует состоянию процесса на отдельном шаге.
a6034953872791716310845631845279189b1081081081081081086363454518181899
Ответ: НОД (603,108)=9.
Реализация алгоритма Евклида (вариант алгоритма с делением с остатком)
Вход: a, b >0. 1. Находим разложение a=bq+r, 0≤ r<b2. если r=0 Шаг 5 (выход) 3. a:= b; b:= r. 4. Возвращаемся на Шаг 1 5. Выход: b – НОД. Примерa=603, b=108 a60310863452718 b108634527189603=5·108+63 108=1·63+45 63=145+27 45=127+18 27=118+9 18=29+0 Ответ: НОД (603,108)=9. Бинарный алгоритм ЕвклидаЭтот вариант создан специально для реализации на ЭВМ. В нем учитывается, что операция деления на число 2 или на любую степень двойки является весьма быстрой и простой операцией (в двоичной системе счисления операция деления на 2 есть всего лишь битовый сдвиг вправо). Учтем, что (2 ka,2 sb)=2 min(k,s)( a, b). Алгоритм:Вход: a, b>0.
Представим a и b в виде: ; , где a1, b1 – нечетные числа.
k:=min( k1, k2).
Если a1>b1 Шаг 4
a1< b1 Шаг 3 a1= b1 Шаг 6
Меняем местами a1 и b1.
c:=a1–b1=2sc1 (c1 - нечетное число)
(Заметим, что с обязательно будет четным, а значит ) 5. a1:= b1 , b1:= c1 . Возвращаемся на Шаг 1. 6. Выход: ( a, b)=2 ka1 . Примерa=603, b=108 a1603279 b12799 c199– 1. a1=603, k1=0; b=108=427=2 227 k2=2, b1=27, k=0 2. a1=603> b1=27 Ш4 4. c=603-27=56=649, c1=9 5. a1=27; b1=9 Ш1 1. a1=27; b1=9 2. a1> b1 Ш4 4. c=a1– b1=18=29, 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. 1.3 НОК (наименьшее общее кратное) Если a1\ b, a2\ b, … , an\ b, то b называется общим кратным чисел a1,…, an. Наименьшее положительное общее кратное чисел a1,…, an называется их наименьшим общим кратным (НОК) .Пусть НОД( a, b)= d, тогда можно записать a=da1, b=db1, где ( a1, b1)=1. Пусть a\ M, b\ M M= ak для некоторого целого k, и тогда число – целое. Но, поскольку ( a1, b1)=1, то b1\ k , и тогда k=b1t для некоторого , и . * Очевидно, , М – общее кратное a и b, и (*) дает формулу всех общих кратных. При t=1 имеем M=НОК( a, b). Формулой M = НОК( a, b) t можно представить все общие кратные чисел a и b. ( ). 1.4. Простые числа Числа a1,…, an называются взаимно простыми, если НОД( a1,…, an)=1, попарно простыми, если , НОД( ai, aj)=1. Если числа попарно a1,…, an простые, то они взаимно простые. Обратное неверно. Число p называется простым, если оно имеет лишь два делителя – “1” и р.Число “1” делится только на себя, и не является ни простым, ни составным, а занимает особое место в теории чисел. Число а>1 имеющее более двух делителей, называется составным. Утверждение 1Наименьший не равный единице делитель числа a: , >1, является простым числом. Доказательство:
Пусть q: q>1, q\ a – наименьший делитель а. Если бы q было составным, то нашлось бы число q1>1: q1\ q, и тогда для некоторого целого k выполнялось бы q= kq1 a=qt=q1kt q1\ a, q1< q (то есть нашелся делитель числа a, который меньше q) q – не наименьший делитель числа a. Пришли к противоречию с условием теоремы. Предположение неверное, следовательно верно обратное. q – простое число. Утверждение 2p – наименьший делитель составного числа а, p≠1 . Доказательство:Представим a в виде a=pa1. Поскольку p – наименьший делитель числа a, то a1≥ p a≥ p2 в силу монотонности квадратичной функции на положительной полуоси, p≤ . Теорема Евклида (о простых числах) №1Простых чисел бесконечно много. Доказательство:Пусть простых чисел ровно k штук, и p1,…, pk – все простые числа. Возьмем n=p1p2… pk+1. По предположению, n – составное число, т.к. n> , существует простое число d: d\ n. Но очевидно, исходя из вида числа n, что , получили противоречие с тем, что p1,…, pk – все простые числа. Теорема Евклида (о простых числах) №2 в числовом ряду (1, 2, 3, …) существует k подряд идущих составных чисел. Доказательство:Возьмем m=k+1.m!+2, m!+3,…, m!+ m – составные числа, и их ровно k штук. Решето ЭратосфенаРешето Эратосфена используется для составления таблицы простых чисел, меньших или равных наперед заданного натурального числа N.
Выписываем числа 1 2 3 … N
Первое число, которое больше, чем 1, есть 2. Двойка делится только на 1 и 2, т.е. является простым числом.
Вычеркиваем из ряда (как составные) все числа, кратные 2, кроме самой двойки.
Второе невычеркнутое число есть 3. Оно не делится на 2, иначе оно оказалось бы вычеркнутым, значит 3 делится только на 1 и 3, значит 3 – простое число.
Вычеркиваем из ряда все числа, кратные 3.
Следующее невычеркнутое число есть 5. Оно простое, так как не делится ни на одно число, меньшее самого себя, иначе оно было бы вычеркнуто. Вычеркиваем все числа, кратные 5, кроме самой пятерки.
Этот процесс продолжаем далее для всех невычеркнутых чисел. Когда этим способом вычеркнуты все числа, меньшие p ( p – простое), то все невычеркнутые числа, меньшие p2, будут простыми. Действительно, всякое составное а< p2 уже вычеркнуто, как кратное его наименьшего делителя d: a=da1 который d≤ < p (по утверждению 2). Тогда следуют правила:
Числа, кратные р, вычеркиваются, начиная с p2.
Составление таблицы простых чисел, меньших или равных N, закончено, как только вычеркнуты все кратные простых, меньших или равных
Пример: N=50 . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 1.5. Единственность разложения на простые сомножители. Утверждение 1.Любое целое число a либо взаимно просто с данным простым р, либо р\а. Доказательство: , p – простое число, выполняется ( a, p)\ p. Тогда в силу простоты p, либо ( a, p)= p, либо ( a, p)=1. В первом случае р\а, во втором a взаимно просто с р. Что и требовалось доказать. Теорема (Основное свойство простых чисел)Если a1,…, ak Z, p\( a1… ak) : p\ ai. Доказательство: В силу утверждения 1, либо ( ai, p)=1, либо ( ai, p)= p. Если бы выполнялось ( ai, p)=1 то выполнялось бы ( a1… ak, p)=1, и тогда p не делило бы ( a1… ak). Получили противоречие с условием теоремы : p\ ai. Теорема (О единственности разложения на произведение простых чисел) , а>1 существует единственное разложение a=p1p2… pn, где , рi – простое . Доказательство:Действительно, обозначая буквой p1 наименьший (простой) делитель а, имеем a= p1a1 Если a1>0, то, обозначая p2 наименьший (простой) делитель числа a1, имеем a1= p2a2 и т.д., пока не придем к an=1 для некоторого n (поскольку ряд a1, a2, …, an - убывающий ряд натуральных чисел, то рано или поздно мы придем к единице). Тогда a=p1p2… pn. Показали существование разложения на простые сомножители. Теперь докажем единственность. Предположим, что для того же самого а существует второе разложение на простые сомножители a= q1q2… qs, и, не нарушая общности, предположим, что s≥ n. Тогда p1p2… pn = q1q2… qs * В силу основного свойства простых чисел, q1\( p1p2… pn) i: q1\ pi. Не нарушая общности, предположим, что i=1 q1\ p1. В силу простоты чисел p1, q1, получим p1= q1. Сократив обе части равенства (*) на q1, получим p2… pn = q2… qs, p1= q1Повторив рассуждения для q2, получим p3… pn = q3… qs, p1= q1, p2= q2И т.д. В итоге получим 1= qn+1… qs, p1= q1, p2= q2, … , pn= qnОтсюда qn+1=1, …, qs=1. То есть оба разложения на простые сомножители тождественны. В разложении числа на простые сомножители некоторые из сомножителей могут повторяться. Обозначая p1,…, pk различные из них, а α 1,…, α k – кратности их вхождения в разложение, получим каноническое разложение числа а: Добавим, что задача разложения числа на простые сомножители, или, иначе, задача факторизации, считается сложной задачей, поскольку известные алгоритмы факторизации имеют экспоненциальную или субэкспоненциальную сложность. Ознакомиться с такими алгоритмами можно будет в гл. 2 настоящего пособия. Теорема (о делителях числа)Пусть – каноническое разложение числа a. Тогда все делители а имеют вид , где 0≤ β1≤ α1, 0≤ β2≤ α2, …, 0≤ βk≤ αk. Доказательство:Пусть q\ a a представимо в виде a=dq, тогда все простые делители числа d входят в каноническое разложение числа а с показателями, не меньшими тех, с которыми они входят в каноническое разложение числа а. Следствие 1Количество различных делителей числа есть . Доказательство очевидно, оно следует из числа всевозможных сочетаний в формуле делителя в теореме о делителях числа. Следствие 2НОД( a1,…, an), где ( ), есть , где ( ). Пример.a1=235 2=150, a2=2 257=140, a3=2 35=40. p1=2, p2=3, p3=5, p4=7. a1= , a2= , a3= . НОД( a1, a2, a3)= =25=10. Следствие 3Совокупность общих делителей a1,…, an совпадает с совокупностью делителей НОД( a1,…, an). Следствие 4НОК , где , Пример.НОК(150,140,40)= Следствие 5Если a1,…, an – попарно простые числа, то НОК( a1,…, an) = a1… an Следствие 6Совокупность общих кратных чисел a1,…, an совпадает с совокупностью кратных их наименьшего общего кратного .Доказательства следствий 1–6 предоставляется читателю в качестве упражнения. Отыскать эти доказательства можно в [5] (Виноградов, «Основы теории чисел»). 1.6. Асимптотический закон распределения простых чисел. Решето Эратосфена отыскивает все простые числа от 1 до N. Однако при большом N поиск простых чисел таким способом отнимает много времени. Современная практическая криптография требует использования больших простых чисел – в некоторых стандартах используются простые числа размером порядка 1024 бита. По понятным причинам, невозможно организовать поиск таких больших простых чисел при помощи решета Эратосфена. В настоящее время разработано несколько вероятностных и детерминированных тестов на простоту. Эти тесты определяют, является ли наугад выбранное число простым или составным. Далее мы изучим такие вероятностные тесты, как тест Ферма, Соловея-Штрассена, Миллера-Рабина. Для поиска простых чисел с помощью таких тестов используют следующий подход: из чисел заданного диапазона случайным образом выбирают числа и проверяют их на простоту. Поиск прекращается как только будет найдено простое число. Такой подход называют случайным поиском простых чисел. Для того чтобы оценить время, которое придется затратить на случайный поиск в заданном диапазоне, необходимо знать, сколько примерно простых чисел в этом диапазоне содержится. Конечно, точное распределение простых чисел в N неизвестно, но некоторые сведения об этом распределении у современной математики имеются. Так, в п.4 мы привели теоремы Евклида о простых числах, в которых утверждается, что, с одной стороны, простых чисел бесконечно много, а значит найдется сколь угодно большое простое число, а с другой стороны – что для любого m найдутся m подряд идущих составных, то есть существуют такие сколь угодно длинные диапазоны, на которых простых чисел нет вообще. Более точно на вопрос о распределении простых чисел в N отвечает асимптотический закон распределения простых чисел. Итак, обозначим π(x) – количество простых чисел, меньших либо равных x. Тогда справедлив Асимптотический закон простых чисел . ■ Другими словами, при x→∞, π( x)→ x/ln x. Кроме того, справедлива Теорема Чебышева (1850 г.)Для любого x при некоторых c1<1< c2 выполняется . ■ Учитывая асимптотический закон, можно сказать, что чем x больше, тем c1 и с2 ближе к 1. Для x>1 с2<1,25506, для x≥17 с1=1. Пример.Пользуясь асимптотическим законом, вычислим примерное количество простых 512-битных чисел (таких, чтобы старший, 512-й, бит был равен 1). Наименьшее значение 512-битного числа составляет 2 511, наибольшее – 2 512-1. Таким образом, нужно найти приблизительное количество K простых чисел из диапазона ( x1=2 511, x2=2 512). K = π( x2)—π( x1) ≈ = = = = = . Тогда вероятность при случайном поиске в заданном диапазоне выбрать простое число составляет P = ≈ = ≈ . Если же случайный поиск производить только среди нечетных чисел, то P = ≈ . То есть для того, чтобы путем случайного перебора среди 512-битных нечетных чисел найти простое, в среднем понадобится 178 итераций. Для 1024-битных чисел поиск среди нечетных чисел потребует в среднем 355 итераций. В общем, при увеличении требуемого размера числа (в битах) в 2 раза, среднее время поиска тоже увеличивается в два раза. |
