Решение сравнений и их приложения.

Решение сравнений и их приложения.

Содержание.

Введение

Глава1. Общие вопросы теории сравнений

§1. Сравнение по модулю

§2. Свойства сравнений

1. Свойства сравнений, не зависящие от модуля
2. Свойства сравнений, зависящие от модуля

§3. Система вычетов

1. Полная система вычетов
2. Приведённая система вычетов

§4. Теорема Эйлера и Ферма

1. Функция Эйлера
2. Теорема Эйлера и Ферма

Глава2. Теория сравнений с переменной

§1. Основные понятия, связанные с решением сравнений

1. Корни сравнений
2. Равносильность сравнений
3. Теорема Вильсона

§2. Сравнения первой степени и их решения

1. Метод подбора
2. Способы Эйлера
3. Метод алгоритма Евклида
4. Метод цепных дробей

§3. Системы сравнений 1-ой степени с одним неизвестным

§4. Деление сравнений высших степеней

§5. Первообразные корни и индексы

1. Порядок класса вычетов
2. Первообразные корни по простому модулю
3. Индексы по простому модулю

Глава3. Приложение теории сравнений

§1. Признаки делимости

§2. Проверка результатов арифметических действий

§3. Обращение обыкновенной дроби в конечную

десятичную систематическую дробь

Заключение

Литература

Введение

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

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

Слово «модуль» происходит от латинского modulus, что по–русски означает «мера», «величина».

Утверждение «а сравнимо с b по модулю m» обычно записывают в виде ab (mod m) и называют сравнением.

Определение сравнения было сформулировано в книге К. Гаусса «Арифметические исследования». Эту работу, написанную на латинском языке начали печатать в 1797 году, но книга вышла в свет лишь 1801 году из-за того, что процесс книгопечатания в то время был чрезвычайно трудоёмким  и длительным. Первый раздел книги Гаусса так и называется: «О сравнении чисел вообще».

Сравнениями очень удобно пользоваться в тех случаях, когда достаточно знать в каких – либо исследованиях числа с точностью до кратных некоторого числа.

Например, если нас интересует, на какую цифру оканчивается куб целого  числа a, то нам достаточно знать  a лишь с точностью до кратных чисел 10 и можно пользоваться сравнениями по модулю 10.

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

Дипломная работа состоит из трёх глав, причём каждая глава разбита на параграфы, а параграфы на пункты.

В первой главе изложены общие вопросы теории сравнений. Здесь рассматриваются понятие сравнения по модулю, свойства сравнений, полная и приведённая система вычетов, функция Эйлера, теорема Эйлера и Ферма.

Вторая глава посвящена теории сравнений с неизвестной. В ней излагаются основные понятия, связанные с решением сравнений, рассматриваются способы решения сравнений первой степени ( метод подбора, способ Эйлера, метод алгоритма Евклида, метод цепных дробей, с помощью индексов), систем сравнений первой степени с одной неизвестной, сравнений высших степеней и др.

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

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

Глава1. Общие вопросы теории сравнений

§1. Сравнение по модулю

Пусть z-кольцо целых чисел, m-фиксированное целое число и m·z-множество всех целых чисел, кратных m.

Определение 1. Два целых числа a и b называют сравнимыми по модулю m, если m делит a-b.

Если числа a и b сравнимы по модулю m, то пишут ab (mod m).

Условие ab (mod m) означает, что a-b делится на m.

ab (mod m)↔(a-b)m

Определим, что отношение сравнимости по модулю m совпадает с отношением сравнимости по модулю (-m) (делимость на m равносильно делимости на –m). Поэтому, не теряя общности, можно считать, что m>0.

Примеры.

1. m=3; 8 5(mod 3), так как 8-5=3 и 3 делится на 3
2. m=5; 12 (mod 5), так как 12-2=10 и 10 делится на 5
3. m=2; 3 7(mod 2), так как 3-7=-4 и -4 делится на 2
4. m=5; 11 (mod 5), так как 11-3=8, а 8 не делится на 5

Теорема. (признак сравнимости дух чисел по модулю m): Два целых числа a и b сравнимы по модулю m тогда и только тогда, когда a и b имеют одинаковые остатки при делении на m.

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

Пусть остатки при делении a и b на m равны, то есть a=mq₁+r,           (1)

                                                                                                    b=mq₂+r,          (2)

 где 0≤r≥m.

Вычтем (2) из (1), получим a-b= m(q₁- q₂), то есть a-b m или ab (mod m).

Обратно, пусть ab (mod m). Это означает, что a-b m или a-b=mt, tz  (3)

Разделим b на m; получим b=mq+r в (3), будем иметь a=m(q+t)+r, то есть при делении a на m получается тот же остаток, что и при делении b на m.

Примеры.

1. Имеем -523(mod 4), так как при делении с остатком на 4 числа -5 и 23 имеют одинаковые остатки

-5=4·(-2)+3

23=4·5+3

2. Числа 24 и 10 не сравнимы по модулю 3: 2410(mod 3), поскольку при делении с остатком на 3 они дают разные остатки.

24=3·8+0

10=3·3+1

Определение 2. Два или несколько чисел, дающие при делении на m одинаковые остатки, называются равноостаточным или сравнимыми по модулю m.

Отметим далее несколько часто используемых фактов:

1. Если два целых числа a и b сравнимы по модулю m, то это можно записать различными способами : ab (mod m) или a=b+mt (где t-целое число), или a-b=mt, или (a-b) m.
2. Если a, то и a-0m или a0(mod m), то есть всякое число, кратное m, сравнимо с нулём по модулю m.
3. Любые два целых числа сравнимы по модулю 1, то есть ab (mod 1) или (a-b) 1.
4. Если a=mq+r, то есть a при делении на m даёт остаток r, то a-r=mq или a (mod m). Таким образом, всякое целое число a всегда сравнимо с остатком r, получающимся при делении его на m.

Примеры.

1. Доказать, что сравнение 2m+1(m+1)²(mod m) является верным.

Имеем: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², а (- m²) делится на m => наше сравнение верно.

2. Доказать, что следующее сравнения являются неверными:

1.  25 (mod 10)

Если числа сравнимы по модулю m, то они имеют с ним один и тот же НОД.

Имеем: 4=2·2, 10=2·5, 25=5·5

НОД(4,10) = 2, НОД(25,10) = 5, следовательно наше сравнение неверно.

2. (2n+1)·(2m+1) 2k (mod 6), где n, m, k – целые числа.

§2. Свойства сравнений

1. Свойства сравнений, не зависящие от модуля.

Многие свойства сравнений аналогичны свойствам равенств.

1.  Отношение a  b (mod m) является отношением эквивалентности, т. е. удовлетворяет требованиям:

а)  рефлексивности: a a (mod m) (всякое целое число a сравнимо с самим собой по модулю m);

    в)  симметричности: если a b (mod m), то и b a (mod m);

   с) транзитивности: если  a  b (mod m),  а  b  с (mod m), то aс (mod m).

2. Сравнения no одному и тому же модулю можно почленно складывать, то есть если a b (mod m), c (mod m), то a+c b+d (mod m).

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

По условию m/(a-b) и m/ (c-d). Следовательно, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c  b+d (mod m).

Примеры.

Найти остаток при делении  на 13.

Решение:   -1 (mod 13) и   1 (mod 13), тогда  (-1)+1 0 (mod 13), то есть остаток от деления  на 13 равен 0.

3.  Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого, то есть если a  b (mod m), c (mod m), то

a-c b-d (mod m).

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

По условию m/(a-b) и m/(c-d). Следовательно, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

4. (следствие свойств 1, 2, 3). К обеим частям сравнения можно прибавлять одно и то же целое число.

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

Пусть a  b (mod m) и k –любое целое число. По свойству рефлексиности

k=k (mod m), а согласно свойствам 2 и 3 имеем a+k  b+k (mod m).

5. Сравнения по одному и тому же модулю можно почленно перемножать, то есть если a  b (mod m), c (mod m), то

a·c·d (mod m).

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

По условию, a-b є mz, c-d є mz. Следовательно a·c-b·d = (a·c - b·c)+(b·c-       b·d)=(a-b)·c+b·(c-d) є mz, то есть a·c·d (mod m).

Следствие. Обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если а  b (mod т) и s — целое неотрицательное число, то as  bs (mod m).

Примеры.

1. Найти остаток от деления на 3 числа: А=-·

 Решение: очевидно 131 (mod 3)

                            2 -1 (mod 3)

                                    5 -1 (mod 3), тогда

 -· 1-1 0 (mod 13)

Ответ: искомый остаток равен нулю, и А делится на 3.

2. Доказать, что 1 +   13, если х=3n+1 (n=0,1,2,…).

Решение:

        Докажем, что 1+0(mod13) или 1+0(mod 13)  

1+=1+1+=

= 1+

Так как 271 (mod 13), то 1+1+1·3+1·9 (mod 13).

ч.т.д.

       3.  Найдём остаток при делении с остатком числа  на 24.

Имеем:  1 (mod 24), поэтому

                1 (mod 24)

Прибавляя к обеим частям сравнения по 55, получаем:

 (mod 24).

Имеем: (mod 24), поэтому

               (mod 24) при любом k є N.

 Следовательно (mod 24). Поскольку (-8)  16(mod 24), искомым остатком является 16.

6.  Обе части сравнения можно умножать на одно и то же целое число.

2.Свойства сравнений, зависящие от модуля.

7.  Если ab (mod т) и т n, то ab (mod п)

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

        Так как ab (mod т), то (а — b)  т. А так как т n, то в силу транзитивности отношения делимости (а — b n), то есть аb (mod n).

Пример.

Найти остаток от деления 196 на 7.

Решение:

Зная, что 196=, можно записать 196 (mod 14). Воспользуемся предыдущим свойством, 14 7, получим 196 (mod 7), то есть 196  7.

8. Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.

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

Пусть ab (mod т) и с-целое положительное число. Тогда a-b = mt и ac-bc=mtc, или acbc (mod mc).

Пример.

Выяснить, является ли значение выражения  целым числом.

Решение:

Представим дроби в виде сравнений: 4 (mod 3)

                                                   1 (mod 9)

                                                                         31 (mod 27)

Сложим почленно эти сравнения (свойство 2), получим 124 (mod 27)      Мы видим, что 124 не делится целочисленно на 27, следовательно значение выражения тоже не является целым числом.

9. Обе части сравнения можно разделить на их общий множитель, если он взаимно простой с модулем.

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

Если cаcb (mod m), то есть m/c(a-b) и число с взаимно простое с m, (с,m)=1, то m делит a-b. Следовательно, ab (mod т).

 Пример.

609 (mod 17), после деления обеих частей сравнения на 3 получим:

 20 (mod 17).

Делить обе части сравнения на число, не взаимно простое с модулем, вообще говоря, нельзя, так как после деления могут получиться числа, несравнимые по данному модулю.

Пример.

8 (mod 4), но 2  (mod 4).

10.   Обе части сравнения и модуль можно разделить на их общий делитель.

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

Если kakb (mod km), то k (a-b) делится на km. Следовательно, a-b делится на m, то есть ab (mod т).

11.   Пусть Р (х) — многочлен с целыми коэффициентами, а и Ь — переменные, принимающие целые значения. Тогда если ab (mod т), то Р (а)  Р (b) (mod m).

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

Пусть Р (х) = с0хп + с1хn-1 + ... + cn-1 x+ сn . По условию ab (mod т), тогда

ak  bk (mod m) при k = 0, 1, 2, …,n. Умножая обе части каждого из полученных n + 1 сравнений на cn-k, получим:

cn-kak  сn-k  bk (mod m), где k = 0, 1, 2, …,n.

Складывая последние сравнения, получим: Р (а)  Р (b) (mod m). Если а  (mod m) и ci di (mod m), 0 ≤ i ≤n, то

 (mod m). Таким образом, в сравнении по модулю m отдельные слагаемые и множители можно заменять числами, сравнимыми по тому же модулю m.

Вместе с тем следует обратить внимание на то, что встречающиеся в сравнениях показатели степеней заменять таким образом нельзя: из

an c(mod m) и nk(mod m) не следует, что аk  с (mod m).

Свойство 11 имеет ряд важных применений. В частности, c его помощью можно дать теоретическое обоснование признаков делимости. Для иллюстрации в качестве примера дадим вывод признака делимости на 3.

Пример.

Всякое натуральное число N можно представить в виде систематического числа:  N = а010n + а1 10n-1 + ... + аn-110 + аn .

Рассмотрим многочлен f (х) = а0хn+ a1xn-1 + ... + аn-1х+аn. Так как

10 1 (mod 3), то по свойству 10  f (10) f(1) (mod 3) или

N = а010n + а1 10n-1 + ... + аn-110 + аn   а1+ а2+…+ аn-1+ аn (mod 3), т. е. для делимости N на 3 необходимо и достаточно, чтобы сумма цифр этого числа делилась на 3.

§3. Системы вычетов

1. Полная система вычетов.

Числа равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m.

Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq+r заставим q пробегать все целые числа.

Соответственно m различным значением r имеем m классов чисел по модулю m.

Любое число класса называется вычетом по модулю m по отношению ко всем числам того же класса. Вычет, получаемый при q=0, равный остатку r, называется наименьшим неотрицательным вычетом.

Вычет ρ, самый малый по абсолютной величине, называется абсолютно наименьшим вычетом.

Очевидно, при r<            имеем ρ=r; при r> имеем ρ=r-m; наконец, если m четное и r=, то за ρ можно принять любое из двух чисел  и -m= - .

Выберем из каждого класса вычетов по модулю т по одному числу. Получим т целых чисел: х1 ,…, хm. Множество {х1 ,…, хт } называют полной системой вычетов по модулю m.

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

Пример.

Составить несколько полных систем вычетов по модулю т = 5. Имеем классы: 0, 1, 2,  3, 4.

0 = {... -10, -5,0,        5,        10,…}

1= {... -9, -4, 1, 6,         11,…}

2. = {... -8, -3, 2, 7,         12,…}
3. = {... -7, -2, 3, 8,         13,…}
4. = {... -6,  -1, 4,        9,        14,…}

Составим несколько полных систем вычетов, взяв по одному вычету из каждого класса:

0,        1,    2,    3,        4

5,        6,    2,    8,        9

  -10, -9,  -8,   -7,        -6

  - 5,  -4,   -3,   -2,        -1

и т. д.

Наиболее употребительны:

1.  Полная система наименьших неотрицательных вычетов: 0, 1,      т -1 В приведенном выше примере: 0, 1, 2, 3, 4. Такая система вычетов составляется просто: надо выписать все неотрицательные остатки, получающиеся при делении на m.
2. Полная система наименьших положительных вычетов(из каждого класса берётся наименьший положительный вычет): 

1, 2, …,m. В нашем примере: 1, 2, 3, 4, 5.

3. Полная система абсолютно наименьших вычетов. Вслучае нечетного m абсолютно наименьшее вычеты представляются рядом.

-,…, -1, 0, 1,…,,

а в случае четного m каким – либо из двух рядов

 +1, …, -1, 0, 1,…, ,

, …, -1, 0, 1, …,.

В приведенном примере:-2, -1, 0, 1, 2.

Рассмотрим теперь основные свойства полной системы вычетов.

Теорема 1. Любая совокупность m целых чисел:

xl ,x2 ,…,хm                                                               (1)

попарно не сравнимых по модулю m, образует полную систему вычетов по модулю m.

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

1.  Каждое из чисел совокупности (1) принадлежит некоторому классу.
2. Любые два числа xi и xj из (1) несравнимы между собой, т. е. принадлежат различным классам.
3. Всего в (1) m чисел, т. е. столько же, сколько имеется классов по модулю т.

Следовательно, совокупность чисел х1 ,х2 ,…,хт — полная система вычетов по модулю m.

Теорема 2. Пусть (а, т) = 1, b — произвольное целое число; тогда если х1 ,х2 ,…,хт —полная система вычетов по модулю m, то и совокупность чисел ах1 + b, ах2 + b,…, ахm + b тоже полная система вычетов по модулю m.

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

Рассмотрим

              ах1 + b, ах2 + b,…, ахm + b                                                (2)

1. Каждое из чисел совокупности (2) принадлежит некоторому классу.
2.  Любые два числа axi +b и axj + b из (2) несравнимы между собой, то есть принадлежат различным классам.

Действительно, если бы в (2) имелись такие два числа, что

axi +b axj + b (mod m), (i = j), то получили бы axi axj (mod т). Так как (а, т) = 1, то свойству  сравнений можно сократить обе части сравнения на а. Получаем xi xj (mod m).

По условию же xi xj (mod т) при (i = j) , так как х1 ,х2, ..., хm — полная система вычетов.

3. Совокупность чисел (2) содержит т чисел, то есть столько, сколько имеется классов по модулю m.

Итак, ах1 + b, ах2 + b,…, ахm + b — полная система вычетов по модулю m.

Пример.

 Пусть т = 10, а = 3, b = 4.

Возьмем какую-нибудь полную систему вычетов по модулю 10, например: 0, 1, 2,…, 9. Составим числа вида ах + b. Получим: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Полученная совокупность чисел — полная система вычетов по модулю 10.

2. Приведённая система вычетов.

Докажем следующую теорему.

Теорема 1.

Числа одного и того же класса вычетов по модулю m имеют с m один и тот же наибольший общий делитель: если ab (mod m), то (а, m) = (b, m).

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

Пусть ab (mod m). Тогда а = b+mt, где t є z. Из этого равенства следует, что (а, т) = (b, т).

Действительно, пусть δ-общий делитель a и m, тогда a δ, m δ. Так как а = b+mt, то b=a-mt, следовательно b δ. Поэтому любой общий делитель чисел a и m  является общим делителем m и b.

        Обратно, если m δ и b δ, то а = b+mt делится на δ, a потому любой общий делитель m и b является общим делителем a и m. Теорема доказана.

Определение 1. Наибольший общий делитель модуля т и любого числа а из данного класса вычетов по т называется наибольшим общим делителем т и этого класса вычетов.

Определение 2. Класс вычетов а по модулю т называется взаимно простым с модулем m, если наибольший общий делитель а и т равен 1 (то есть если т и любое число из а взаимно просты).

Пример. 

Пусть т = 6. Класс вычетов 2 состоит из чисел {..., -10,-4, 2, 8, 14, ...}. Наибольший общий делитель любого из этих чисел и модуля 6 равен 2. Значит, (2, 6) = 2. Наибольший общий делитель любого числа из класса 5 и модуля 6 равен 1. Значит, класс 5 взаимно прост с модулем 6.

Выберем из каждого класса вычетов, взаимно простого с модулем m, по одному числу. Получим систему вычетов, составляющую часть полной системы вычетов. Ее называют приведенной системой вычетов по модулю m.

Определение 3. Совокупность вычетов по модулю m, взятых по одному из каждого взаимно простого с т класса вычетов по этому модулю, называется приведенной системой вычетов.

Из определения 3 следует способ получения приведенной системы вычетов по модулю т: надо выписать какую-либо полную систему вычетов и удалить из нее все вычеты, не взаимно простые с m. Оставшаяся совокупность вычетов — приведенная система вычетов. Приведенных систем вычетов по модулю m, очевидно, можно составить бесчисленное множество.

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

Пример.

Если т = 8, то 1, 3, 5, 7 — приведенная система наименьших неотрицательных вычетов, 1, 3, -3,-1 — приведенная система абсолютно наименьших вычетов.

Теорема 2.

 Пусть число классов, взаимно простых с m, равно k. Тогда любая совокупность k целых чисел

                                                                                                   (1)

попарно несравнимых по модулю m и взаимно простых с m, представляет собой приведенную систему вычетов по модулю m.

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

 а) Каждое число совокупности (1) принадлежит некоторому классу.

2. Все числа из (1) попарно несравнимы по модулю т, то есть принадлежат различным классам по модулю m.
3. Каждое число из (1) взаимно просто с т, то есть все эти числа принадлежат различным классам, взаимно простым с модулем m.
4. Всего в (1) имеется k чисел, то есть столько, сколько должна содержать приведенная система вычетов по модулю m.

Следовательно, совокупность чисел (1) — приведенная система вычетов по модулю т.

§4. Функция Эйлера.

Теоремы Эйлера и Ферма.

1. Функция Эйлера.

Обозначим через φ (т) число классов вычетов по модулю m, взаимно простых с m, то есть число элементов приведенной системы вычетов по модулю т. Функция φ (т) является числовой. Ее называют функцией Эйлера.

Выберем в качестве представителей классов вычетов по модулю т числа 1, ... , т - 1, т. Тогда φ (т) — количество таких чисел, взаимно простых с т. Иными словами, φ(т) — количество положительных чисел, не превосходящих m и взаимно простых с m.

Примеры.

1. Пусть т = 9. Полная система вычетов по модулю 9 состоит из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9. Из них взаимно просты с 9 числа 1,2,4, 5, 7, 8. Так как количество этих чисел равно 6, то φ (9) = 6.
2. Пусть т = 12. Полная система вычетов состоит из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Из них взаимно просты с 12 числа 1, 5, 7, 11. Значит,

 φ(12) = 4.

При т = 1 полная система вычетов состоит из одного класса 1. Общим натуральным делителем чисел 1 и 1 является 1, (1, 1) = 1. На этом основании полагают φ(1) = 1.

Перейдем к вычислению функции Эйлера.

1) Если т = р — простое число, то φ (р) = р- 1.

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

  Вычеты 1, 2, ... , р- 1 и только они взаимно просты с простым числом р. Поэтому φ(р) = р - 1. 

2) Если т = рк — степень простого числа р, то

                                φ(т) = (р - 1).                                                   (1)

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

Полная система вычетов по модулю т = рк состоит из чисел 1,..., pk - 1, рк  Натуральные делители т являются степенями р. Поэтому число а может иметь общий делитель с m, отличный от 1, лишь в случае, когда а делится на р. Но среди чисел 1, ... , pk -1 на р делятся лишь числа р, 2р, ... , р2, ... рк, количество которых равно рк : р = рк-1. Значит, взаимно просты с т = рк остальные рк - рк-1 = pk-l(p-1) чисел. Тем самым доказано, что

φ (рк) = рк-1 (р-1).

Теорема 1. 

Функция Эйлера мультипликативна, то есть для взаимно простых чисел m иn имеем φ (mn) = φ(m) φ (n).

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

 Первое требование в определении мультипликативной функции выполняется тривиальным образом: функция Эйлера определена для всех натуральных чисел, причем φ (1) = 1. Нам надо лишь показать, что если тип взаимно простые числа, то

                       φ (тп) = φ (т) φ  (п).                                            (2)

Расположим полную систему вычетов по модулю тп в виде п х т — матрицы

                1                          2                   т

                                          т + 1                  т + 2              2т

………………………………    

(п -1) т+1       (п - 1) m + 2      пт

Поскольку т и п взаимно просты, то число х взаимно просто с тп тогда и только тогда, когда х взаимно просто с т и х взаимно просто с п. Но число km + t взаимно просто с т в том и только том случае, когда t взаимно просто с т. Поэтому числа, взаимно простые с m, располагаются в тех столбцах, для которых t пробегает приведенную систему вычетов по модулю т. Число таких столбцов равно φ (т). В каждом столбце представлена полная система вычетов по модулю п. Из этих вычетов φ (п) взаимно просты с п. Значит, общее количество чисел, взаимно простых и с т и с n, равно φ (т) φ (n)

(φ (т) столбцов, в каждом из которых берется φ (п) чисел). Эти числа, и только они, взаимно просты с тп. Тем самым доказано, что

φ (тп) = φ (т) φ  (п).

Примеры.

№1.  Доказать справедливость следующих равенств

φ(4n) =

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

1. Если (n,2)=1, то φ(4n)= φ(4) φ(n)=2 φ(n)
2. Если же n=

№2.  Решить уравнение

Решение: так как (m)=, то =, то есть =600, =75, =3·, тогда х-1=1, х=2,

                                                                                                                       y-1=2, y=3

                                                                                                               Ответ: х=2, y=3

Мы можем вычислить значение функции Эйлера (m), зная каноническое представление числа m:

m=.

В силу мультипликативности (m) имеем:

(m)=.

Но по формуле (1) получаем, что

-1), и поэтому

                                       (3)

Равенство (3) можно переписать в виде:

Поскольку =m, то                 (4)

Формула (3) или, что то же самое, (4) и является искомой.

Примеры.

№1.  Чему равна сумма

Решение:  ,

, =18 (1-) (1- =18 , тогда = 1+1+2+2+6+6=18.

№2. На основании свойств числовой функции Эйлера доказать, что в последовательности натуральных чисел существует бесконечное множество простых чисел.

Решение: Пологая количество простых чисел конечным множеством, допустим, что - наибольшее простое число и пусть a=  есть произведение всех простых чисел, на основании одного из свойств числовой функции Эйлера

Так как a≥, то a – составное число, но так как его каноническое представление содержит все простые числа, то =1. Имеем:

 =1 ,

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

№3.Решить уравнение , где х= и =2.

Решение: Используем свойство числовой функции Эйлера,

,

 и по условию =2.

Выразим из =2 , получим , подставим в

:

(1+-1=120, =11 =>

Тогда х=, х=11·13=143.

Ответ: х= 143

2. Теорема Эйлера и Ферма.

В теории сравнений важную роль играет теорема Эйлера.

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

Если целое число a взаимно простое с m, то

                                        (1)

Доказательство. Пусть

                                            (2)

есть приведённая система вычетов по модулю m.

Если a-целое число, взаимно простое с m, то

                                         (3)

также есть приведённая система вычетов по модулю m. Поэтому произведение чисел (3) сравнимо с произведением чисел (2), то есть

                 (4)

Произведение  взаимно простое с m. Поэтому согласно свойству 9 обе части сравнения (4) можно разделить на это произведение, тогда

Особенно простой вид теорема Эйлера принимает, если m=p – простое число. В этом случае , а потому получаем следующее утверждение.

Теорема Ферма.

        Если  целое число а не делится на простое число p, то

Теорема Ферма часто формулируется иначе:

Если p-простое и а-любое целое число, то

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

а) Если (а,p)=1, то согласно теореме Ферма                                         

После умножения обеих частей этого равенства на а, получим:

б) Если    (а,p) = 1 , то а делится на p. Но тогда и произведение

а(-1) =а тоже делится на p , то есть а , или .

        Итак, для любого целого числа а имеем:

Примеры.

№1.  

Найдем остаток от деления 243132 на 34.

Решение: 243 5 (mod 34). Тогда 243132  5132 (mod 34).

Согласно теореме Эйлера 5φ(34)  1 (mod 34), или 5161 (mod 34).

 Далее делим 132 на 16: 132 = 16 • 8 + 4. Тогда 243132  5132  516·8+4(516)· 54625

Таким образом, 243132  13 (mod 34).

Следовательно, г= 13.

№2.

Девятая степень однозначного числа n оканчивается цифрой 7; найти это однозначное число.

 Решение: так как девятая степень однозначного числа n оканчивается цифрой 7, то остаток от деления числа n9  на 10 должен быть равен 7, что равносильно справедливости сравнения n97(mod 10)

Так как (7,10)=1, то (n,10)=1. Воспользуемся теоремой Эйлера, получим: n4 (mod 10), где φ(10)=4.

Возведём обе части последнего сравнения в квадрат

n8(mod 10).

Тогда n9= n8·n1·n(mod 10) и следовательно, n(mod 10).

Ответ: n=7

№3.

Показать, что

Решение: Воспользуемся малой теоремой Ферма: если (а,p)=1, то

 .

        Числа 1,2,3,4,5,6 взаимно просты с числом 7. На основании указанной теоремы

 ,                                       (1)

где а= 1,2,3,4,5,6.

        Сравнение (1) почленно возведём в куб, получим:

                      (2)

Складывая почленно сравнения вида (2) имеем при а= 1,2,3,4,5,6:

№4.

Показать, что (

Решение: Каноническое разложение числа 105 = 3·5·7.

        Замечая, что (73,3)=(73,5)=(73,7)=1 и 73-простое число, применим малую теорему Ферма к числу 73 по модулям 3,5,7, получим сравнения:

Путём возведения обеих частей сравнений в соответствующие степени, получим сравнения:

Воспользуемся свойством: если некоторое сравнение имеет место по нескольким модулям, то оно справедливо по модулю, являющемуся наименьшим общим кратным данных модулей; следовательно,

,

откуда                                          (

§1. Основные понятия, связанные с решением сравнений.

1. Корни сравнений.

Пусть т — целое число и  f(х) = а0хп + а1хп-1 + ... + ап —многочлен с целыми коэффициентами a0 ,a1, …, ап .Если подставить вместо х целые числа, значения многочлена f(х) тоже будут целыми числами.

Определение 1. Пусть f(х) = а0хп + ... + ап , φ(х)=bоХк + ... + bk — многочлены с целыми коэффициентами а0,…,ап , bо,…,bk . Решить сравнение f (х) φ(x) (mod m) — значит найти все целые числа х, при подстановке которых в многочлены f(х) и φ(х) получаются целые числа, разность которых делится на m. Если f(с)(с) (mod m), то говорят, что целое число с удовлетворяет сравнению f (х) φ(x) (mod m), или, иначе, является корнем этого сравнения.

Теорема 1. 

Если число с удовлетворяет сравнению

f (х)  φ (х) (mod m),                                                       (1)

mo и любое число с1 такое, что с  с1 (mod m), удовлетворяет тому же сравнению.

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

Так как с удовлетворяет сравнению (1), то f(с) φ (с) (mod m), то есть  f(с) — φ (с)  0 (mod m). Но так как с  с1 (mod m), то по свойству 11 сравнений  и f(с1)  φ (с1) (mod m). Теорема доказана.

Из доказанной теоремы вытекает, что если целое число с удовлетворяет сравнению f(x) 0 (mod m), то и все числа из содержащего с класса вычетов  по модулю т удовлетворяют тому же сравнению. Поэтому задача о решении сравнений может быть поставлена иначе:

Определение. Решить сравнение:

f (х)  φ (х) (mod m),

где f(х) и φ(х) — многочлены с целыми коэффициентами— значит найти все классы вычетов по модулю m, любое число из которых удовлетворяет сравнению (1) (то есть при подстановке в (1) любого числа из этих классов вычетов получаются числа, сравнимые по модулю т).

Из определения  вытекает, что любое сравнение вида (1) можно решить, сделав т проб, а именно, подставив в f(х) и φ (х) вместо х по очереди все числа из полной системы вычетов по модулю т (например, числа

0, 1,…, т-1). После этого надо вычислить значения f(с) и φ(с) и отобрать те, для которых f (с) — φ (с) делится на т.

 Примеры.

1. Решим сравнение:

                                 f (х) = х3 — 3    0 (mod 6).                                           (2)

Надо подставить вместо х числа 0, 1, 2, 3, 4, 5,6.  f (0) =-3, f (1) = -2, f (2) = 5,  f(3) = 24, f(4) = 61, f(5) = 122. Только f(3) = 24 делится на 6. Значит, решением сравнения (2) является класс вычетов  = {... -9, -3, 3, 9 ...}.

Разумеется, вместо чисел 0, 1,2, 3, 4, 5 можно было подставить числа, образующие иную полную систему вычетов по модулю 6, например числа

-2, -1,0, 1,2, 3.

Существуют сравнения, совсем не имеющие решений.

2. Решим сравнение:

х4 + 2х — 1  0 (mod 7).

Составим полную систему абсолютно наименьших вычетов

0, 1, 2, 3, -3, -2, -1 по модулю 7.  Ни один из вычетов данной системы не удовлетворяет данному сравнению. Следовательно, сравнение решений не имеет.

С теоретической точки зрения задача решения сравнений вида / (х) г= 0 (mod т) очень проста: мы просто ищем решения в конечном множестве классов (т классов) по модулю т, что достигается, как мы уже установили, путем конечного числа испытаний вычетов некоторой полной системы вычетов по модулю т. Однако на практике указанный прием испытания вычетов при больших модулях оказывается затруднительнымдак как приводит к большому количеству испытаний. Например, для решения сравнения 19х8+ + 13х2 — 2х + 17 Е55 0 (mod 625), следуя указанному приему решения сравнений, надо проверить 625 вычетов.

Естественно возникает вопрос: нельзя ли упростить работу и свести ее к выполнению меньшего числа операции? Оказывается, можно. Существуют способы, позволяющие найти число решений сравнения, а в ряде случаев и найти все решения значительно быстрее.