Квадратични сравнения по съставен модул. Решаване на сравнения от първа степен. Делимост и сравнения по модул

Въведение

§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. Преобразуване на обикновена дроб в крайна дроб

десетична систематична дроб

Заключение

Литература

Въведение

В живота си често се налага да се справяме с цели числа и проблеми, свързани с тях. В тази теза разглеждам теорията за сравнение на цели числа.

Две цели числа, чиято разлика е кратна на дадено естествено числом се наричат ​​сравними по модулм.

Думата „модул“ идва от латинското modulus, което на руски означава „мярка“, „величина“.

Твърдението „a е сравнимо с 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, тогава напишете a b (mod m).

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

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

Нека дефинираме, че отношението на сравнимост по модул m съвпада с отношението на сравнимост по модул (-m) (делимостта на m е еквивалентна на делимостта на –m). Следователно, без загуба на общост, можем да приемем, че m>0.

Примери.

Теорема. (знак за съпоставимост на духовните числа по модул 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 или a b (mod m).

Обратно, нека a b (mod m). Това означава, че a-b m или a-b=mt, t z (3)

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

Примери.

5=4·(-2)+3

23=4·5+3

24=3·8+0

10=3·3+1

Определение 2. Две или повече числа, които дават еднакви остатъци, когато се разделят на m, се наричат ​​равни остатъци или сравними по модул m.

Примери.

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

1. Докажете, че следните сравнения са неверни:

Ако числата са сравними по модул m, тогава те имат еднакъв gcd с него.

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

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

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

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

Много свойства на сравненията са подобни на свойствата на равенствата.

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

B) симетрия: ако a b (mod m), след това b a (mod m);

В) преходност: ако a b (mod m) и b с (mod m), след това a с (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.

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).

1. (следствие от свойства 1, 2, 3). Можете да добавите едно и също цяло число към двете страни на сравнението.

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

Нека a b (mod m) и k е всяко цяло число. Чрез свойството рефлексивност

k=k (mod m), а според свойства 2 и 3 имаме a+k b+k (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).

Последица. И двете страни на сравнението могат да бъдат повдигнати до една и съща неотрицателна цяло число: ако ab (mod m) и s е неотрицателно цяло число, тогава a s b s (mod m).

Примери.

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

2 -1 (мод 3)

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

- · 1-1 0 (мода 13)

Отговор: търсеният остатък е нула и А се дели на 3.

Решение:

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

1+ =1+ 1+ =

Тъй като 27 1 (mod 13), тогава 1+ 1+1·3+1·9 (mod 13).

и т.н.

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

Имаме: 1 (mod 24), така че

1 (мод. 24)

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

(мод. 24).

Следователно имаме: (mod 24).

(mod 24) за всяко k є N.

Следователно (мод. 24). От (-8)16 (mod 24), необходимият остатък е 16.

1. И двете страни на сравнението могат да бъдат умножени по едно и също цяло число.

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

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

Тъй като a b (mod t), тогава (a - b) t. И тъй като t n , то поради транзитивността на отношението на делимост(a - b n), тоест a b (mod n).

Пример.

Намерете остатъка, когато 196 е разделено на 7.

Решение:

Знаейки, че 196= , можем да напишем 196(мода 14). Нека използваме предишното свойство, 14 7, получаваме 196 (mod 7), тоест 196 7.

1. И двете страни на сравнението и модулът могат да бъдат умножени по едно и също положително цяло число.

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

Нека a b (mod t ) и c е положително цяло число. Тогава a-b = mt и ac-bc=mtc, или ac bc (mod mc).

Пример.

Определете дали стойността на израз ецяло число.

Решение:

Нека представим дроби под формата на сравнения: 4(мод 3)

1 (мод 9)

31 (мод. 27)

Нека добавим тези сравнения термин по термин (свойство 2), получаваме 124(mod 27) Виждаме, че 124 не е цяло число, делимо на 27, оттук и значението на изразасъщо не е цяло число.

1. Двете страни на сравнението могат да бъдат разделени на техния общ множител, ако той е взаимно прост с модула.

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

Ако ок cb (mod m), тоест m/c(a-b) и числотос взаимно прости с m, (c,m)=1, тогава m дели a-b. следователно a b (mod t).

Пример.

60 9 (mod 17), след като разделим двете страни на сравнението на 3, получаваме:

20 (мода 17).

Най-общо казано, невъзможно е да се разделят двете страни на едно сравнение с число, което не е взаимнопросто с модула, тъй като след разделянето могат да се получат числа, които са несравними по отношение на даден модул.

Пример.

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

1. И двете страни на сравнението и модулът могат да бъдат разделени с техния общ делител.

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

Ако ka kb (mod km), тогава k (a-b) се разделя на km. Следователно a-b се дели на m, т.е a b (mod t).

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

Нека P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n. По условие a b (mod t), тогава

a k b k (mod m) за k = 0, 1, 2, …,n. Умножаване на двете страни на всяко от получените n+1 сравнения по c n-k , получаваме:

c n-k a k c n-k b k (mod m), където k = 0, 1, 2, …,n.

Събирайки последните сравнения, получаваме: P (a) P (b) (mod m). Ако a (mod m) и c i d i (mod m), 0 ≤ i ≤n, тогава

(mod m). По този начин, при сравнение по модул m, отделните членове и фактори могат да бъдат заменени с числа, сравними по модул m.

В същото време трябва да се отбележи, че експонентите, намерени в сравненията, не могат да бъдат заменени по този начин: от

a n c(mod m) и n k(mod m) не следва, че a k s (mod m).

Свойство 11 има редица важни приложения. По-специално, с негова помощ е възможно да се даде теоретична обосновка на признаците на делимост. За илюстрация, като пример, ще дадем извеждането на теста за делимост на 3.

Пример.

Всяко естествено число N може да се представи като систематично число: N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n .

Да разгледаме полинома f(x) = a 0 x n + a 1 x n-1 + ... + a n-1 x+a n . защото

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

N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n a 1 + a 2 +…+ a n-1 + a 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= - .

Нека изберем от всеки клас остатъци по модул T едно число наведнъж. Получаваме t цели числа: x 1,…, x m. Множеството (x 1,…, x t) се нарича пълна система от удръжки по модул m.

Тъй като всеки клас съдържа безкраен брой остатъци, е възможно да се съставят безкраен брой различни пълни системи от остатъци за даден модул m, всеки от които съдържа t удръжки.

Пример.

Компилирайте няколко пълни системи от модулни извадки T = 5. Имаме класове: 0, 1, 2, 3, 4.

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

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

Нека създадем няколко пълни системи от приспадания, като вземем по едно приспадане от всеки клас:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

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

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

и т.н.

Най-често:

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

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

1. Пълна система от абсолютно минимални удръжки.В случай на нечетно m, абсолютните най-малки остатъци са представени един до друг.

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

а в случай на четно m, един от двата реда

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

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

В дадения пример: -2, -1, 0, 1, 2.

Нека сега разгледаме основните свойства на пълната система от остатъци.

Теорема 1 . Всяка колекция от m цели числа:

x l ,x 2 ,…,x m (1)

по двойки несравними по модул m, образува пълна система от остатъци по модул m.

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

1. Всяко от числата в колекцията (1) принадлежи към определен клас.
2. Всякакви две числа x i и x j от (1) са несравними помежду си, т.е. принадлежат към различни класове.
3. Има m числа в (1), т.е. същият брой, колкото има модулни класове T.

x 1, x 2,…, x t - пълна система от удръжки по модул m.

Теорема 2. Нека (a, m) = 1, b - произволно цяло число; тогава ако x 1, x 2,…, x t е пълна система от остатъци по модул m, тогава колекцията от числа ax 1 + b, брадва 2 + b,…, брадва m + b също е пълна система от остатъци по модул m.

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

Нека помислим

Ax 1 + b, ax 2 + b,…, ax m + b (2)

1. Всяко от числата в колекцията (2) принадлежи към определен клас.
2. Които и да е две числа ax i +b и ax j + b от (2) са несравними помежду си, тоест принадлежат към различни класове.

Наистина, ако в (2) имаше две числа, такива че

ax i +b ax j + b (mod m), (i = j), тогава ще получим ax i ax j (mod t). Тъй като (a, t) = 1, тогава свойството на сравненията може да намали и двете части на сравнението сА . Получаваме x i x j (mod m).

По условие x i x j (mod t) при (i = j), тъй като x 1, x 2, ..., x m - пълна система от удръжки.

1. Наборът от числа (2) съдържа T числа, тоест толкова, колкото има класове по модул m.

И така, ax 1 + b, ax 2 + b,…, ax m + b - пълна система от остатъци по модул m.

Пример.

Нека m = 10, a = 3, b = 4.

Нека вземем някаква пълна система от остатъци по модул 10, например: 0, 1, 2,…, 9. Нека съставим числа от форматабрадва + б. Получаваме: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Полученият набор от числа е пълна система от остатъци по модул 10.

1. Дадената система на удръжки.

Нека докажем следната теорема.

Теорема 1.

Числата от един и същи остатъчен клас по модул m имат един и същ най-голям общ делител с m: ifа б (mod m), тогава (a, m) = (b, m).

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

Нека a b (mod m). Тогава a = b +mt, където t є z. От това равенство следва, че (a, t) = (b, t).

Наистина, нека δ е общ делител на a и m, тогава aδ, m δ. Тъй като a = b +mt, тогава b=a-mt, следователно bδ. Следователно всеки общ делител на числата a и m е общ делител на m и b.

Обратно, ако m δ и b δ, тогава a = b +mt се дели на δ и следователно всеки общ делител на m и b е общ делител на a и m. Теоремата е доказана.

Определение 1. Най-голям общ делител на модула t и всяко число a от този клас отчисления от T наречен най-голям общ делител T и този клас удръжки.

Определение 2. Клас на остатъци a по модул t наречен взаимнопрост на модулм , ако най-големият общ делител a и t е равно на 1 (тоест, ако m и всяко число от a са взаимно прости).

Пример.

Нека t = 6. Остатъчен клас 2 се състои от числата (..., -10, -4, 2, 8, 14, ...). Най-големият общ делител на което и да е от тези числа и модул 6 е 2. Следователно (2, 6) = 2. Най-големият общ делител на всяко число от клас 5 и модул 6 е 1. Следователно клас 5 е взаимнопрост с модул 6 .

Нека изберем едно число от всеки клас остатъци, което е взаимнопросто с модул m. Получаваме система от удръжки, която е част от пълната система от удръжки. Викат яредуцирана система от остатъци по модул m.

Определение 3. Набор от остатъци по модул m, взети по един от всеки взаимнопрост с T клас остатъци за този модул се нарича редуцирана система от остатъци.

От дефиниция 3 следва метод за получаване на редуцирана система от остатъчни модули T: необходимо е да се запише някаква пълна система от остатъци и да се премахнат от нея всички остатъци, които не са взаимно прости с m. Останалият набор от удръжки е намалената система от удръжки. Очевидно могат да бъдат съставени безкраен брой системи от остатъци по модул m.

Ако вземем като изходна система пълната система от най-малко неотрицателни или абсолютно най-малко остатъци, тогава с помощта на посочения метод получаваме съответно редуцирана система от най-малко неотрицателни или абсолютно най-малки остатъци по модул m.

Пример.

Ако Т = 8, тогава 1, 3, 5, 7 е редуцираната система от най-малко неотрицателни остатъци, 1, 3, -3, -1- редуцирана система на абсолютно минимални удръжки.

Теорема 2.

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

по двойки несравними по модул m и взаимно прости с m, е редуцирана система от остатъци по модул m.

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

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

1. Всички числа от (1) са несравними по двойки по модул T, тоест те принадлежат към различни класове по модул m.
2. Всяко число от (1) е взаимнопросто с T, т.е. всички тези числа принадлежат към различни класове взаимно прости по модул m.
3. Общо (1) наличник числа, т.е. толкова, колкото редуцираната система от остатъци по модул m трябва да съдържа.

Следователно наборът от числа(1) - намалена система на удръжки по модул T.

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

Теореми на Ойлер и Ферма.

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

Нека означим с φ(T) броят на класовете остатъци по модул m, взаимно прости с m, т.е. броят на елементите на редуцираната система от остатъци по модулт. Функция φ (t) е числова. Викат яФункция на Ойлер.

Нека да изберем като представители на класовете остатък по модул t числа 1, ..., t - 1, t. Тогава φ (t) - броят на тези числа, взаимно прости ст. С други думи, φ (t) - броят на положителните числа, непревишаващи m и относително прости на m.

Примери.

1. Нека t = 9. Пълната система от остатъци по модул 9 се състои от числата 1, 2, 3, 4, 5, 6, 7, 8, 9. От тях числата 1, 2, 4, 5, 7, 8 са взаимно прости до 9. Тъй като броят на тези числа е 6, тогава φ (9) = 6.
2. Нека t = 12. Пълната система от остатъци се състои от числата 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. От тях числата 1, 5, 7, 11 са взаимно прости с 12 . Това означава

φ(12) = 4.

При t = 1, пълната система от остатъци се състои от един клас 1. Общият естествен делител на числата 1 и 1 е 1, (1, 1) = 1. На тази основа приемаме, че φ(1) = 1.

Нека да преминем към изчисляването на функцията на Ойлер.

1) Ако t = p е просто число, тогава φ(p) = p- 1.

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

Отчисления 1, 2, ..., p- 1 и само те са относително прости с просто числоР. Следователно φ (р) = р - 1.

2) Ако t = p k - основна мощност p, тогава

φ(t) = (p - 1) . (1)

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

Пълна система от удръжки по модул t = p k се състои от числа 1,..., p k - 1, p k Естествени делители T са степениР. Следователно броят Аможе да има общ делител с m, различен от 1, само в случай, когатоАразделена наР.Но сред числата 1, ... , стрк -1 НаРсамо числата се делятp, 2p, ... , p2 , ... РДа се, чийто брой е равенРДа се: p = pк-1. Това означава, че те са взаимнопрости сt = pДа сеПочивкаРДа се- Рк-1= pк-л(p-1)числа. Това доказва това

φ (РДа се) = pк-1(p-1).

Теорема1.

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

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

Първото изискване в дефиницията на мултипликативна функция е изпълнено по тривиален начин: функцията на Ойлер е дефинирана за всички естествени числа и φ (1) = 1. Трябва само да покажем, че акоТипвзаимнопрости числа, тогава

φ (tp)= φ (T) φ (P).(2)

Нека подредим пълната система от удръжки по модулtpкатоПхT -матрици

1 2 T

t +1 t +2 2т

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

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

Тъй катоTИПса относително прости, след това числотохреципрочно само сtpтогава и само когатохреципрочно само сTИхреципрочно само сП. Но брояткм+треципрочно само сTако и само акоTреципрочно само сT.Следователно числата, взаимно прости с m, се намират в тези колони, за коитоTминава през редуцираната система от модулни остатъциT.Броят на тези колони е равен на φ(T).Всяка колона представя пълната система от удръжки по модулП.От тези удръжки φ(P)съвместно сП.Това означава, че общият брой числа, които са относително прости и сTи с n, равно на φ(T)φ(n)

(φ (T)колони, във всяка от които е взето φ(P)числа). Тези числа и само те са взаимно прости си т.н.Това доказва това

φ (tp)= φ (T) φ (P).

Примери.

№1 . Докажете валидността на следните равенства

φ(4n) =

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

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

Решение:защото(m)=, Че= , това е=600, =75, =3·, тогава x-1=1, x=2,

y-1=2, y=3

Отговор: x=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 .Решете уравнението, където x=И=2.

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

,

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

Нека изразим от=2 , получаваме, заместник в

:

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

Тогава x=, x=11·13=143.

Отговор:х= 143

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

Теоремата на Ойлер играе важна роля в теорията на сравненията.

Теорема на Ойлер.

Ако цяло число a е взаимно просто с m, тогава

(1)

Доказателство.Позволявам

(2)

има редуцирана система от остатъци по модул m.

Акоае цяло число, взаимно просто на m, тогава

(3)

При n те дават еднакви остатъци.

Еквивалентни формулировки: a и b сравними по модул n ако тяхната разлика а - bсе дели на n или ако a може да бъде представено като а = b + кн , Където к- някакво цяло число. Например: 32 и −10 са сравними по модул 7, тъй като

Твърдението „a и b са сравними по модул n“ се записва като:

Свойства на равенство по модул

Връзката за сравнение по модул има свойствата

Всякакви две цели числа аИ bсравним модул 1.

За числата аИ bбяха сравними по модул н, е необходимо и достатъчно разликата им да се дели на н.

Ако числата и са сравними по двойки по модул н, тогава техните суми и , както и продуктите и също са сравними по модул н.

Ако числата аИ bсравними по модул н, след това техните степени а кИ b ксъщо са сравними по модул нпод всеки естествен к.

Ако числата аИ bсравними по модул н, И нразделена на м, Че аИ bсравними по модул м.

За числата аИ bбяха сравними по модул н, представена под формата на нейното канонично разлагане на прости множители стр аз

необходимо и достатъчно за

Отношението за сравнение е отношение на еквивалентност и има много от свойствата на обикновените равенства. Например, те могат да се събират и умножават: ако

Сравненията обаче не могат, най-общо казано, да бъдат разделени едно на друго или на други числа. Пример: , но намалявайки с 2, получаваме грешно сравнение: . Правилата за съкращения за сравнения са както следва.

Също така не можете да извършвате операции върху сравнения, ако техните модули не съвпадат.

Други свойства:

Свързани определения

Дедукционни класове

Наборът от всички числа, сравними с апо модул нНаречен клас на приспадане апо модул н и обикновено се обозначава [ а] нили . По този начин сравнението е еквивалентно на равенството на класовете остатъци [а] н = [b] н .

От сравнението по модул не релация на еквивалентност в множеството от цели числа, тогава класовете остатъци по модул нпредставляват класове на еквивалентност; броят им е равен н. Наборът от всички класове остатъци по модул нозначен с или.

Операциите събиране и умножение по индуцират съответните операции върху множеството:

По отношение на тези операции множеството е краен пръстен и ако нпросто - крайно поле.

Системи за приспадане

Остатъчната система ви позволява да извършвате аритметични операции върху краен набор от числа, без да излизате извън неговите граници. Пълна система от удръжкипо модул n е всеки набор от n цели числа, които са несравними по модул n. Обикновено най-малките неотрицателни остатъци се приемат като пълна система от остатъци по модул n

или абсолютните най-малки отчисления, състоящи се от числа

в случай на нечетен ни числа

в случай на дори н .

Решаване на сравнения

Сравнения от първа степен

В теорията на числата, криптографията и други области на науката често възниква проблемът за намиране на решения за сравнения от първа степен на формата:

Решаването на такова сравнение започва с изчисляване на gcd (a, m)=d. В този случай са възможни 2 случая:

• Ако bне кратно д, тогава сравнението няма решения.
• Ако bмногократни д, тогава сравнението има уникално решение по модул м / д, или, което е същото, дмодулни решения м. В този случай, в резултат на намаляване на първоначалното сравнение с дсравнението е:

Където а 1 = а / д , b 1 = b / д И м 1 = м / д са цели числа и а 1 и м 1 са относително прости. Следователно броят а 1 може да бъде обърнато по модул м 1, тоест намерете такова число ° С, че (с други думи, ). Сега решението се намира чрез умножаване на полученото сравнение по ° С:

Практическо изчисляване на стойността ° Сможе да се приложи по различни начини: с помощта на теоремата на Ойлер, алгоритъма на Евклид, теорията на непрекъснатите дроби (вижте алгоритъма) и т.н. По-специално, теоремата на Ойлер ви позволява да запишете стойността ° Скато:

Пример

За сравнение имаме д= 2, така че по модул 22 сравнението има две решения. Нека заменим 26 с 4, сравнимо с него по модул 22, и след това намалим всичките 3 числа с 2:

Тъй като 2 е взаимнопросто с модул 11, можем да намалим лявата и дясната страна с 2. В резултат на това получаваме едно решение по модул 11: , еквивалентно на две решения по модул 22: .

Сравнения от втора степен

Решаването на сравнения на втора степен се свежда до установяване дали дадено число е квадратен остатък (използвайки закона за квадратична реципрочност) и след това изчисляване на корен квадратен по модул.

История

Китайската теорема за остатъка, известна от много векове, гласи (на съвременен математически език), че остатъчният пръстен по модул на произведението на няколко взаимно прости числа е

Помислете за сравнение на формата х 2 ≡а(мод стрα), където стр– просто нечетно число. Както беше показано в параграф 4 от §4, решението на това сравнение може да бъде намерено чрез решаване на сравнението х 2 ≡а(мод стр). Освен това сравнението х 2 ≡а(мод стрα) ще има две решения, ако ае квадратен остатък по модул стр.

Пример:

Решете квадратично сравнение х 2 ≡86 (mod 125).

125 = 5 3, 5 е просто число. Нека проверим дали 86 е квадрат по модул 5.

Оригиналното сравнение има 2 решения.

Нека намерим решение на сравнението х 2 ≡86 (mod 5).

х 2 ≡1 (модулация 5).

Това сравнение може да бъде решено по начина, посочен в предишния параграф, но ще използваме факта, че квадратният корен от 1 по модул е ​​±1 и сравнението има точно две решения. По този начин решението на сравнението по модул 5 е

х≡±1(mod 5) или, в противен случай, х=±(1+5 T 1).

Нека заместим полученото решение в сравнение по модул 5 2 =25:

х 2 ≡86 (mod 25)

х 2 ≡11 (mod 25)

(1+5T 1) 2 ≡11 (mod 25)

1+10T 1 +25T 1 2 ≡11 (mod 25)

10T 1 ≡10 (mod 25)

2T 1 ≡2 (модулация 5)

T 1 ≡1(mod 5), или, което е същото, T 1 =1+5T 2 .

Тогава решението на сравнението по модул 25 е х=±(1+5(1+5 T 2))=±(6+25 T 2). Нека заместим полученото решение в сравнение по модул 5 3 =125:

х 2 ≡86 (mod 125)

(6+25T 2) 2 ≡86 (mod 125)

36+12·25 T 2 +625T 2 2 ≡86 (mod 125)

12·25 T 2 ≡50 (mod 125)

12T 2 ≡2 (модулация 5)

2T 2 ≡2 (модулация 5)

T 2 ≡1(mod 5), или T 2 =1+5T 3 .

Тогава решението на сравнението по модул 125 е х=±(6+25(1+5 T 3))=±(31+125 T 3).

Отговор: х≡±31 (mod 125).

Нека сега разгледаме едно сравнение на формата х 2 ≡а(mod 2 α). Подобно сравнение не винаги има две решения. За такъв модул са възможни следните случаи:

1) α=1. Тогава сравнението има решение само когато а≡1(mod 2), а решението е х≡1(mod 2) (едно решение).

2) α=2. Сравнението има решения само когато а≡1(mod 4), а решението е х≡±1(mod 4) (две решения).

3) α≥3. Сравнението има решения само когато а≡1(mod 8) и ще има четири такива решения. Сравнение х 2 ≡а(mod 2 α) за α≥3 се решава по същия начин като сравненията на формата х 2 ≡а(мод стрα), само решения по модул 8 действат като първоначално решение: х≡±1(mod 8) и х≡±3 (mod 8). Те трябва да се сравняват по модул 16, след това по модул 32 и т.н. до модул 2 α.

Пример:

Решете сравнение х 2 ≡33 (mod 64)

64=2 6 . Нека проверим дали първоначалното сравнение има решение. 33≡1(mod 8), което означава, че сравнението има 4 решения.

Модул 8 тези решения ще бъдат: х≡±1(mod 8) и х≡±3(mod 8), което може да бъде представено като х=±(1+4 T 1). Нека заместим този израз за сравнение по модул 16

х 2 ≡33 (mod 16)

(1+4T 1) 2 ≡1 (mod 16)

1+8T 1 +16T 1 2 ≡1 (mod 16)

8T 1 ≡0 (mod 16)

T 1 ≡0 (mod 2)

Тогава разтворът ще приеме формата х=±(1+4 T 1)=±(1+4(0+2 T 2))=±(1+8 T 2). Нека заместим полученото решение в сравнение по модул 32:

х 2 ≡33 (mod 32)

(1+8T 2) 2 ≡1 (mod 32)

1+16T 2 +64T 2 2 ≡1 (мод. 32)

16T 2 ≡0 (мод. 32)

T 2 ≡0 (mod 2)

Тогава разтворът ще приеме формата х=±(1+8 T 2) =±(1+8(0+2t 3)) =±(1+16 T 3). Нека заместим полученото решение в сравнение по модул 64:

х 2 ≡33 (mod 64)

(1+16T 3) 2 ≡33 (mod 64)

1+32T 3 +256T 3 2 ≡33 (mod 64)

32T 3 ≡32 (mod 64)

T 3 ≡1 (mod 2)

Тогава разтворът ще приеме формата х=±(1+16 T 3) =±(1+16(1+2t 4)) =±(17+32 T 4). И така, по модул 64, оригиналното сравнение има четири решения: х≡±17(mod 64)i х≡±49 (mod 64).

Сега нека разгледаме едно общо сравнение: х 2 ≡а(мод м), (а,м)=1, - канонично разширение на модула м. Съгласно теоремата от параграф 4 на §4 това сравнение е еквивалентно на системата

Ако всяко сравнение на тази система е разрешимо, тогава цялата система е разрешима. След като намерим решението на всяко сравнение на тази система, ще получим система от сравнения от първа степен, решавайки която с помощта на китайската теорема за остатъка, ще получим решение на първоначалното сравнение. Освен това броят на различните решения на първоначалното сравнение (ако то е разрешимо) е 2 к, ако α=1, 2 к+1, ако α=2, 2 к+2, ако α≥3.

Пример:

Решете сравнение х 2 ≡4 (модулация 21).

Определение 1. Ако две числа са 1) аИ bкогато се раздели на стрдават същия остатък r, тогава такива числа се наричат ​​equiremainder или сравними по модул стр.

Изявление 1. Позволявам стрнякакво положително число. След това всяко число авинаги и освен това по единствения начин може да бъде представен във формата

Но тези числа могат да бъдат получени чрез настройка rравно на 0, 1, 2,..., стр−1. Следователно sp+r=aще получи всички възможни цели числа.

Нека покажем, че това представяне е уникално. Нека се преструваме, че стрможе да се представи по два начина a=sp+rИ a=s 1 стр+r 1 . Тогава

(2)

защото r 1 приема едно от числата 0,1, ..., стр−1, след това абсолютната стойност r 1 −rпо-малко стр. Но от (2) следва, че r 1 −rмногократни стр. Следователно r 1 =rИ с 1 =с.

Номер rНаречен минусчисла апо модул стр(с други думи, числото rнарича остатък от число аНа стр).

Изявление 2. Ако две числа аИ bсравними по модул стр, Че a−bразделена на стр.

Наистина ли. Ако две числа аИ bсравними по модул стр, тогава когато се раздели на стримат същия остатък стр. Тогава

разделена на стр, защото дясната страна на уравнение (3) е разделена на стр.

Изявление 3. Ако разликата на две числа се дели на стр, тогава тези числа са сравними по модул стр.

Доказателство. Нека означим с rИ r 1 остатък от деление аИ bНа стр. Тогава

Примери 25≡39 (mod 7), −18≡14 (mod 4).

От първия пример следва, че 25, когато се раздели на 7, дава същия остатък като 39. Наистина, 25 = 3·7+4 (остатък 4). 39=3·7+4 (остатък 4). Когато разглеждате втория пример, трябва да вземете предвид, че остатъкът трябва да бъде неотрицателно число, по-малко от модула (т.е. 4). Тогава можем да запишем: −18=−5·4+2 (остатък 2), 14=3·4+2 (остатък 2). Следователно, −18, когато е разделено на 4, оставя остатък 2, а 14, когато е разделено на 4, оставя остатък 2.

Свойства на модулните сравнения

Имот 1. За всеки аИ стрВинаги

не винаги има сравнение

Където λ е най-големият общ делител на числата мИ стр.

Доказателство. Позволявам λ най-голям общ делител на числата мИ стр. Тогава

защото m(a−b)разделена на к, Че

Следователно

И ме един от делителите на числото стр, Че

Където h=pqs.

Имайте предвид, че можем да позволим сравнения въз основа на отрицателни модули, т.е. сравнение a≡bмод( стр) означава в този случай, че разликата a−bразделена на стр. Всички свойства на сравненията остават в сила за отрицателните модули.