Малая теорема Ферма. Малая теорема ферма 9В. Се н де ров, ас пива к малая теорема Ферма
 Скачать 0.54 Mb.
|
|
МАЛАЯ ТЕОРЕМА ФЕРМА 9В . СЕ Н ДЕ РОВ, АС ПИВА К Малая теорема Ферма Ч ЕМ ОТЛИЧАЕТСЯ УЧЕНИК МАТЕМАТИЧЕСКОГО класса от ученика географического, экономического, политологического или коррекционного класса Тем, что он больше размышляет над задачами Да, и этим тоже. Ноне только. Еще он знает малую теорему Ферма. Программы обучения математике бывают разные можно начать с подробного изучения геометрии, можно – с комбинаторики, кто-то начинает с теории множеств, все не перечесть. Но малая теорема Ферма прочно вошла в программу математических классов. Компьютерщики авторы учебника Конкретная математика Р.Грэхем, Д.Кнут и О.Паташник – тоже включили ее в тот набор сведений, с которым они знакомят своих студентов. Формулируется эта теорема, открытая советником парламента Тулузы (Франция) Пьером Ферма (в 1640 году, очень коротко если p – простое число, a целое число, то a p – а кратно p. Сразу и невидно, почему скромное с виду утверждение столь важно. Тем не менее, оно заслуживает величайшего внимания. Мы начнем с материала, который доступен семикласснику, а закончим недавними открытиями в криптографии Квант № Иллюстрация В .Х л е б ник о вой КВА Н T $ 2 0 0 0 / № 1 Частные случаи Если из книги вытекает какой-нибудь поучительный вывод, он должен получаться помимо воли автора, в силу самих изображенных фактов. Ги де Мопассан Из любых двух последовательных целых чисел a и a + 1 одно четное, а другое нечетное. Поэтому произведение четно при любом целом Делимость числа a 2 + a на 2 можно доказать и по- другому, разобрав два случая если a четно, то a 2 тоже четно, а сумма двух четных чисел a и a 2 четна если a нечетно, то a 2 тоже нечетно, а сумма двух нечетных чисел a и a 2 четна. Вот так доказывают замечательное свойство многочлена a 2 + a. Впрочем, при p = 2 в малой теореме Ферма фигурирует другой многочлен a 2 – a = (a – 1)a. Все его значения в целых точках – четные числа (докажите!). Теперь рассмотрим многочлен a 3 – a . Его легко разложить на множители a a a a a a 3 2 1 1 1 − = − = − + e j b gb Получили произведение трех последовательных целых чисел a – 1, a и a + 1. Как мы уже знаем, это произведение четно. Поскольку из любых трех последовательных чисел однократно, их произведение (a – 1)a(a + 1) = a 3 – a кратно 3 (и, значит, даже кратно Упражнение 1. При любом целом a сумма a 3 + 5a кратна Докажите это. Многочлен a 4 – a при a = 2 и a = 3 принимает значения 4 – 2 = 14 и 3 4 – 3 = 78. Конечно, эти значения четны, но никакого общего делителя кроме 2 (и 1) у них нет. Не повезло Впрочем, число 4 составное, а малая теорема Ферма говорит только о многочленах вида a p – a, где p – простое число. Пусть p = 5. Вычислим несколько значений многочлена a 5 – a. При a = ± 1 и при a = 0 получаем ноль. Смотрим дальше 2 5 – 2 = 30, 3 5 – 3 = 240, 4 5 – 4 = 1020, 5 5 – 5 = = 3120, 6 5 – 6 = 7770,... Все эти значения кратны числу 30. Поскольку 30 = 2 ⋅ 3 ⋅ 5, доказательство делимости на распадается натри части во-первых, надо доказать, что a 5 – a кратно 2; во-вторых, a 5 – a кратно 3; в-третьих, a 5 – a кратно Первая часть очевидна числа a 5 и a либо оба четны, либо оба нечетны. Не вызывает затруднений и вторая часть a a a 5 4 1 − = − = e j a a a 2 2 1 1 − + = e je j a a a a − + + 1 1 1 2 b g b ge произведение трех последовательных чисел всегда кратно Чуть сложнее третья часть. Нет, конечно, из пяти последовательных целых чисел обязательно однократно, так что произведение (a – 2)(a – 1)a(a + 1)(a + кратно 5. Но a 2 + 1 ≠ (a – 2)(a + Как же быть Самый бесхитростный способ – перебрать все подряд остатки отделения на 5: любое целое число при делении надает в остатке 0, 1, 2, 3 или 4. Если остаток равен 0, то кратен 5 второй множитель произведения – 1)a(a + 1)( a 2 + 1). Если остаток равен 1 или 4, то кратен 5 первый или третий множитель. Если же остаток равен 2 или 3, тов дело вступает четвертый множитель. (Для тех, кто еще не привык работать с остатками, объясним: если a = 5b + 2, те. если a дает остаток 2 при делении на 5, то a 2 + 1 = 5 2 2 b + b g + 1 = 5 5 4 1 2 b b + + e Аналогично можно рассмотреть случай a = 5b + Есть и другой способ a a 2 1 2 2 5 + = − + + b gb значит, если нас интересуют только остатки отделения на, то a 2 + 1 можно-таки заменить на (a – 2)(a + Формулой это записывают так a a 2 1 2 2 + ≡ − + b gb g mod 5 b Предложенное в 1801 году К. Ф. Гауссом обозначение ≡ » еще не раз будет использовано нами. По определению сравнимо с b по модулю n, если a – b кратно те, где k – целое число. Обозначение a b ≡ mod n b g оказалось удачным потому, что свойства сравнений похожи на свойства обычных равенств. Сравнения можно складывать если a b ≡ mod n b g и c d ≡ mod n b g , то a + + c ≡ b + d mod n b g . В самом деле, по определению, a = = b + kn и c = d + ln, где k, l – целые числа. Значит c b kn d ln + = + + + = b g b g b d k l n + + + b что и требовалось. Аналогично, формулы a c b kn d ln − = + − + = b g b g b d k l n − + − b g , ac b kn d ln = + + = b gb g bd knd bln kln + + + = 2 = bd kd bl kln n + + + b позволяют утверждать, что сравнения можно вычитать и умножать. Коли можно умножать, то можно и возводить в степень если a ≡ b mod n b g , то для любого натурального числа m верно сравнение a m ≡ b m mod n Сокращать сравнения надо с осторожностью ≡ 36 (mod но ≡ /6 (mod Упражнения Решите сравнение 3 11 x ≡ mod 101 b g 3. Какие целые числа x удовлетворяют сравнению 14 0 x ≡ mod 12 b g ? 4. Пусть k ≠ 0 . Докажите, что а) если ka kb ≡ mod kn b g , то a b ≡ mod n б) если ka kb ≡ mod n b g и числа k, n взаимно просты, то a b ≡ mod n Продолжим изучение многочленов вида a p – a: докажем, что при любом целом a число a 7 – a кратно 7. Как всегда, можно рассмотреть все 7 остатков отделения на 0 7 – 0 = 0, 1 7 – 1 = 0, 2 7 – 2 = 126 = 7 ⋅ 18,..., 6 7 – 6 = = 279930 = 7 ⋅ 39990. (Можно и чуточку сэкономить: поскольку любое целое число представимо в виде a = 7b, 7b ± 1, 7b ± 2 или 7b ± 3, очевидно, при проверке малой теоремы Ферма для p = 7 можно ограничиться рассмотрением случаев a = 0, 1, 2 и Но бездумная проверка не может научить нас ничему интересному. Лучше рассмотрим разложение на МАЛАЯ ТЕОРЕМА ФЕРМА 11множители:a a a a 7 6 1 − = − = e j a a a 3 3 1 1 − + = e je j = a a a a a a a − + + + − + 1 1 1 1 2 2 b ge jb ge Поскольку a a a a 2 2 1 6 7 + + = + − + ≡ e j a a 2 6 + − = = a a − + 2 3 b gb g mod 7 b и a a a a 2 2 1 6 − + ≡ − − = a a + − 2 3 b gb g mod 7 b имеем a a a a a 7 1 2 3 − ≡ − − + b gb gb g a a a + + − 1 2 3 b gb gb g mod 7 b Произведение семи последовательных целых чисел кратно Упражнение 5. Докажите, что а) наибольший общий делитель чисел вида a 7 – a равен 42; б) наибольший общий делитель чисел вида a 9 – a равен 30. (Заметьте 30 не кратно. Это находится в согласии стем, что число 9 непростое, а составное.) Теперь рассмотрим число p = 11. Очевидно a a a 11 10 1 − = − = d i a a a 5 5 1 1 − + = d id i = a a a a a a − + + + + 1 1 4 3 2 b ge j a a a a a + − + − + 1 1 4 3 2 b ge Тут не так-то просто догадаться, как быть дальше. Но полный перебор всех 11 остатков все еще возможен. И когда мы его выполним, окажется, что значения многочлена кратны 11 при a ≡ 3, 4, 5 или mod 11 b g , а значения многочлена a 4 – a 3 + a 2 – a + кратны 11 при a ≡ 2, 6, 7 или Между прочим, если мы раскроем скобки в произведении, получим a a a a 2 2 7 12 14 45 − + − + ≡ e je j a a a a 2 2 4 1 3 1 + + − + = e je j = a a a a 4 3 2 10 1 + − + + ≡ a a a a 4 3 2 1 + + + + mod 11 b Аналогично можно проверить, что (a – 2)(a – 6)(a – – 7)(a – 8) ≡ a 4 – a 3 + a 2 – а + 1 mod 11 b Что дальше При p = 13, если действовать нашим способом, придется возводить в двенадцатую степень числа от 1 доили раскрывать скобки в произведении тринадцати множителей a – 6, a – 5,..., a + 5, a + Заниматься этим не хочется, даже если ограничиться возведением в степень чисел 1, 2, 3, 4, 5, 6 или перемножать всего лишь шесть скобок (a 2 – 1)(a 2 – 4)(a 2 – – 9)(a 2 – 16)(a 2 – 25)(a 2 – Чем больше p, тем больше вариантов надо перебирать. Поэтому мы прекратим разбор частных случаев и перейдем к доказательству малой теоремы Ферма, которое охватывает сразу все простые числа Упражнения а) Произведение любых четырех последовательных целых чисел кратно 24. Докажите это. б) Произведение любых пяти последовательных целых чисел кратно 120. Докажите это. в) Докажите, что a 5 – 5 3 a + 4a при всяком целом a кратно 120. 7. Для любого натурального a число a 5 оканчивается на туже цифру, что и a. Докажите это Докажите, что m n 5 – mn 5 кратно 30 при любых целых m и n. 9. Если число k не кратно ни 2, ни 3, ни 5, то k 4 – 1 кратно. Докажите это а) Докажите, что 2222 5555 + 5555 2222 кратно 7. б) Найдите остаток отделения числа 13 15 14 16 17 + FH IK + 18 19 20 на 7. 11. Докажите, что число 11 10 – 1 оканчивается на два нуля (т.е. кратно 100). 12. а) Найдите все целые числа a, для которых a 10 + оканчивается цифрой ноль. б) Докажите, что ни при каком целом a число a 100 + 1 не оканчивается цифрой ноль Пусть n – четное число. Найдите наибольший общий делитель чисел вида a n – a, где a – целое число. Пусть n – натуральное число, n > 1. Докажите, что наибольший общий делитель чисел вида a n – a, где a пробегает множество всех целых чисел, совпадает с наибольшим общим делителем чисел вида a n – a, где a = 1, 2, 3,..., 2 n . (Заметьте: из этого следует, что наибольший общий делитель чисел вида a n – a, где a – целое, совпадает с наибольшим общим делителем чисел такого вида, где a – натуральное.) Общий случай И каждого в свою уложат яму. Эжен Гильвик Выпишем в строчку числа 1, 2, 3, ..., p – 1, домножим каждое из них на k, где k не кратно p, и рассмотрим остатки отделения на p. Например, при p = 19 и k = получим таблицу 1. В нижней строке таблицы – те же самые числа, что ив верхней, только они расположены в другом порядке Оказывается, это общий закон не только при p = 19 и k = 4, но при любом простом p и не кратном p целом числе k всегда получатся те же самые числа 1, 2, 3, ..., p – 1, возможно, записанные в некотором другом порядке. Почему? Ну, во-первых, в нижней строке не может появиться 0, ибо произведение не кратных простому числу p чисел a и k не может быть кратно p. Во-вторых, все числа нижней строки разные (это легко доказать от противного если бы числа ak и bk давали при делении на p одинаковые остатки, то разность ak – bk = (a – b)k была бы кратна p, что невозможно, поскольку a – b не кратно p). Этих двух замечаний достаточно ненулевых остатков отделения на p существует p – 1 штук, все они вынуждены по одному разу появиться в нижней строке таблицы. Упражнения 15. Существует ли такое натуральное n, что число 1999n оканчивается на цифры 987654321? 16. Если целое число k взаимно просто с натуральным числом n, то существует такое натуральное число x, что kx – 1 кратно n. Докажите это Если целые числа a и b взаимно просты, то любое целое число c представимо в виде c = ax + by, где x, y – целые числа. Докажите это. Как вы помните, малая теорема Ферма утверждает, что при любом целом k и простом p число k p – k = k k p− − 1 1 d Таблица п 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 a 4 0 4 4 4 8 4 2 5 6 5 0 6 4 6 8 6 2 7 4 a 9 1 d o m 2 6 0 1 4 1 8 1 3 7 1 1 5 п 2 3 4 5 6 7 8 9 a 4 4 8 2 1 6 1 0 2 4 2 8 2 2 3 6 3 4 a 9 1 d o m 4 8 2 1 6 1 1 5 9 3 1 7 1 КВА Н T $ 2 0 0 0 / № 1 кратно p. Значит, для чисел k, не кратных p, теорему можно формулировать следующим образом: Теорема 1. Если целое число k не кратно простому числу p, то k p−1 дает остаток 1 при делении на Доказательство Поскольку остатки отделения на p чисел k, 2k, 3k, ..., (p – 1)k – это (с точностью до перестановки) числа 1, 2, 3, ..., p – 1, то k k k p k ⋅ ⋅ ⋅ ⋅ − ≡ 2 3 1 K b g 1 2 3 1 ⋅ ⋅ ⋅ ⋅ − K p b g mod p откуда k p p p− − ≡ − 1 1 1 b g b g ! ! mod p Сократив на (p – 1)!, получим желаемое p− ≡ 1 1 mod p А тот, кто не решил упражнение 4 б) и не знает, почему сравнения можно сокращать (на число, взаимно простое с модулем, пусть рассуждает следующим образом поскольку произведение k p p− − ⋅ − 1 1 1 e j b g ! кратно p, а число – 1)! не кратно p, то число k p−1 – 1 кратно простому числу Упражнения Найдите остаток отделения числа 3 2000 на 43. 19. Если целое число a не кратно 17, то a 8 – 1 или a 8 + 1 кратно. Докажите это. Докажите, что m n 61 – mn 61 кратно 56786730 при любых целых m и n. 21. Найдите все такие простые числа p, что 5 2 p + 1 кратно p. 22. Пусть p – простое число, p ≠ 2. Докажите, что число – 5 p – 2 кратно 6p. 23. Если p – простое число, то сумма 1 1 p− + 2 1 p− + ... + p p − − 1 1 b при делении надает остаток p – 1. Докажите это. Шестизначное число кратно 7. Его первую цифру стерли и затем записали ее позади последней цифры числа. Докажите, что полученное число тоже кратно 7. (Например, из кратных чисел 632387 и 200004 таким образом получаем числа 323876 и, которые тоже кратны 7.) 25. Пусть p – простое число, отличное от 2, 3 и 5. Докажите, что число, записанное p – 1 единицей, кратно p. (Например кратно 7.) 26*. Докажите, что для любого простого p число, состоящее из 9p цифр (сначала p единиц, потом p двоек, p троек, ..., наконец, p девяток, при делении надает такой же остаток, как и число Таблицы умножения Назло ей я все-таки помножил землекопов. Правда, ничего хорошего про них не узнал, но зато теперь можно было переходить к другому вопросу. Л.Гераскина Рассмотрим все n – 1 разных ненулевых остатков отделения на n. Составим таблицу умножения, написав на пересечении го столбца и й строки остаток отделения на n произведения ab. Например, при n = 5 получим таблицу 2, при n = 11 — таблицу Поскольку в обоих примерах число n простоев каждой строке, как ив каждом столбце, возникает некоторая перестановка чисел 1, 2, ..., n – 1. Если же рассмотреть составное число, тов таблице обязательно встретится нуль. Например, при n = 4 имеем 2 2 0 ⋅ ≡ (табл.4); не лучше ситуация и при n = 12 (табл опять в некоторых строках есть нули И вообще, при любом составном числе n = ab, где 1 < a, b < n, на пересечении й строки иго столбца стоит остаток отделения нате. Итак, если n составное, то имеются делители нуля ненулевые остатки a и b, произведение ab которых кратно n, иными словами, равно нулю по модулю n. Но даже при составном n в некоторых строках таблицы умножения нет нулей. В таблице 4 таковы первая и третья строки, а в 2 3 1 1 2 3 2 2 0 2 3 3 Таблица Таблица 2 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1 × 1 2 3 4 5 6 7 8 9 0 1 1 1 2 3 4 5 6 7 8 9 0 1 2 2 4 6 8 0 1 1 3 5 7 9 3 3 6 9 1 4 7 0 1 2 5 8 4 4 8 1 5 9 2 6 0 1 3 7 5 5 0 1 4 9 3 8 2 7 1 6 6 6 1 7 2 8 3 9 4 0 1 5 7 7 3 0 1 6 2 9 5 1 8 4 8 8 5 2 0 1 7 4 1 9 6 3 9 9 7 5 3 1 0 1 8 6 4 2 0 1 0 1 9 8 7 6 5 4 3 2 Таблица 3 × 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 2 3 4 5 6 7 8 9 0 1 1 1 2 2 4 6 8 0 1 0 2 4 6 8 0 1 3 3 6 9 0 3 6 9 0 3 6 9 4 4 8 0 4 8 0 4 8 0 4 8 5 5 0 1 3 8 1 6 1 1 4 9 2 7 6 6 0 6 0 6 0 6 0 6 0 6 7 7 2 9 4 1 1 6 1 8 3 0 1 5 8 8 4 0 8 4 0 8 4 0 8 4 9 9 6 3 0 9 6 3 0 9 6 3 0 1 0 1 8 6 4 2 0 0 1 8 6 4 2 1 1 1 1 0 1 9 8 7 6 5 4 3 Таблица 5 МАЛАЯ ТЕОРЕМА ФЕРМА 13таблице 5 – первая, пятая, седьмая и одиннадцатая. Подумав немного, можно понять, что нули присутствуют в тех и только тех строках, номера которых имеют с числом n общий делитель, отличный от 1 (докажите это!). Давайте же вычеркнем из таблицы все такие строки и столбцы. (Если n – простое число, то вычеркивать ничего не придется) При n = 4 получим таблицу из двух строки столбцов (табл, а при n = 12 останется таблица размером 4 × 4 (табл.7). Упражнение 27. Заметьте, что каждая из таблиц 2–7 симметрична относительно обеих своих диагоналей. Докажите, что это так для любого Теорема Эйлера Чтобы обобщить малую теорему Ферма на случай составного числа n, оставим в таблице умножения только те строки и столбцы, в которых нет нулей, те. рассмотрим взаимно простые с n остатки отделения на n. В новой таблице строки (и столбцы) отличаются друг от друга лишь порядком, в котором расположены числа. Другими словами, если мы для натурального числа n выпишем все остатки a 1 , a 2 , ..., a r , взаимно простые си домножим каждый из них на взаимно простое с n число k, то получим числа ka 1 , ka 2 ,..., ka r , которые тоже взаимно просты си дают разные остатки при делении на n (докажите!). Итак, строка остатков отделения на n чисел ka 1 , ka 2 ,... ..., ka r может отличаться от строки a 1 , a 2 , ..., a r только порядком расположения чисел. Поэтому точно также, как для простого p, для составного n имеем ka ka a a a r r 1 2 1 2 K K ≡ mod n откуда k a a a r r − ≡ 1 0 1 2 e j K mod n Значит, произведение k a a a r r − 1 1 2 e j K кратно n. Поскольку числа a 1 , a 2 , ..., a r взаимно просты стократно. Если n – простое число, то r = n – 1 и получаем в точности утверждение малой теоремы Ферма. В общем же случае приходим к теореме Эйлера: Теорема 2. Если k – целое число, взаимно простое с натуральным числом n, то k r – 1 кратно n, где r количество взаимно простых с n натуральных чисел, не превосходящих Упражнения Докажите, что если число k не кратно 3, то а) k 3 при делении надает остаток 1 или б) k 81 при делении надает остаток 1 или 242. 29. а) Если a b c 3 3 3 + + кратно 9, то хотя бы одно из целых чисел a, b, c кратно 3. Докажите это. б) Сумма квадратов трех целых чисел кратна 7 в томи только том случае, когда сумма четвертых степеней этих чисел кратна. Докажите это. Докажите, что число 7 7 7 7 7 7 – 7 7 7 7 кратно 10. 31. Каковы три последние цифры числа 7 9999 ? 32. Если целое число a взаимно просто с натуральным числом n > 1, то сравнение ax b ≡ mod n b g равносильно сравнению x a b r ≡ –1 mod n b g . Докажите это Если n – нечетное натуральное число, то 2 n! – 1 кратно Докажите это. Найдите все натуральные n > 1, для которых сумма + 2 n + ... + n n − 1 b g кратна n. 35*. Для каждого натурального числа s существует кратное ему натуральное число n, сумма цифр которого равна s. Докажите это. Функция Эйлера В 1763 году Леонард Эйлер (1707–1783) ввел обозначение (читают фи от эн) для количества r остатков, взаимно простых с n. Например, ϕ 1 b g = 1, ϕ 4 b g = 2, ϕ 12 b g = = Если число p простое, то ϕ p b g = p – 1. Легко вычислить и ϕ p m e j , где m – натуральное число. В самом деле, выпишем всевозможных остатков 0, 1, 2, ..., p m – Из них кратны p в точности остатки 0, p, 2p,..., p m – Значит p p p p m m m m e j = − = − F HG I KJ − 1 Давайте вычислим ϕ 1000 b g – количество чисел первой тысячи, которые не кратны ни 2, ни 5. Для этого из вычтем сначала 500 – именно столько впервой тысяче четных чисел. Не забудем вычесть и 200 – столько впервой тысяче чисел, кратных 5. Что еще Еще мы должны учесть, что некоторые числа (оканчивающиеся цифрой 0) кратны и 2, и 5. Таких чисел 100 штук каждое из них мы учитывали оба раза, а надо было – только один раз Поэтому правильный ответ дает формула g = 1000 – 500 – 200 + 100 = Упражнения Найдите ϕ 2 5 a b d i , где a, b – натуральные числа. Пусть p, q – различные простые числа. Найдите а) ϕ pq b б) ϕ p q a b F H I K , где a, b – натуральные числа Решите уравнения а) ϕ 7 x FH IK = 294; б) ϕ 3 5 x y FH IK = В принципе, примененный нами способ позволяет вычислить для любого натурального числа n. Например, чтобы вычислить ϕ 300 b g , мы можем выписать все числа от 1 дои вычеркнуть 150 четных чисел, а также чисел, кратных 3, и 60 чисел, кратных 5. Затем мы должны вспомнить, что некоторые числа вычеркнуты дважды (а иные даже трижды, и восстановить справедливость, тек числу 300 – 150 – 100 – 60 прибавить чисел, кратных 2 ⋅ 3 = 6, а также 30 чисел, кратных 2 ⋅ 5 = = 10, и 20 чисел, кратных 3 ⋅ 5 = 15. Но и этого недостаточно каждое из десяти чисел, кратных 2 ⋅ 3 ⋅ 5 = = 30, было сначала трижды выброшено (как кратное 2, 3, 5) и затем трижды возвращено (как кратное 6, 10, 15). Но выбросить эти 10 чисел все-таки надо Поэтому 300 150 100 b g = − − − 60 50 30 20 10 80 + + + − = 1 5 7 1 1 1 1 5 7 1 1 5 5 1 1 1 7 7 7 1 1 1 5 1 1 1 1 7 5 Таблица Таблица 6 × 1 3 1 1 3 3 3 1 4 Квант № 1 КВА Н T $ 2 0 0 0 / № 1 Ничего сложного, как видите, нет. Нос ростом количества простых делителей числа n мы будем получать ответ, в котором все больше и больше слагаемых и вычитаемых. В статье Н. Васильева и В.Гутенмахера Арифметика и принципы подсчета (Приложение к журналу Квант за 1994 год) это все подробно объяснено. А здесь мы изложим другой способ. Теорема 3. Функция Эйлера мультипликативна, те m n b g b g b для любых взаимно простых натуральных чисел m и Следствие Если n = p p p a a s a s 1 2 1 2 ⋅ ⋅ K , где p 1 , p 2 ,..., p s различные простые числа, a 1 , a 2 ,..., a s – натуральные числа, то p p p a a s a s b g e j e j e j = ⋅ ⋅ = 1 2 1 2 K = p p p p p p a a a a s a s a s s 1 1 1 2 2 1 1 1 1 2 2 − − ⋅ ⋅ − − − − e je j e Доказательство теоремы 3. Рассмотрим числа вида mx + ny, где 0 ≤ x < n и 0 ≤ y < m. Запишем их в виде таблицы размером n × m. Например, при n = 5 и m = получаем таблицу Остатки отделения на mn всех чисел этой таблицы разные. В самом деле, если бы какие-то два остатка совпали, то было бы выполнено сравнение mx ny mx ny 1 1 2 2 + ≡ + mod mn где 0 ≤ x 1 , x 2 < n и 0 ≤ y 1 , y 2 < m. Отсюда следуют два сравнения ny mx ny 1 1 2 2 + ≡ + mod m b g и ny mx ny 1 1 2 2 + ≡ + mod n Первое приводит к сравнению ny ny 1 2 ≡ mod m из которого вследствие взаимной простоты чисел m и n получаем y y 1 2 ≡ mod m Вспомнив, что 0 ≤ y 1 , y 2 < m, получаем y 1 = Аналогично, сравнение по модулю n приводит к равенству x 1 = Итак, все mn чисел таблицы дают разные остатки при делении на mn. Но возможных остатков отделения на mn ровно столько же, сколько чисел в таблице Значит, рассматриваемые числа дают всевозможные остатки отделения на mn. Другими словами, для любого числа d = = 0, 1,..., mn – 1 существует и единственна такая пара целых чисел x, y, что 0 ≤ x < n, 0 ≤ y < m и d ≡ mx + + ny mod mn В таблице 8 четные числа образуют четыре столбца, а числа, кратные 5, образуют одну строку. Это не случайно: НОД(mx + ny, m) = НОД(ny, m) = НОД(y, аналогично, НОД(mx + ny, n) = НОД(x, n). По этой причине в рассматриваемой таблице числа, взаимно простые с m, расположены в ϕ m b g столбцах (тех, где y взаимно просто с m), а числа, взаимно простые с образуют ϕ n b g строк. Теперь доказательство теоремы 3 не составляет труда: чтобы d было взаимно просто с mn, необходимо и достаточно, чтобы d было взаимно просто с числами m и Такие числа d лежат на пересечении ϕ m b g столбцов (состоящих из чисел, взаимно простых с m) с ϕ n b g строками (состоящими из чисел, взаимно простых с Всего получаем решетку из ϕ m b g ϕ n b g чисел, что и требовалось доказать. Упражнения 39. Запишем числа от 0 до mn – 1 в таблицу из m строки столбцов (табл.9). а) Составьте такую таблицу для m = 3 и n = 4. Зачеркните в ней сначала все четные числа, а затем – те из оставшихся чисел, которые кратны 3. Заметьте, что незачеркнутыми остались в y \ x 0 1 2 3 4 5 6 7 0 0 5 0 1 5 1 0 2 5 2 0 3 5 3 1 8 3 1 8 1 3 2 8 2 3 3 8 3 3 4 2 6 1 1 2 6 2 1 3 6 3 1 4 6 4 1 5 3 4 2 9 2 4 3 9 3 4 4 9 4 4 5 9 5 4 2 3 7 3 2 4 7 4 2 5 7 5 2 6 7 Таблица Таблица 9 0 1 2 n 1 – n n 1 + n 2 + 2 n 1 – 2 n 2 n 1 + 2 n 2 + 3 n 1 – ( m ) 1 – n ( m ) 1 – n 1 + ( m ) 1 – n 2 + n Рис МАЛАЯ ТЕОРЕМА ФЕРМА 15точности числа, взаимно простые си что незачеркнутые числа не образуют решетки. б) Докажите теорему Эйлера последующему плану) числа, взаимно простые с n, заполняют собой ϕ n b g столбцов таблицы 9; 2) остатки отделения на m всех m чисел любого столбца таблицы 9 различны) в каждом столбце присутствует ровно ϕ m b g чисел, взаимно простых с m; 4) число взаимно просто с mn тогда и только тогда, когда оно взаимно просто с n (такие числа лежат в ϕ n b g столбцах) и взаимно просто св каждом столбце таких чисел ϕ m b g ). 40. Окружность разделили n точками на n равных частей. Сколько можно построить различных замкнутых ломаных из n равных звеньев с вершинами в этих точках (Две ломаные, получающиеся одна из другой поворотом, считаем одинаковыми. На рисунке 1 изображены все такие ломаные при n = 20.) 41. Для любых натуральных чисел m и n докажите равенства: а) ϕ ϕ ϕ ϕ m n m n m n b g b g b g d i b g d i = HOK HOД , , ; б) ϕ ϕ mn m n m n b g b g d i b g = ⋅ HOK HOД , , ; в) ϕ ϕ ϕ ϕ m n m n mn m n b g b g b g b g b g d i НОД НОД , , = г) Пусть m и n – натуральные числа, причем НОД(m,n) > Докажите неравенство ϕ mn b g > ϕ ϕ m n b g b g 42. Решите уравнения а) ϕ x b g = 18; б) ϕ x b g = 12; в) x – ϕ x b g = = 12; где ж) ϕ x b g = = x/n, где n – натуральное число, n > 3; з) ϕ nx b g = ϕ x b g , где n – натуральное число, n > Шифры с открытым ключом На вопрос, что он написал в шифровке, Штирлиц ответил Не помню. Теперь это знает только Центр.» Вообразите, что вам нужно получить зашифрованное сообщение от вашего друга, новы с ним не договорились заранее, каким шифром будете пользоваться. Как быть? Существует ли такой метод шифрования, что его можно сообщить всему миру (в том числе и вашему другу, и врагам, но это не даст врагам возможности расшифровать сообщение? Это был бы замечательный шифр в отличие от старых шифров, где главный секрет – ключ, знание которого позволяет и зашифровывать, и расшифровывать сообщения, новый шифр – с открытым ключом каждый может зашифровывать, но только автор шифра может расшифровать получаемые сообщения. Шифр Так начались необычайные события, которые вовлекли в свой круговорот немало людей. Е.Велтистов Скорее всего, шифр с открытым ключом уже изобретен! В 1978 году три математика – Ривест, Шамир и Адлеман – зашифровали некоторую английскую фразу и пообещали награду в 100$ первому, кто расшифрует сообщение y = 968696137546220614771409222543558829057599911 2457431987469512093081629822514570835693147662288 Они подробно объяснили способ шифрования. Сначала фразу бесхитростно (a = 01, b = 02, c = 03,..., z = пробел = 00) записали в виде последовательности цифр. Получилось некоторое 78-значное число x. Затем взяли 64-значное простое число p и 65-значное простое число Перемножили их (не вручную, разумеется, а на компьютере Теперь – главное x ≡ 9007 mod pq Понимаете Они опубликовали и произведение pq, и число 9007, и сам метод шифрования (и, разумеется, число y). Было даже сказано, что из чисел p и q однозначное, а другое 65-значное. В секрете остались только сами числа p и q. Требовалось найти Эта история завершилась в 1994 году, когда Аткинс, Крафт, Ленстра и Лейланд расшифровали эту фразу. Числа p и q оказались равны p = 349052951084765094914784961990389813341776463 8493387843990820577, q = 327691329932667095499619881908344614131776429 В книге Введение в криптографию (М, МЦНМО, 1998 г) сказано Этот замечательный результат (разложение на множители 129-значного числа) был достигнут благодаря использованию алгоритма разложения чисел на множители, называемого методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта и продолжавшейся после предварительной теоретической подготовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно компьютеров, объединенных сетью К сожалению, рассказ о методе квадратичного решета увел бы нас далеко в сторону от основной темы. Потому оставим его до лучших времена здесь обсудим основную идею системы RSA (по первым буквам фамилий авторов, Shamir, Идея очень красива. Во-первых, зная p и q, можно найти ϕ pq b g = (p – 1)(q – 1). Во-вторых (и это главное!), если ef k pq = + 1 ϕ b где e, f, k – натуральные числа, то для любого числа взаимно простого с pq, по теореме Эйлера имеем x x x x x ef k pq = ⋅ ≡ ⋅ = e j b g ϕ 1 mod pq Вы поняли, что такое e и f? В нашем примере e = единственное обязательное математическое требование к числу e – его взаимная простота с числом (p – 1)(q – впрочем, брать e = 1 или e = (p – 1)(q – 1) – 1 вряд ли разумно, если хотите сохранить секреты. А число f, как уже было сказано, – решение сравнения ef ≡ 1 mod ϕ pq b g В Приложении рассказано, как алгоритм Евклида позволяет решать такие сравнения КВА Н T $ 2 0 0 0 / № 1 Сравнения y x x f ef ≡ ≡ mod pq b g показывают, что для нахождения x достаточно найти остаток отделения на pq. (Числа выбраны так, что x < pq. При этом x не кратно ни p, ни q. Не подумайте, что это всерьез нас ограничивает если p и q – большие числа, то вероятность того, что x нацело разделится на p или q, пренебрежимо мала. Кроме того, можно предусмотреть в алгоритме, чтобы в случае чего сообщение x было автоматически как-то так чуть-чуть изменено, без изменения его смысла, что x и pq станут взаимно просты.) Почему многие надеются, что шифр RSA является шифром с открытым ключом Да потому, что числа pq и e можно сделать общедоступными. Тогда зашифровать сообщение сможет любой, у кого есть компьютер (и какая- нибудь программа, позволяющая выполнять действия с многозначными числами. Расшифровать сообщение легко, если мы знаем число f. Но единственный известный ныне способ нахождения числа f требует нахождения чисел p и q, те. разложения произведения pq на множители. А эффективных алгоритмов решения этой задачи пока нет (удача 1994 года не в счет если бы в числах p и q было не 64 и 65, а хотя бы по 300 цифр, то и ресурсов сети Internet не хватило бы. Впрочем, нет сейчас и доказательства того, что никто никогда не научится быстро (математик сказал бы за время, полиномиальное от количества цифр) разлагать числа на простые множи- тели. Приложение Как возводить в большую степень? Чтобы возвести число x в ю степень, по определению, достаточно выполнить 9006 умножений. Но можно обойтись и меньшим числом операций вычислить x 2 , x 2 2 d i = x 4 , x 4 2 F H I K = = x 8 ,..., x 2048 2 F H I K = x 4096 , наконец, x 4096 2 F H I K = x 8192 и воспользоваться формулой x 9007 = x x x x x x x x ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 2 4 8 32 256 512 которая основана на том, что в двоичной системе счисления имеет вид 10001100101111 10 Понимаете Мы разложили 9007 в сумму 1 + 2 + 4 + 8 + 32 + + 256 +512 + 8192 и смогли сильно сэкономить обошлись ю возведениями в квадрат на первом этапе вычислений и ю умножениями на втором этапе. Всего 20 умножений вместо Огромная экономия (Для придирчивого читателя отметим, что выше следовало бы говорить не об умножениях, а об умножени- ях по модулю pq: дабы количество цифр не росло катастрофически, мы всякий раз должны не только перемножать, но и брать остаток отделения на pq. Но сейчас разговор не об этом.) Преимущества изложенного метода возведения в степень тем нагляднее, чем больше показатель степени. Например, если показатель степени состоит не из четырех цифр, как 9007, а из нескольких десятков или сотен цифр, то наивный способ не то что утомителен, а неосуществим ни на каких, даже самых мощных, компьютерах. А основанный на двоичной системе работает ив такой ситуации! Упражнение 43 МС числом разрешено производить две операции увеличить в 2 раза и увеличить на 1». За какое наименьшее число операций можно из числа 0 получить число а) 100; б) 9907; в) n, если в двоичной системе счисления n имеет вид a a a a m m − 1 1 Алгоритм Евклида Алгоритм Евклида – это способ отыскания наибольшего общего делителя, основанный на формуле НОД(a,b) = НОД(a – bq, которая верна для любых целых чисел a, b, q. (Докажите эту формулу) Подробно о нем рассказано в статье Н.Васильева «Алгоритм Евклида и основная теорема арифметики (Приложение к журналу Квант № 6 за 1998 год. Собственно говоря, нам нужен даже не алгоритм Евклида, а основанный на нем способ решения линейных уравнений. Итак, даны два взаимно простых числа e ив интересовавшем нас случае m = ϕ pq b g , но здесь это неважно. Нужно найти такие числа f и k, что ef = 1 + Если бы m было не очень большим, то можно было бы выполнить полный перебор всех m остатков. Но если m большое, то перебор нереален. Оказывается, алгоритм Евклида позволяет быстро решать эту задачу. Чтобы объяснить, как он работает, рассмотрим пример e = = 9007, m = 19876. (Мы хотели взять сто-с-лишним-значное число m, нов последний момент струсили) Уравнение = 1 + 19876k можно записать в виде = 1 + 9007 ⋅ 2k + те – 2k) = 1 + Обозначим a = f – 2k. Тогда = 1 + Заметьте получилось уравнение того же типа, что и исходное, только коэффициенты стали меньше. Теперь следующий шаг + 1559a = 1 + те = 1 + 1862(k – Обозначим k – 4a = b, тогда = 1 + Далее – b) = 1 + Обозначив a – b = c, получаем уравнение = 1 + Дальше – также = c – 6d, 44x = 1 + 39d; 5x = 1 + 39(d – x), y = d – x, 5x = 1 + Машина продолжила бы вычисления дальше, пока коэффициент при одной из неизвестных не стал бы равен 1. А мы остановимся уже здесь очевидно, x = 8, y = 1 – одно из решений (Окончание см. нас ШКОЛА В « КВАНТЕ штук в кубическом метре, но все они одинаковы и находятся в среднем на одном и том же расстоянии друг от друга — порядка 1 3 N . Ив результате найдем некоторую эффективную, или среднеобъемную, диэлектрическую проницаемость такой пузырьковой жидкости. Но даже эту скромную программу выполнить не очень легко, да это и необязательно делать сейчас до конца – на основе двух рассмотренных выше примеров ясно, что результат будет зависеть от суммарного объема пузырьков, попавших в конденсатор, и что временнáя зависимость тока будет скорее всего иной, чем в упомянутых примерах. А что еще мы не учли в этих случаях Многое. Например, что диэлектрик втягивается в конденсатор. Это значит, что в первом случае снарядного течения газовый пузырь, попавший в конденсатор, будет сжиматься слева и справа двумя пробками жидкости. Тоже самое будет происходить и с пузырьковой жидкостью, если суммарный объем пузырьков будет непостоянен в пространстве, так что движение такой газожидкостной смеси в конденсаторе не будет равномерным. Далее, в реальности существует сопротивление проводов и внутреннее сопротивление источника напряжения. Если их сумма равна r, то разность потенциалов между пластинами конденсатора запишется в виде q C t U rI t b g b и уже не будет постоянной величиной. А если учесть еще индуктивность цепи и соответствующую ей ЭДС самоиндукции, то закон Кирхгофа даст страшное дифференциальное уравнение для заряда q dt r dq dt q C t U 2 2 + + = b которое описывает затухающие колебания. Решить это уравнение сложно, так как емкость конденсатора изменяется со временем (в этом-то и состоит суть метода, но можно ожидать, что на вышенарисованные кривые зависимости заряда и тока от времени наложатся гармошки колебаний (см. рис.2, точечные кривые). Кроме того, можно предложить и другую схему измерений. Например, зарядить конденсатор от какого-либо источника, затем отключить последний и сохранять на пластинах постоянный заряд (вот тут-то и пригодится пренебрежимо малая электропроводность жидкости. Тогда при прохождении через конденсатор жидкости с различным содержанием газа в пузырьках будет изменяться разность потенциалов между пластинами. Такие приборы существуют и называются емкостными датчиками. Надо признаться, что такими способами мы найдем только суммарный относительный объем газовой фазы, а не концентрацию пузырьков. Не худо было бы определить как-нибудь и их средний размер. Нужно, следовательно, использовать еще какие-то физические явления и приборы (например, оптические)... Так что, прежде чем открыть бутылку нарзана, подумайте о числе пузырьков и законах физики. И – приятного аппетита! последнего уравнения. Зная x и y, легко находим d = x + y = 9, c = x + 6d = 62, b = d + 5c = 319, a = b + c = 381, k = b + 4a = 1843, f = a + 2k = Победа Числа k и f найдены (Проверка 9007 ⋅ 4067 = = 36631469 = 1 + Упражнение 44* (для тех, кто очень любит программировать. а) Найдите число f, которое нашли Аткинс, Крафт, Ленстра и Лейланд. б) Расшифруйте фразу, зашифрованную в году Ривестом, Шамиром и Адлеманом. Что дальше? Что остается от сказки потом, После того, как ее рассказали? В.Высоцкий Подытожим. Впервой части статьи мы доказали малую теорему Ферма и ее обобщение – теорему Эйлера. Рассказали о практическом применении теоремы Эйлера в криптографии. Правда, осталось тайной, откуда взялись числа p, точнее говоря, как можно конструировать большие – в несколько десятков или сотен цифр – простые числа). Во второй части мы расскажем обоснованных на малой теореме Ферма методах конструирования больших простых чисел. Расскажем и о числах Кармайкла, история которых Малая теорема Ферма (Начало см. нас. началась в древности, а существование бесконечного множества которых доказано в 1994 году. Малую теорему Ферма необязательно доказывать именно так, как это сделано выше. Во второй части мы изложим другие способы. Один из них приведет к теореме о существовании первообразного корня по простому модулю и далее к теореме о строении мультипликативной группы вычетов по (не обязательно простому) модулю Чтобы вы лучше оценили силу результатов второй части статьи, подумайте над следующими задачами. Все они будут решены во второй части. Не огорчайтесь даже в том случае, если ни одна из них не получится это не упражнения, а довольно трудные задачи! Задачи 1. Существует ли такое составное число n (число Кармай- кла), что для любого целого числа a разность a n – a кратна n? 2. Ни для какого натурального числа n число 2 n + 1 не кратно n + 1. Докажите это Если 2 n + 1 кратно n, то n = 1 или n кратно 3. Докажите это Для каких n числа 1, 2,... ..., n – 1 можно расставить вдоль окружности так, чтобы для любых подряд идущих чисел a, b, c разность b 2 – ac была кратна На рисункае 2 изображен случай Для каких простых чисел p существует такое целое число a, что a a a a 4 3 2 1 + + + + кратно p? 1 3 2 6 4 Рис. 2 |