Алгоритмічні основи криптології
І Рівень
1. Означення найбільшого спільного дільника.
Визначення. Число d ??Z, що ділиться одночасно на числа а, b, c, ... , k ??Z, називається спільним дільником цих чисел. Найбільше d з такою властивістю називається найбільшим спільним дільником. Позначення: d = (a, b, c, ..., k).
Перелічимо, подекуди доводячи, основні властивості найбільшого спільного дільника.
Теорема (Властивість 1) . Якщо (a, b) = d, то знайдуться такі цілі числа u і v, що d=au+bv.
Доказ . Розглянемо множину P = { au + bv ??u,v ??Z }. Очевидно, що P ??Z , причому P – ідеал у Z. Очевидно, що a, b, 0 ??P. Нехай x, y ??P і y ??0. Тоді залишок ділення x на y належить P. Дійсно:
x = yq + r, 0 ??r < y,
r = x – yq = (au1 + bv1) – (au2+bv2) q=a ( u1 – u2 q)+ b (v1–v2q) ??P.
Нехай d ??P - найменше додатне число з P (задумайтеся, чому таке існує!). Тоді а ділиться на d. Справді, a=dq+r1, 0 ??r1< d, a ??P, d ??P, значить r1??P, отже r1=0. Аналогічно одержуємо, що b ділиться на d, отже d - спільний дільник a і b.
Оскільки d ??P, то d = au0+ bv0. Якщо тепер d1 - спільний дільник a і b, то d1 | (au0+bv0), тобто d1| d. Значить d ??d1 і d - найбільший спільний дільник.
Властивість 2 . Для будь-яких цілих чисел а і k справедливо: ( а , kа ) = а ; (1, а ) = 1.
Властивість 3 . Якщо a = bq + c , то сукупність спільних дільників a і b збігається із сукупністю спільних дільників b і c , зокрема,
( a , b ) = ( b , c ).
Доказ. Нехай d | a , d | b , тоді d | c . Нехай d | c , d | b , тоді d | a .
Проілюструємо цей доказ на давньогрецький лад. Подивіться на рис. 2:

Рис. 2
Якщо d ціле число разів укладається в а і в b , то, очевидно, що d мусить ціле число разів укластися й у с.
Властивість 4 . Нехай a , b і m - довільні цілі числа. Тоді
( am , bm ) = m ( a , b ).
Доказ. Якщо d - найбільший спільний дільник чисел а і b , то dm | am і dm | bm , тобто dm - дільник am і bm . Покажемо, що dm - найбільший спільний дільник цих чисел. Оскільки d - найбільший спільний дільник чисел а і b , то, відповідно до властивості 1, для деяких цілих чисел u і v виконується рівність d = au + bv. Помноживши цю рівність на m, одержимо:
dm = amu + bmv .
Видно, що якщо деяке число s ділиться одночасно на am і bm , то s має ділитися і на dm , тобто s ??dm , отже, dm - найбільший спільний дільник.
Властивість 5 . Нехай s - дільник а і b . Тоді:
(a/s,b/s)=(a,b)/s
Доказ .
(a,b)=(a/s*s,b/s*s)=s(a/s,b/s)
Властивість 6 . Очевидно тепер, що
(a/(a,b),b/(a,b))=1
Властивість 7 . Якщо ( a , b ) = 1, то ( ac , b ) = ( c , b ).
Доказ . Нехай ( c, b ) = d . Маємо: d | b , d | c , отже d | ac , тобто d - дільник ас і b . Нехай тепер ( ac , b ) = s . Маємо: s | b , s | ac , s - дільник b , тобто або s = 1, або s не ділиться на а . Це означає, що s | c , значить s | d . Отже, d і s поділяються один на одного, тобто d = s.
2. Які числа називаються взаємно простими.
Цілі числа a і b називаються взаємно простими, якщо ( a , b ) = 1.
Згадуючи властивість 1 з попереднього пункту, легко помітити, що два числа a і b є взаємно простими тоді і тільки тоді, коли знайдуться цілі числа u і v такі, що au + bv = 1.
3. Означення ланцюгового дробу.
Ланцюговий (чи неперервним ) дробом називається вираз виду:
EMBED Equation.3
Домовимося називати числа q 1 , q 2 ,..., q n ,... - неповними частками і вважаємо, що q 1 ??Z, а q 2 ,..., q n ,... ??N . Числа
??1 = q 1 , ??2 = q 1 +EMBED Equation.3, ??3 = q 1 +EMBED Equation.3, і т.д.
називаються прямуючими дробами ланцюгового дробу ??.
Ланцюговий дріб може бути кінцевим (має скінченне число дробових ліній і неповних часток), так і нескінченним вниз і вправо. У першому випадку дріб є деяким раціональним числом, у другому - поки незрозуміло чим дріб взагалі є, але зрозуміло, що всі його прямуючі дроби - раціональні числа.
Домовимося називати значенням (чи величиною) нескінченного ланцюгового дробу границю нескінченної послідовності його прямуючих дробів:
EMBED Equation.3
(поки без усякого доказу існування цієї границі).
Алгоритм Евкліда.
. Алгоритм Евкліда.
Слово "алгоритм" є російською транскрипцією латинізованого імені видатного арабського математика ал-Хорезми Абу Абдули Мухаммеда ібн ал-Маджусі (787 - 850) і означає в сучасному смислі деякі правила, список інструкцій чи команд, виконуючи які, хтось досягне необхідного результату. Алгоритм, що дозволяє за заданими натуральними числами a і b знаходити їхній найбільший спільний дільник, вважається придумав самий впливовий математик усіх часів і народів - Евклід, він викладений у IX книзі його знаменитих "Початків".
Відступ "Панегірик Евкліду"
Про життя Евкліда ми не маємо ніяких достовірних зведень, можливо, що він не був реальною історичною особистістю, а був колективним псевдонімом деякої групи Олександрійських математиків, типу Ніколя Бурбаки. Якщо він жив, то він жив за часів Птолемея Першого (306 - 283), якому, відповідно до переказу, він сказав "До геометрії немає царської дороги". Але Птолемеї свідомо культивували науку і культуру в Олександрії, тому не звертали уваги на такі слова своїх учених.
Найбільш знаменитий твір Евкліда - тринадцять книг його "Начал", але є ще й інші дрібні опуси. Ми не знаємо, яка частина цих праць належить самому Евкліду і які частини складають компіляції, але в цих працях виявляється разюча проникливість і далекоглядність. Це перші математичні праці, що дійшли до нас від древніх греків цілком. В історії Західного світу "Начала", після Біблії, - книга, що найбільше число раз видана і найбільш вивчена. Велика частина нашої шкільної геометрії запозичена буквально з перших шести книг "Начал", традиція Евкліда дотепер тяжіє над нашим елементарним навчанням. Для професійного математика ці книги усе ще мають непереборне зачарування, а їх логічна дедуктивна побудова вплинула на сам спосіб наукового мислення більше, ніж інший здобуток.
Панегірик кінчений.
Нехай дані два числа a і b ; a ??0, b ??0, вважаємо, що a > b . Символом := у записі алгоритму позначаємо присвоювання. Алгоритм:
1. Ввести a і b .
2. Якщо b = 0 , то Відповідь: а . Кінець .
3. Замінити r := "залишок від ділення а на b ", а := b , b := r .
4. Йти на 2.

рис.3.
Як і чому виконання цього коротенького набору інструкцій приводить до знаходження найбільшого спільного дільника ми з'ясуємо трохи пізніше, зараз же хочеться сказати кілька слів про сам алгоритм. Покрокове виконання алгоритму Евкліда переконують у його простоті без строкатості. Проілюструємо роботу алгоритму на грецький лад мал. 3:
У сучасному буквеному записі, що кочує з одного підручника в іншій, алгоритм Евкліда виглядає так: a > b; a, b ??Z .
Маємо: b > r 1 > r 2 >... > r n > 0, отже процес обірветься максимум через b кроків. Дуже цікавий і практично важливе питання в тому, коли алгоритм Евкліда працює особливо довго, а коли швидко, ми розглянемо трохи пізніше. Покажемо зараз, що r n = ( a , b ). Переглянемо послідовно рівності зверху вниз: усякий дільник а і b ділиться на r1 , r2 ,..., rn . Якщо ж переглядати цей ланцюжок рівностей від останнього до першого, то видно, що rn | rn -1 , rn | rn -2 , і т.д., тобто rn ділиться на а і b . Тому rn - найбільший спільний дільник чисел а і b .
З його розгляду алгоритму Евкліда зрозуміло, що сукупність дільників а і b збігається із сукупністю дільників ( a , b ). Ще він дає практичний спосіб одержання чисел u і v з Z (чи, якщо завгодно, з теореми пункту 2) таких, що r n = au + bv = ( a, b ).
Дійсно, з ланцюжка рівностей маємо:
r n = r n -2 - r n -1 q n = r n -2 - ( r n -3 - r n -2 q n -1 ) q n = ...
(йдемо по ланцюжку рівностей знизу нагору, виражаючи з кожної наступної рівності залишок і підставляючи його у вираз, що одержаний вже до цього моменту)
... = au + bv = ( a , b ).
Приклад. Нехай а = 525, b = 231. Віддамо ці числа на розтерзання алгоритму Евкліда: (нижче приводиться запис ділення куточком, і кожен раз те, що було в куточку, а саме дільник, дописується до залишку ділення з лівої сторони, а залишок, як новий дільник, береться в куточок)
Запис того самого у вигляді ланцюжка рівностей:
525 = 231 · 2 + 63 231 = 63 · 3 + 42 63 = 42 · 1 + 21 42 = 21 · 2
Таким чином, (525, 231) = 21. Лінійне представлення найбільшого спільного дільника:
21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 = 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) = 525 · 4 - 231 · 9,
і наші горезвісні u і v з Z рівні, відповідно, 4 і - 9.
Означення простого числа.
Число р ??N , р ??1, називається простим, якщо р має лише два додатних дільники: 1 і р. Інші натуральні числа (крім 1) прийнято називати складеними. Число 1 має особливий статус за домовленістю, – воно ні просте, ні складене.
Коли алгоритм Евкліда працює найдовше?
Означення числа порівняльного за модулем
Визначення. Нехай а, b ??Z , m ??N. Число а порівняльне з b за модулем m, якщо а і b при діленні на m мають однакові залишки: a ??b(mod m) .
Означення повної системи лишків.
Визначення. Будь-яке число з класу еквівалентності ??m називається лишком за модулем m. Сукупність лишків, узятих по одному з кожного класу еквівалентності ??m, називається повною системою лишків за модулем m (у повній системі лишків усього m чисел). Безпосередньо самі залишки ділення на m називаються найменшими невід’ємними лишками і утворюють повну систему лишків за модулем m.
Означення зведеної системи лишків
Визначення. Зведеною системою лишків за модулем m називається сукупність усіх лишків з повної системи, взаємно простих з модулем m.
Зведену систему звичайно вибирають з найменших невід’ємних лишків. Зрозуміло, що зведена система лишків за модулем m містить ?(m) лишків, де ?(m) – функція Ейлера – кількість чисел, менших за m і взаємно простих з m.
Що означає розв’язати порівняння.
Розв’язати порівняння – означає знайти всі ті х, що задовольняють даному порівнянню, при цьому весь клас чисел за mod m вважається одним розв’язком.
Скільки розв’язків має порівняння за простим модулем p.
Якщо порівняння axn+a1 xn-1+…+an??0(mod p) степеня n за простим модулем р має більше n різних розв’язків, то всі коефіцієнти a,a1 ,…,an кратні р.
Доказ. Нехай порівняння axn +a1 xn-1+…+an??0(mod p), має n+1 розв’язок і x1 ,x2 ,…,xn,xn+1–найменші невід’ємні лишки цих розв’язків
Які порівняння називаються рівносильними?
Порівняння називаються рівносильними, якщо вони мають однакові розв’язки.
Наведіть функцію знаходження кількості дільників даного числа.
Нехай ??( а) = а 0 ??1 - тотожна одиниця (свідомо мультиплікативна функція). Тоді, якщо
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-004.gif",
та тотожність леми 1 пункту 13 набуває вигляду:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-001.gif",
- це не що інше, як кількість дільників числа a .
Наведіть функцію знаходження суми дільників даного числа.
Нехай ??( a ) = a 1 ??a - тотожна мультиплікативна функція. Тоді, якщо
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-004.gif",
то тотожність леми 1 пункту 13 набуває вигляду:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-002.gif"
сума всіх дільників числа a .
Означення алгоритму.
Означає в сучасному смислі деякі правила, список інструкцій чи команд, виконуючи які, хтось досягне необхідного результату.
Чи можна розкласти довільне ціле число відмінне від -1, 0, 1 за допомогою добутку простих чисел?
ІІ рівень
Типи задач в теорії алгоритмів. Наведіть характеристики.
Задача обчислення функції EMBED Equation.3 полягає у знаходженні для вказаного слова EMBED Equation.3 значення функції EMBED Equation.3 . Ми будемо описувати задачі обчислення наступним чином:
Задано: EMBED Equation.3 .
Обчислити: EMBED Equation.3 .
Втім, коли нам не буде настільки важливо, в якому алфавіті і як саме кодуються аргументи та значення функції, ми допускатимемо і менш формальні описи задач на кшталт
Задано: EMBED Equation.3 .
Обчислити: EMBED Equation.3 .
Іноді задачу у вищеозначеному сенсі ми будемо називати масовою. Конкретне задане EMBED Equation.3 називатимемо індивідуальною задачею. Значення EMBED Equation.3 будемо називати розв'язком індивідуальної задачі EMBED Equation.3 . Масову задачу можна вважати нескінченним набором індивідуальних задач.
Нехай EMBED Equation.3 — множина слів у алфавіті А*. Часто L називають мовою. Задача розпізнавання мови L полягає у визначенні, належить задане слово EMBED Equation.3 цій мові, чи ні:
Задано: EMBED Equation.3 .
Розпізнати: EMBED Equation.3 ?
Наприклад,
Задано: EMBED Equation.3 .
Розпізнати: чи є EMBED Equation.3 повним квадратом ?
Індивідуальною задачею є будь-яке задання слова w. Розв'язком індивідуальної задачі є відповідь "так" чи "ні", яку прийнято кодувати символами 1 та 0 відповідно.
Ще один різновид задачі, який нам буде траплятися, називається задачею пошуку елемента із заданою властивістю. Нехай алфавіт А не містить символу # і EMBED Equation.3 {#})*. Для кожного заданого EMBED Equation.3 задача полягає або у знаходженні хоча б одного EMBED Equation.3 такого, що EMBED Equation.3 # EMBED Equation.3 , або у констатації, що елемента EMBED Equation.3 з такою властивістю немає:
Задано: EMBED Equation.3 .
Знайти: EMBED Equation.3 таке, що EMBED Equation.3 # EMBED Equation.3 .
Індивідуальною задачею є довільно задане слово EMBED Equation.3 , а її розв'язком е або відповідне EMBED Equation.3 , або відповідь "не існує", яку зручно кодувати символом #. Наприклад,
Задано: EMBED Equation.3 .
Знайти: EMBED Equation.3 таке, що EMBED Equation.3 .
Ми ввели три типи задач — обчислення, розпізнавання та пошуку. Насправді, в обчислювальному відношенні всі вони рівносильні між собою — кожну задачу одного типу можна переформулювати як задачу будь-якого з двох інших типів.
Так, задача розпізнавання мови EMBED Equation.3 є ні чим іншим, як задачею обчислення її характеристичної функції EMBED Equation.3 , що набуває значення 1 на аргументах з EMBED Equation.3 і лише на них. Задачу обчислення функції EMBED Equation.3 легко подати як задачу пошуку, взявши EMBED Equation.3 # EMBED Equation.3 , де EMBED Equation.3 — множина слів у алфавіті EMBED Equation.3 # EMBED Equation.3 . Нарешті, кожну задачу пошуку можна звести до деякої задачі розпізнавання .
Діофантові рівняння. Частковий та повний розв’язок.
ax + by = c ,
де a , b , c ??Z ; a і b - не нулі.
Нехай ( a , b ) = d . Тоді a = a 1 d ; b = b 1 d і рівняння виглядає так:
a 1 d· x + b 1 d· y = c , тобто d· ( a 1 x + b 1 y ) = c .
в такого рівняння є розв’язок (пари цілих чисел x і y ) тільки тоді, коли d | c . Нехай d | c . Поділимо обидві частини рівняння на d, і далі будемо вважати, що ( a , b ) = 1.
Випадок 1. Нехай c = 0, рівняння має вид ax + by = 0 - " однорідне лінійне діофантове рівняння". Тоді:
x = b / a * y
Оскільки x має бути цілим числом, то y = at , де t - довільне ціле число (параметр). Значить x = - bt і розв’язками однорідного діофантового рівняння ax + by = 0 є усі пари виду {- bt , at }, де t = 0; ±1; ±2;... Множина усіх таких пар називається загальним розв’язком лінійного однорідного діофантового рівняння, будь-яка ж конкретна пара з цієї множини називається частковим розв’язком.
Випадок 2. Нехай тепер c ??0. Цей випадок закривається наступною теоремою.
Теорема. Нехай ( a , b ) = 1, { x 0 , y 0 } - частковий розв’язок діофантового рівняння ax + by = c . Тоді його загальний розв’язок задається формулами:
EMBED Equation.2
Таким чином, в теорії лінійних діофантових рівнянь загальний розв’язок неоднорідного рівняння є сумою загального розв’язку відповідного однорідного рівняння і якогось (кожного) часткового розв’язку неоднорідного рівняння.
Як же шукати саме частковий розв’язок { x 0 , y 0 }. Ми домовилися, що ( a , b ) = 1. Це означає, що знайдуться такі u і v з Z , що au + bv = 1 (пункт 4), причому ці u і v знаходимо за допомогою алгоритму Евкліда. Помножимо тепер рівність au + bv = 1 на c і одержимо: a ( uc ) + b ( vc ) = c , тобто x 0 = uc , y 0 = vc .
Обчислення прямуючих дробів.
Проспостерігаємо за поведінкою прямуючих дробів
??1 = q 1 , ??2 = q 1 + EMBED Equation.3, ??3 = q 1 + EMBED Equation.3, ...
ланцюгового дробу
EMBED Equation.3
з метою навчитися швидко їх обчислювати без перетворення багатоповерхових виразів.
Прямуючий дріб ??s , s > 1, одержуємо із дробу ??s -1 заміною в записі виразу ??s -1 букви q s -1 виразом q s -1 + 1/ q s . Ми вже знаємо з пункту 7, що якщо "багатоповерховий" прямуючий дріб спростити (порахувати), то вийде деяке раціональне число P/Q - "одноповерховий" дріб. Домовимося завжди буквою Ps позначати чисельник придатної дробу ??s (чисельник його раціонального значення, тобто "одноповерхового" дробу), а буквою Q s - знаменник.
Приймемо для зручності P 0 = 1, Q 0 = 0. (Це просто угода, на нуль ділити не потрібно.) Маємо:
EMBED Equation.3
EMBED Equation.3, тобто P 1 = q 1 , Q 1 = 1,
EMBED Equation.3,
EMBED Equation.3 і т.д.
Видно, що виходять рекурентні співвідношення:
P s = q s P s -1 + P s -2 - чисельники
Q s = q s Q s -1 + Q s -2 - знаменники
Ці співвідношення разом з початковими умовами P 0 = 1, Q 0 = 0, P 1 = q 1 , Q 1 = 1 значно прискорюють процес обчислення прямуючих дробів. Самі співвідношення дуже легко довести, якщо скористатися принципом математичної індукції.
Приклад. Згадаємо розклад в ланцюговий дріб числа 105/38 і обчислимо прямуючі дроби. Маємо:
EMBED Equation.3
Обчислення чисельників і знаменників прямуючих дробів зводимо в таблицю:
Другий рядок цієї таблиці - неповні частки - заповнюється відразу після роботи алгоритму Евкліда, числа P0 = 1, Q0 = 0, P1 = q1 , Q1 = 1 проставляються в таблицю автоматично. Два останні рядки заповнюються зліва направо з використанням рекурентних співвідношень. Наприклад, число 11 = P3 у третьому рядку виникло так: трійка, що стоїть над ним, помножилася на трійку, що стоїть перед ним, і до результату додалася двійка спереду, отже P3=q3P2+P1=3?3+2. Після того, як у таблиці вже є число 11, наступна клітинка в цьому рядку заповнюється числом 4 · 11 + 3 = 47, і т.д. Погодьтеся, що цей процес набагато швидший за розкручування багатоповерхових дробів. Відповідь:
??0 = ??; ??1 = 2; ??2 = 3; ??3 = EMBED Equation.3=2,75,
EMBED Equation.3 EMBED Equation.3
- на п'ятому кроці (починаючи з нуля) прямуючі дроби підійшли до самого числа, стрибаючи довкола нього, причому дроби з парними номерами більші за початкове число, а з непарними - менші, і послідовність прямуючих дробів дуже швидко сходиться до самого числа. Це, звичайно, не випадково, але про ці властивості трохи нижче.
Порахуємо прямуючі дроби розкладу ??2 у ланцюговий дріб з прикладу 1 попереднього пункту. Складемо таблицю:
Уже на шостому кроці одержали дріб 99/70 = 1,41428..., тобто досягнена дуже висока точність. Знадобилося для цього лише кілька хвилин, що показує ефективність ланцюгових дробів.
Теорема Ейлера. Застосування???.
Нехай m>1, (a,m)=1, ?(m) – функція Ейлера. Тоді:
a?(m) ??1(mod m).
Доказ. Нехай х набуває значення із зведеної системи лишків за mod m:
x=r1,r2,...,rc
де c=?(m) їх кількість, r1,r2,..., rc - найменші невід’ємні лишки за mod m. Отже, найменші невід’ємні лишки, що відповідають числам ax є відповідно:
??1 , ??2 ,..., ??c
– теж набувають значень із зведеної системи лишків, але в іншому порядку (див. Лему 2 з пункту 17). Значить:
a ??r1 ?????(mod m)
a ??r2 ?????(mod m)
...
a ??rc ?????(mod m)
Перемножимо ці с порівнянь. Вийде:
ac r1 r2 ...rc ??j 1 ?j 2 ... ?j c (mod m)
Оскільки r1 r2 ...rc = ?1 ?2 ... ?c ??0 і взаємно просте з модулем m, то, поділивши останнє порівняння на r1 r2 ...rc, одержимо a?(m) ??1(mod m).
Теорема Ферма. Застосування.
Нехай р – просте число, р не ділить a. Тоді:
ap-1 ??1(mod p) .
Доказ 1. Нехай в умові теореми Ейлера m=p, тоді ?(m)=p-1 (див. пункт 14 ). Одержуємо ap-1 ??1(mod p).
Необхідно відзначити важливість умови взаємної простоти модуля і числа a у формулюваннях теорем Ейлера і Ферма. Простий приклад: порівняння 62 ??1(mod 3) очевидно не виконується. Однак можна легко підправити формулювання теореми Ферма, щоб зняти обмеження взаємної простоти.
Наслідок 1. Без всяких обмежень на a ??Z,
ap ??a(mod p) .
Доказ. Помножимо обидві частини порівняння ap-1 ??1(mod p) на a. Зрозуміло, що вийде порівняння, справедливе і при a, кратному р.
Звичайно, доказ 1 теореми Ферма вийшов настільки коротким завдяки проведеній могутній попередній підготовці (доведена теорема Ейлера і вивчені властивості функції ?(m)). Наведемо ще один варіант доказу теореми Ферма.
Доказ 2. Оскільки р - просте число, то всі біноміальні коефіцієнти (крім C0p і Cpp) діляться на р, тому що чисельник виписаного виразу містить р, а знаменник не містить цього множника. Якщо згадати біном Ньютона, то стає зрозуміло, що різниця (A+B)p-Ap -Bp= =Cp1Ap-1B1+Cp2Ap-2B2+...+Cpp-2A2Bp-2+Cpp-1A1Bp-1, де А і В – довільні цілі числа, завжди ділиться на р. Послідовним застосуванням цього спостереження одержуємо, що (A+B+C)p--Ap-Bp-Cp={[(A+B)+C]p-(A+B)p-Cp}+(A+B)p -Ap -Bp завжди ділиться на р; (A+B+C+D)p-Ap–Bp -Cp-Dp завжди ділиться на р; і взагалі, (A+B+C+...+K)p -Ap-Bp-Cp-...-Kp завжди ділиться на р. Нехай A=B=C=...=K=1 і візьмемо кількість цих чисел рівним a. Вийде, що ap-a ділиться на р, а це і є теорема Ферма в більш загальному формулюванні.
Наслідок 2. (a+b)p ??ap +bp (mod p).
Наведемо кілька прикладів застосування теорем Ферма і Ейлера. Зазначимо, що ефективність застосування теорем Ферма і Ейлера ґрунтується на тому, що порівняння, що даються цими теоремами, зручно підносити до степеня, оскільки справа у них стоїть одиниця, що на піднесення до степеня не реагує.
Приклад 1. Дев'ятий ступінь однозначного числа закінчується на 7. Знайти це число.
Розв’язування. a9 ??7(mod 10) – дано. Крім того, (7, 10)=1 і ( a , 10)=1. За теоремою Ейлера, a?(10) ??1(mod 10). Отже, a4 ??1(mod 10) і, після піднесення до квадрату, a8 ?1(mod 10). Поділимо почленно a9 ??7(mod 10) на a8 ??1(mod 10) і одержимо a?7(mod 10). Це означає, що a=7.
Розв’язування порівнянь першого степеня вигляду ax??b(mod m) для взаємно простих a і m.
Випадок 1. Нехай а і m взаємно прості. Тоді нескоротний дріб m/a розкладається в ланцюговий дріб:
EMBED Equation.3
Цей ланцюговий дріб, зрозуміло, скінченний, тому що m/a - раціональне число. Розглянемо два останні прямуючі дроби:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-002.gif"; EMBED Equation.3
Згадуємо (пункт 9) властивість чисельників і знаменників прямуючих дробів: mn-1-an-1=
=(-1)n. Далі (доданок mn-1, кратний m, можна викинути з лівої частини порівняння):
-an-1 ??(-1)n (mod m) тобто
an-1 ??(-1)n-1 (mod m) тобто
a[(-1)n-1 Pn-1 b] ??b(mod m)
і єдиним розв’язком вихідного порівняння є:
x ??(-1)n-1 Pn-1 b(mod m)
Випадок 2. Нехай (a,m)=d. У цьому випадку, для можливості розв'язку порівняння ax??b(mod m) необхідно, щоб d ділило b, інакше порівняння узагалі виконуватися не може. Дійсно, ax??b(mod m) буває тоді, і тільки тоді, коли ax-b ділиться на m без остачі, тобто ax-b=t · m,
t ??Z, звідки b=ax-t ??m , а права частина останньої рівності кратна d.
Нехай b=db1, a=da1, m=dm1. Тоді обидві частини порівняння xa1 d??b1 d(mod m1 d) і його модуль поділимо на d :
xa1 ??b1 (mod m1),
де вже а1 і m1 взаємно прості. Згідно випадку 1 цього пункту, таке порівняння має єдиний розв’язок x0 :
x ??x0 (mod m1 ) (*)
За вихідним модулем m, числа (*) утворять стільки розв’язків вихідного порівняння, скільки чисел виду (*) міститься в повній системі лишків: 0,1,2,..., m-2, m-1. Очевидно, що з чисел x=x0+t??m в повну систему найменших невід’ємних лишків попадають лише x0, x0+m1, x0+2m1, ..., x0+(d-1)m1, тобто усього d чисел. Значить у вихідного порівняння є d розв’язків.

Китайська теорема про лишки.
(Китайська теорема про лишки). Нехай дана найпростіша система порівнянь першого степеня:
EMBED Equation.3 (*)INCLUDEPICTURE \d \z "../pict/19-009.gif"
де m1,m2,...,mk попарно взаємно прості. Нехай, m1 m2 ...mk =Ms ms; Ms Ms????1(mod ms) (Очевидно, що таке число Ms???завжди можна підібрати хоча б за допомогою алгоритму Евкліда, оскільки (ms, Ms )=1); x0 =M1 M1??b1+M2 M2??b2 +...+Mk Mk??bk. Тоді система (*) рівносильна одному порівнянню
x ??x0 (mod m1 m2 ...mk ),
а саме набір розв’язків (*) збігається з набором розв’язків порівняння x??x0(mod m1m2 ...mk).
Доказ. Маємо: ms ділить Mj, при s?j. Отже, x0 ??Ms Ms??bs (mod ms), звідки x0??bs(mod ms). Це означає, що система (*) рівносильна системі
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-010.gif"
яка, у свою чергу, рівносильна одному порівнянню x??x0 (mod m1 m2 ...mk ).
Зведення розв’язування порівняння високого степеня до розв’язування порівняння меншого степеня.
Лема 1. Довільне порівняння f(x) ??0(mod p), де р - просте число, рівносильне деякому порівнянню степеня не вищого за p-1.
Доказ. Розділимо f(x) на многочлен xp-x ("многочлен ділення круга") із залишком: f(x)=(xp-x)??Q(x)+R(x), де, як відомо, степінь залишку R(x) не перевищує р-1. Але за теоремою Ферма, xp-x??0(mod p). Це означає, що f(x)??R(x)(mod p), а вихідне порівняння рівносильне порівнянню R(x)??0(mod p).