Q. Некоторые доказательства

Это приложение содержит некоторые доказательства для теорем, используемых в лекции 2 курса "Математика криптографии и теория шифрования" и лекции 1. Почти все они короткие и неформальные. Они рассчитаны на студентов, изучающих курс криптографии. Читатель, заинтересованный в более детальном изучении, может пополнить свои знания из книг, посвященных теории чисел.

Q.1. Лекция 2

Эта лекция содержит некоторые доказательства теорем по теории делимости, евклидовых алгоритмов и сравнений.

Теория делимости

Ниже - доказательства нескольких теорем по теории делимости.

Теорема Q.I:Уравнение деления (алгоритм)

Для целого числа a и b, где b > 0, существуют целые числа q и r, такие, что

a = q x b + r.

Доказательство:

Рассмотрим арифметическую прогрессию в форме

...,-3 x b, - 2 x b, - 1 x b , 0 x b, 1 x b, 2 xb, 3 x b, ...

Очевидно, что целое число является или равным одному из членов этой прогрессии, или находится между двумя последовательными членами. Другими словами, a = q x b + r, где q x b - член в вышеупомянутой прогрессии и r - смещение от этого члена.

Теорема Q.2. Если a|1, тогда $$a = \pm 1$$.

Доказательство:

a|1 ->.1 = a x x, где x - целое число.

Это означает: ( x = 1 и a = 1 ) или ( x = -1 и a = -1 ).

Поэтому: $$a = \pm l$$.

Теорема Q.3.Если a|b и b|a, тогда $$a= \pm b$$.

Доказательство:

a | b -> b = x x a, где x - целое число.

b |a -> = y x b, где y - целое число.

Мы имеем a =y x (x x a) = (y x x) x a. -> y x x = 1.

Это означает: ( x = 1 и y = 1 ) или ( x = -1 и y = -I ).

Поэтому: $$a = y\ \times \ b \to \pm b$$.

Теорема Q.4. Если a|b и b|c, тогда a|c.

Доказательство:

a | b -> b= x x a, где X - целое число.

b| c -> c = y x b, где y -целое число.

Мы имеем c = y x (x x a) = (y x x ) x a.

Поэтому a | c.

Теорема Q.5.Если a|b и a|c, тогда a|(b + c).

Доказательство:

a | b -> b = x x a, где x - целое число.

a | c -> c = y x a, где y - целое число.

Мы имеем b + c = (x + y) x a.

Поэтому a| (b + c).

Теорема Q.6. Если a |b и a | c, тогда a |(m x b + n x c), где m и n - произвольные целые числа.

Доказательство:

a |b -> b = x x a, где x - целое число.

a |c -> c = y x a, где y - целое число.

Мы имеем (m x b + n x c) = m x (x x a) +n x x (y x a)= (m x x + n xy) x a.

Поэтому a |(m x b + n x c).

Евклидовы алгоритмы

Мы использовали евклидов и расширенный евклидов алгоритмы в лекции 2. Ниже даны доказательства двух теорем, связанных с этими алгоритмами.

Теорема Q.7.Если a = b x q + r ( r - остаток от деления a на b ), то НОД (a, b) = НОД (b, r).

Доказательство

Предположим, что E - набор всех общих делителей a и b. Каждый элемент E делит a и b, поэтому он делит r = a - b x q. Это означает, что E - набор всех общих делителей a, b, и r.

Предположим, что F - набор всех общих делителей b и r. Каждый элемент F делит b и r ; поэтому делит a = b x q + r. Это означает, что F - набор всех общих делителей a, b и r.

Это означает, что E = F -> a, b и r имеют одинаковый набор общих делителей. Поэтому НОД (a, b) == НОД (b, r).

Как мы видели в лекции 2, эта теорема - основание евклидового алгоритма для нахождения наибольшего общего делителя двух целых чисел.

Теорема Q.8.Если a и b - целые числа и оба не равны нулю, то существуют целые числа x и y, такие, что НОД (a, b) = x x a + y x b.

Доказательство:

Предположим, что D - набор всех значений (x x a +y x b), а d есть наименьшее значение отличное от нуля.

Мы можем записать a= q x d + r -> r= a - q x d=(1 - q x x)a + (-q x y) b, где 0 <= r <= d.

Это подразумевает, что r входит в D. Но поскольку r < d, то или r = 0, или d | a.

Подобным путем мы можем показать, что d | b.

Поэтому d - общий делитель a и b.

Любой другой делитель a и b делит d = x x a+ y x b. Поэтому d должен быть НОД (a,b).

Как мы видели в лекции 2, эта теорема - основание расширенного евклидового алгоритма.

Сравнение

Ниже даются доказательства некоторых теорем о сравнении, используемые в лекции 2.

Теорема Q.9.Если a, b и n - целые числа и n > 0, то $$a \equiv b\ (mod\ n)$$, тогда и только тогда, когда существует целое число q, такое, что q x n + b.

Доказательство:

Если $$a \equiv b\ (mod\ n)$$, то n | (a - b), это означает, что есть целое число q, такое, что a - b = q x n.

Поэтому мы имеем a = q x n + b.

Если есть целое число q, такое, что a = q x n + b, тогда a - b = q x n, что означает n |(a - b).

Поэтому мы имеем $$a \equiv b\ (mod\ n)$$.

Теорема Q.10.Если a, b, c и n - целые числа при n > 0, такие, что $$a \equiv b\ (mod\ n)$$, то

Доказательство: Обратите внимание, что $$a \equiv (mod\ n) \to n | (a - b)$$.

Теорема Q.11.Если a, b, c, d и n - целые числа при n > 0, такие, что $$a \equiv b (mod\ n)$$ и $$c \equiv d (mod\ n)$$, то

Доказательство:

Обратите внимание, что $$a\ \equiv \ b mod n \to (a - b) \to (a-b) =k x n$$ ; $$c \equiv d (mod\ n) \to (c - d) = l x n$$

Q.2. Лекция 9

В этом разделе приводятся некоторые доказательства теорем, используемых в лекции 1. Мы не будем приводить длинных доказательств, таких как доказательство китайской теоремы об остатках, - интересующимся студентам рекомендуем посмотреть книги по теории чисел.

Простые числа

Мы докажем только одну теорему о простых числах.

Теорема Q.I2.Если n - составной объект, то есть простой делитель p, такой, что $$p \le \surd n$$.

Доказательство:

Поскольку n - составной объект, n =a x b.

Если p - наименьший простой делитель n, тогда p <= a и p <= b.

Поэтому $$p^{2} < n \to p \le \surd n$$

Эта теорема используется в решете Эратосфена, чтобы найти все простые сомножители n.

Phi-функция Эйлера

Ниже приводятся три доказательства, связанные с phi-функцией Эйлера.

Теорема Q.I3.Если p - простое число, тогда $$\varphi (p)= p - 1$$.

Доказательство:

Поскольку p - простое число, все целые числа, меньшие, чем p, взаимно простые по отношению к p.

Поэтому $$\varphi (p)= p - 1$$.

Эта теорема - часть phi-функции Эйлера.

Теорема Q.14.Если p - простое число и e - положительное целое число, тогда $$\varphi (p) =p^{e }- p^{e-1}$$

Доказательство:

Целые числа, которые не являются взаимно простыми с pe - (1 x p ), (2 x p). .., ( pe-1 x p). Все они целые числа и имеют общий делитель p с pe. Общее количество этих целых чисел - pe-1. Остальная часть целых чисел является взаимно простой с pe.

Поэтому $$\varphi (p) =p^{e }- p^{e-1}$$

Теорема Q.15.Если n - составной объект с разложением на простые множители Пpei, то $$\varphi (n) = П(p^{ei} - p^{ei-1})$$

Доказательство:

Доказательство базируется на факте, что $$\varphi (m \times n) = \varphi (m) \times \varphi ( n)$$ - мультипликативная функция, в которой m и n являются взаимно простыми. Поскольку элементы в разложении n на простые множители взаимно простые, $$\varphi (Пp_{i}^{ei}) = П\varphi (p_{i}^{ei})$$.

Поэтому $$\varphi (n) = П(p^{ei} - p^{ei-1})$$

Эта теорема - обобщение phi-функции Эйлера.

Малая теорема Ферма

Ниже приводятся две теоремы, которые относятся к малой теореме Ферма.

Теорема Q.I6.Если положительное целое число, взаимно простое c p, то $$a^{p-1} \equiv 1 (mod\ p)$$.

Эта теорема - первая версия Малой теоремы Ферма.

Доказательство:

Может быть доказано, что вычеты элементов a, 2a, .., (p -1) a по модулю p равны 1,2..., (p - 1), но не обязательно в том же самом порядке,

В результате a x 2a x o o o (p - l) равно [(p - 1)]! ap-1

В результате 1 x 2 x o - o x (p - 1) равно [(p - 1)]!

Это означает $$[(p-1)]! a^{p-1}\equiv [(p - l)]! (mod\ p)$$,

Сокразая обе стороны тождества на (p - 1)!, мы получаем $$a^{p-1} \equiv 1(mod\ p)$$.

Теорема Q.I7.Если p - простое число и а - положительное целое число, то $$a^{p} \equiv a (mod\ p)$$.

Эта теорема - вторая версия теоремы Ферма.

Доказательство:

Если a и p взаимно-простые, используя результат предыдущей теоремы, мы умножаем обе стороны сравнения, чтобы получить $$a^{p} \equiv a (mod\ p)$$.

Если p|a, то $$a^{p }\equiv a \equiv 0 (mod\ p)$$.

Теорема Эйлера

Ниже приводится доказательство одной теоремы, связанной с первой версией теоремы Эйлера. Вторую версию мы доказали в лекции 1.

Теорема Q.18.Если n и a являются взаимно-простыми, то $$a \varphi (n) \equiv 1 (mod\ n)$$.

Доказательство:

Предположим, что элементы в $$Z n* - r_{1}, r _{2,}.., r_{\varphi (n)}$$

Мы создаем другой набор $$ar_{1}, ar _{2,}.., ar, a^{\varphi (n)}$$ умножая каждый элемент в Z n * на a. Может быть доказано, что каждый элемент в этом новом наборе является конгруэнтным элементу в Zn* (не обязательно в том же самом порядке).

Таким образом, $$ar_{1}, ar _{2,}.., ar, ar^{\varphi (n)} \equiv r_{1}, r _{2,}.., r^{\varphi (n)} (mod\ n)$$

Мы имеем $$a^{\varphi (n)} [r_{1} x r _{2,} x.. x r_{\varphi (n)}] \equiv r_{1} x r _{2,} x\dots x r_{\varphi (n)}] (mod\ n)$$

.

Основная теорема арифметики

Ниже приводится частичное доказательство основной теоремы арифметики.

Теорема Q.19

Основная теорема Арифметики

Ниже приводится частичное доказательство Основной теоремы Арифметики.

Теорема Q.19

Любое положительное целое число n больше чем 1 может быть представлено, как произведение простых чисел.

Доказательство:

Мы используем индукцию. Первое утверждение (база индукции) n = 2, является простым числом. Предположим, что все положительные целые числа меньше, чем n может быть представлены как произведение простых чисел. Мы докажем, что n может также быть представлено как произведение простых чисел.

Может иметь два случая: n - простое число, или n - составной объект.

Эта теорема - частичное доказательство основной теоремы арифметики. Чтобы полностью доказать эту теорему, мы должны показать, что это произведение уникально. Но мы рекомендуем посмотреть полное доказательство в книгах по теории чисел.