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

1. Достаточно заметить, что а = а×1

2. По условию, найдутся такие d₁ и d₂ что а = bd₁ и b = cd₂. Но тогда а = cd₁d₂, т. е. ас.

3. Мы имеем а = bc₁ и b = ас₂, откуда следует, что а = ас₁с₂, т. е. c₁c₂ = 1. Так как числа с₁ и с₂ по условию целые, то либо c₁ = с₂ = 1, либо c₁ = с₂ = -1. В первом из этих случаев а = b, а во втором а = -b.

4. Пусть а = bс. Если |c| ≥ 1, то поскольку |b| > |а|, должно быть и |bc| > |a|, что, однако, противоречит предположенному. Значит, |с| < 1, а так как по условию число с целое, должно быть c = О, а потому и а = 0.

5. Очевидно, из а = bс следует |а| = |b||с|, а из |a| = |b||c| следует а = bс или а = b(-с), причем числа с, -с и |с| целые или нет одновременно.

6. В самом деле, пусть

где все числа с₁, с₂, ..., с_n - целые. Сложив все эти равенства почленно, мы получим

В скобках стоит целое число, что и доказывает требуемое.

8. Доказательство ведется от противного. Предположим, что простых чисел конечное число, так что все они могут быть выписаны:

Произведение всех этих чисел обозначим через Р и рассмотрим разность Р - 1. Эта разность больше каждого из простых чисел, перечисленных в списке (Д.1), и потому не может быть простым числом. Следовательно, она делится хотя бы на одно простое число p_k. Но Р также делится на p_k. Следовательно, на основании следствия теоремы 6, должно быть и 1 p_k, откуда следует, что p_k = 1, а это противоречит простоте числа p_k (см. стр. 21).

Приведенное доказательство бесконечности множества простых чисел было найдено Евклидом (IV век до н. э.).

9. Если числа аир взаимно просты, то теорема доказана. Если же эти числа не взаимно просты, то оба они делятся на одно и то же число, отличное от единицы. Ввиду простоты р таким числом может быть только само р. Значит, в этом случае a p, а это и требовалось.

10. Разделив М на m с остатком, получим

где 0 г <т. Так как Мит делятся на а и Ь, по следствию теоремы б, число г также должно делиться и на а, и на Ь и тем самым быть общим кратным этих чисел. Но г ><т, а т есть наименьшее положительное общее кратное а и Ь. Значит, г не может являться положительным числом, так что г =. 0. Поэтому М; т. >11. Пусть числа а и b взаимно просты, и m - их наименьшее общее кратное. Так как aba и abb по предыдущей теореме abm. Пусть ab = mk. Положим m = ас. Тогда ab - ack, т. е. b = ck, так что bk. Точно так же убеждаемся в том, что и аk Так как числа а и b по условию взаимно простые, должно быть k = 1, а это и означает, что m = ab.

12. Обозначим через m наименьшее общее кратное чисел b и с. По предыдущей теореме m = bс. Далее, по условию abс, кроме того, очевидно, аbb. Значит, по теореме 10, abbc, т. е. ab = bck или, после сокращения на b, а = ck, а это и требовалось.

13. Доказательство ведется индукцией по числу сомножителей. Если сомножитель один, то теорема тривиальна. Предположим, что теорема доказана для любого произведения n сомножителей. Пусть (a₁a₂...a_na_n+1p. Обозначим a₁a₂....a_n через А. Тогда Аa_n+1p. Если a_n+1p, то теорема доказана, а если нет, то по теореме 9 числа а_n+1 и р взаимно просты. Но тогда по предыдущему Ар. Так как А есть произведение n сомножителей, по индуктивному предположению один из них должен делиться на р. Теорема доказана.

Следствие. Вся дробь представляет собой целое число, т. е. ее числитель делится на знаменатель. Будем считать, что числитель является произведением двух сомножителей: р и 1⋅2 ... (р - 1 ) = (р-1)!

Ни один из сомножителей знаменателя дроби не делится на р. Следовательно, по предыдущей теореме, на р не делится и весь знаменатель. Но тогда на основании теоремы 9 он взаимно прост с р. Поэтому на знаменатель должен делиться второй сомножитель числителя. Обозначая частное от этого деления через q, мы имеем С^k_р = pq, и требуемое доказано.

14. Сначала докажем возможность разложения любого числа, отличного от единицы, на простые множители. Предположим, что все числа, меньшие N, могут быть так разложены. Если число N простое, то оно автоматически разлагается в произведение простых (именно, в произведение, состоящее только из одного сомножителя - самого числа N), и теорема доказана. Пусть теперь N составное, N₁- некоторый делитель N, отличный как от N, так и от единицы, и N₂ - частное от деления N на N₁. Тогда N = N₁N₂, причем, как легко проверить, 1 < N₂ < N. Так как N₁ и N₂ меньше N, то, по предположению, они разлагаются в произведения простых множителей. Пусть N₁ = p₁p₂ ... p_k и N₂ = q₁q₂ ... q_l - эти разложения. Тогда р₁р₂ ... p_kq₁q₂ ... q_l является искомым разложением числа N. Возможность разложения, таким образом, доказана.

Переходим к доказательству единственности разложения. Пусть нам даны два разложения числам на простые множители: р₁р₂ ... p_k и q₁q₂ ... q_l. Очевидно,

Так как q₁q₂ ... q_l делится на р₁ то по предыдущей теореме хотя бы одно из чисел q₁, q₂,....., q_l делится на р₁. Пусть q₁р₁ (то, что мы считаем именно первый сомножитель в (Д.2) справа делящимся на р₁ никакого дополнительного предположения не означает, так как мы вправе переставлять сомножители местами и обозначить через q₁ именно тот из них, который делится на р₁). Так как число q₁ простое, это возможно лишь при р₁ - q₁. Сокращая равенство (Д.2) на р₁ получаем

Аналогично предыдущему убеждаемся в том, что не которое из чисел q₂, q₃,...,q_l (например, q₂) делится на р₂, и потому р₂ = q₂. Сокращая равенство (Д.З) на р₂, мы уменьшаем число сомножителей в его частях еще на единицу. Такой процесс сокращения, очевидно, можно продолжать до тех пор, пока мы не сократим одно из произведений полностью. Пусть первым сократится произведение, состоящее в (Д.2) слева. Произведение, стоящее в (Д.2) справа, тоже должно при этом сократиться нацело, так как в противном случае мы получили бы равенство вида

которое невозможно, так как единица не делится ни на какое простое число. При этом мы получаем также, что

Теорема полностью доказана.

15. Пусть

и

соответственно канонические разложения чисел а и b, a d - некоторый общий делитель этих чисел. Если d ≠ 1, то d делится на некоторое простое число р. Тогда по теореме 3 а р и b р, так что р находится как среди чисел р₁, р₂, ...., p_k, так и среди чисел q₁, q₂, ..., q_l. Поэтому среди простых чисел, входящих в каноническое разложение а, существует хотя бы одно, входящее в каноническое разложение b.

Наоборот, если а и b взаимно просты и р входит в каноническое разложение а, то b не делится на р, так что р не может входить в каноническое разложение b.

16. Необходимость. Так как

(i = 1, 2, ..., k), мы из b a получаем требуемое простой ссылкой на теорему 2.

Достаточность доказывается по индукции. Делимость b p₁^α₁ мы имеем в числе условий. Предположим, что нами уже установлено, что

Кроме того, в нашем распоряжении имеется делимость bpαl+1l+1 . Так как числа pα11.....pαll и pαl+1l+1 по предыдущей теореме взаимно просты, мы можем применить следствие теоремы 11, которое дает нам

Этим индуктивный переход обоснован.

17. Необходимость. Пусть а b. Из теоремы 13 следует, что каждый простой делитель b является простым делителем а. Таким образом, b имеет вид

где 0 ≤ β₁, 0 ≤ ₂, ...., 0 ≤ _k. Предположим, что β₁ > α₁. Так как

- целое число, числитель последней дроби должен делиться на знаменатель и тем более на число р₁^β₁-α₁. Но тогда по теореме 13 на р₁ должно делиться хотя бы одно из чисел р₂, ..., p_k, чего не может быть. Значит, β₁ ≤ α₁. Так как нумерация простых делителей а для нас безразлична, мы тем самым доказали, что и β₂ ≤ α₂,...., β_k ≤ α_k. Необходимость доказана.

Для доказательства достаточности заметим, что если b имеет указанный вид, то

18. Напишем канонические разложения чисел m

Отберем среди простых р₁,...,p_n те, которые делят t, т. е. содержатся среди q₁,....,q_l. Пусть для определенности это будут p₁,...,p_r равные соответственно числам q₁,.....,q_r. Положим тогда

Согласно теореме 15 будет (m₁,t) = 1. Кроме того, возьмем натуральное число k, которое было бы не меньше каждого из отношений

Это значит, что kβ_i ≥ α_i для i = 1,...., r, откуда согласно теореме 17 t^km₂.

19. Необходимость. Пусть

Ввиду равно-остаточности a и b должно быть r₁ = r₂.

Значит,

т. е. (а - b)m.

Достаточность. Пусть (а - b)m. Разделов a и b на m с остатком, мы получим (Д.4) и (Д.5). При этом

т. е.

По теореме 6 (r₁ - r₂)m. Но |r₁ - r₂| < m. Значит, по теореме 4 r₁ - r₂ = 0 или r₁ = r₂, а это и требовалось.

20. Из условия на основании теоремы 16 мы имеем

Сложив почленно эти равенства, мы после простых преобразований получаем

что по теореме 19 и означает равно-остаточность сумм.

Для доказательства равно-остаточности произведений отметим следующее тождество:

Из него следует, что произведение двух чисел вида а + bm снова является числом того же вида. Поэтому, рассуждая по индукции, мы убеждаемся в том, что произведение любого количества чисел вида а + bm есть число этого же вида.

Перемножив теперь почленно все равенства (Д.6) и применив к правой части только что проведенные рассуждения, мы получаем

где t - некоторое целое число. Равно-остаточность произведений, таким образом, доказана.

21. Необходимость. Если описанный алгорифм является признаком равно-остаточности при делении на т, то числа А и b при делении на m должны быть равно-остаточными. В частности, это будет так, если A = t^k + b. Но это значит, что A - b = t^km.

Достаточность. В наших обозначениях A - b = at^k, т. е. числа А и b равно-остаточны при делении на m. Если t^km, то по следствию теоремы 17 они равно-остаточны и при делении на m. Поэтому конструируемая алгорифмом в этом случае последовательность A₀, A₁ ... состоит из равно-остаточных при делении на m чисел. Следовательно, процесс построения этой последовательности является признаком равно-остаточности при делении на m.

22. Необходимость. Если описанный алгорифм действительно является признаком равно-остаточности при делении на m, то он, в частности, должен быть применим и к числу A = t^k + а₀. Здесь f(A) = а₀ + 1, и равно-остаточность чисел A и f(A) при делении на m означает (t^k - 1)m.

Достаточность. Пусть А ≥ t^k. Тогда из определения функции f следует, что

Здесь каждое слагаемое (см., например, задачу 22, п. д)) делится на t^k - 1. Значит, если (t^k- 1)m, то и (А - f(A))m. Равно-остаточность остальных членов последовательности (3.4), а также ее членов, если она начинается с числа А < t^k, вытекает из ее построения.

23. Необходимость. В случае А = t^k + a₀ равно-остаточность чисел А и f(A)= a₀ - 1 при делении на m дает нам (t^k + 1)m.

Достаточность. Мы имеем в нашем случае при А ≥ t^k

(знак "плюс" стоит здесь в члене, соответствующем нечетному коэффициенту при k в показателе, а знак "минус" - в члене, соответствующем четному коэффициенту). Согласно пп. д) и е) задачи 22 при нечетном r выражение t^kr + 1 делится на t^k + 1, а при четном r выражение t^kr - 1 делится на t^k - 1. Значит, если (t^k - 1)m, то на m делится каждый член в (Д.7) справа, а потому и вся разность А - f(A). Тем самым числа А и f(A) оказываются равно-остаточными при делении на т. Равно-остаточность остальных членов последовательности (3.4), а также членов этой последовательности, если она начинается с числа А < t^k, вытекает непосредственно из ее построения.

24. Доказательство ведется индукцией по а. При а = 1 имеем

и 0р.

Предположим, что а^р - а делится на р, и докажем, что (а+1)^р - (а+1) также делится на р.

Действительно, разлагая (а + 1)^р по формуле бинома Ньютона, имеем

а^р - а делится на р по предположению. По следствию теоремы 13 C^k_p (при 1 ≤ k ≤ р - 1) также делится на р. Следовательно, на р делится каждое слагаемое правой части соотношения (Д.8), а потому (теорема 6) и вся сумма.

Индуктивный переход обоснован, и вся теорема доказана.

Следствие. По теореме Ферма

а^р - а = а(а^р-1 - 1 )р.

Если при этом а не делится на р, то по теореме 13 на р должно делиться а^р-1 - 1.

25. Пусть

По теореме 15 каждое из чисел р₁ ..., p_k отлично от каждого из чисел q₁, ..., q_l Значит, каноническим

разложением m₁m₂ будет p₁^α₁....p_k^α_kq₁^β₁.......q_l^β_l. Поэтому

т. е.

26. Докажем сначала индукцией по α, что а^pα-1(p-1) - 1 делится на р^α. При α = 1 доказываемое утверждение является, очевидно, следствием теоремы Ферма, справедливость которого уже была установлена. Таким образом, основание индукции доказано.

Предположим теперь, что

и рассмотрим выражение

Мы должны доказать, что оно делится на р^α+1. Но

Так как а^pα-1(p-1) - 1, по предположению, делится на р^α, число а^pα-1(p-1) имеет вид Np^α + 1. Значит,

т. е. по формуле бинома

В последней сумме первое слагаемое делится на p^α+1, так как оно делится на р^αp и αр ≥ α + 1. В каждое из следующих р - 1 слагаемых этой суммы входит р с показателем, не меньшим α, и, кроме того, биномиальный коэффициент, в силу следствия теоремы 13 делящийся на р. Значит, каждое из этих слагаемые также делится на p^α+1. Наконец, разность 1 - 1 = 0 может быть отброшена. Поэтому по теореме 6

Случай, когда число m имеет только один простой делитель, таким образом, разобран.

Предположим теперь, что теорема Эйлера доказана для показателей m₁ и m₂, причем числа m₁ и m₂ взаимно простые. Докажем теорему Эйлера для показателя m = m₁m₂. Если потом положить

то мы, очевидно, и получим индуктивный переход, необходимый нам для завершения доказательства теоремы. Итак, доказываем высказанное утверждение.

Пусть числа а и m взаимно просты. Тогда а также взаимно просто с m₁. Значит, и a^φ(m₂) взаимно просто с m₁. Поэтому, по предположению,

делится на m₁. Точно так же убеждаемся в том, что a^φ(m) - 1 делится и на m₂. А так как числа m₁ и m₂ взаимно простые, а^φ(m) - 1 делится и на их произведение, т. е. на m. Теорема Эйлера доказана.

27. Пусть

Тогда

На основании теоремы Эйлера и теоремы 20 число a^φ(m)q₁a^r равно-остаточно при делении на m с числом a^r. Аналогично устанавливается равноостаточность при этом делении чисел a^k₂ и a^r. Значит, и числа a^k₁ и а^k₂ при делении на m равно-остаточны.

28. Найдем сначала хотя бы одно решение (х',y') этого уравнения. Очевидно, что для этого достаточно найти такое число х', что (ах' - с)b. По теореме Эйлера (а^φ(b)-1)b. Значит, (са^φ(b) - с)b, и в качестве х' можно взять число сa^φ(b)-1

Пусть теперь (x",y")-какое-то другое решение уравнения ах + by - с. Покажем, что числа х' и х" равно-остаточны при делении на b. В самом деле, пусть

Вычитая почленно второе равенство из первого, получаем

откуда а(х' - х")b. Так как а и b по условию взаимно просты, по теореме 12 (х' - х")b, и нам остается сослаться на теорему 19.

Таким образом, все искомые значения х находятся среди чисел

Но (ax_t - с)b, так что, полагая

мы получаем, что все пары чисел x_t и y_t являются решениями нашего уравнения.

29. Ввиду взаимной простоты m и 10, числа 10а + b и (10а + b) по теореме 15 равноделимы на m. Но

так что по теореме Эйлера и теореме 20 число 10a + b равноделимо на m с числом a + kb.