Методи за решаване на сравнения от първа степен. Сравнения по модул

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

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

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

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

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

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

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

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

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

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

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

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

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

Сравненията обаче не могат, най-общо казано, да бъдат разделени едно на друго или на други числа. Пример: , но намалявайки с 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: .

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

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

История

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

Сравнение с едно неизвестно хизглежда като

Където . Ако а н не се дели на м, така се вика степенсравнения.

С решениесравнението е всяко цяло число х 0 , за което

Ако х 0 удовлетворява сравнението, тогава, според свойството на 9 сравнения, всички цели числа, сравними с х 0 по модул м. Следователно, всички сравнителни решения, принадлежащи към един и същ клас на остатък по модул T, ще го разгледаме като едно решение. По този начин сравнението има толкова решения, колкото има елементи от пълната система от остатъци, които го удовлетворяват.

Наричат ​​се сравнения, чиито набори от решения съвпадат еквивалентен.

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

Сравнение на първа степен с едно неизвестно хизглежда като

(2.2)

Теорема 2.4. За да има едно сравнение поне едно решение, е необходимо и достатъчно броят b разделено на НОД( а, м).

Доказателство.Първо доказваме необходимостта. Позволявам д = GCD( а, м) И х 0 - решение за сравнение. Тогава , тоест разликата о 0 − b разделена на T.Така че има такова цяло число р, Какво о 0 − b = qm. Оттук b= ах 0 − qm. И тъй като д, като общ делител, дели числата АИ T,тогава умаляваното и изважданото се разделят на д, и следователно b разделена на д.

Сега нека докажем достатъчността. Позволявам д- най-голям общ делител на числата АИ T,И b разделена на д. Тогава по определението за делимост съществуват следните цели числа а 1 , b 1 ,T 1 , Какво .

Използвайки разширения Евклидов алгоритъм, намираме линейно представяне на числото 1 = gcd( а 1 , м 1 ):

за някои х 0 , г 0 . Нека умножим двете страни на последното равенство по b 1 д:

или, което е същото,

,

това е и е решението за сравнението. □

Пример 2.10. Сравнение 9 х= 6 (mod 12) има решение, тъй като gcd(9, 12) = 3 и 6 се дели на 3. □

Пример 2.11. Сравнение 6x= 9 (mod 12) няма решения, тъй като gcd(6, 12) = 6 и 9 не се дели на 6. □

Теорема 2.5. Нека сравнението (2.2) е разрешимо и д = GCD( а, м). Тогава наборът от решения за сравнение (2.2) се състои от д модулни остатъчни класове T,а именно, ако х 0 - едно от решенията, тогава всички останали решения са

Доказателство.Позволявам х 0 - решение на сравнение (2.2), т.е И , . Значи има такова нещо р, Какво о 0 − b = qm. Сега замествам в последното равенство вместо х 0 произволно решение на формата, където получаваме израза

, делимо на м. □

Пример 2.12. Сравнение 9 х=6 (mod 12) има точно три решения, тъй като gcd(9, 12)=3. Тези решения: х 0 = 2, x 0 + 4 = 6, х 0 + 2∙4=10.□

Пример 2.13. Сравнение 11 х=2 (mod 15) има уникално решение х 0 = 7, тъй като НОД(11,15)=1.□

Ще ви покажем как да решавате сравнения от първа степен. Без загуба на общност ще приемем, че GCD( а, t) = 1. Тогава решението на сравнението (2.2) може да се търси, например, с помощта на Евклидовия алгоритъм. Наистина, използвайки разширения евклидов алгоритъм, ние представяме числото 1 като линейна комбинация от числа аИ T:

Нека умножим двете страни на това равенство по b, получаваме: b = abq + мрб, където abq - b = - мрб, това е а ∙ (bq) = b(мод м) И bq- решение за сравнение (2.2).

Друго решение е да се използва теоремата на Ойлер. Отново вярваме, че GCD(a, T)= 1. Прилагаме теоремата на Ойлер: . Умножете двете страни на сравнението по b: . Пренаписване на последния израз като , получаваме, че това е решение за сравнение (2.2).

Нека сега GCD( а, м) = д>1. Тогава а = аTд, м = мTд, където НОД( А 1 , м 1) = 1. Освен това е необходимо b = b 1 д, за да може сравнението да е разрешимо. Ако х 0 - решение за сравнение А 1 х = b 1 (мод м 1), и единственият, тъй като GCD ( А 1 , м 1) = 1, тогава х 0 ще бъде решението и сравнението А 1 xd = db 1 (мод м 1), това е първоначалното сравнение (2.2). Почивка д- 1 решения се намират по теорема 2.5.

Въведение

§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) е числова. Викат яФункция на Ойлер.

Нека да изберем като представители на класовете остатък по модул t числа 1, ..., t - 1, t. Тогава φ (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)

Сравняване на числа по модул

Изготвил: Ирина Зутикова

MAOU "Лицей № 6"

Клас: 10 "а"

Научен ръководител: Желтова Олга Николаевна

Тамбов

2016

• проблем
• Цел на проекта
• Хипотеза
• Цели на проекта и план за постигането им
• Сравнения и техните свойства
• Примери за задачи и техните решения
• Използвани сайтове и литература

проблем:

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

Цел на проекта:

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

Хипотеза:

По-задълбочено изучаване на темата „Сравняване на числа по модул“ ще помогне на учениците да решат някои нестандартни и олимпиадни задачи.

Цели на проекта и план за постигането им:

1. Проучете подробно темата „Сравнение на числа по модул“.

2. Решаване на няколко нестандартни и олимпиадни задачи чрез сравнение по модул на числа.

3. Създайте бележка за учениците по темата „Сравняване на числа по модул“.

4. Провеждане на урок на тема „Сравняване на числа по модул“ в 10а клас.

5. Дайте на класа домашна работа по темата „Сравнение по модул“.

6. Сравнете времето за изпълнение на задачата преди и след изучаване на темата „Сравнение по модул“.

7. Направете изводи.

Преди да започна да изучавам подробно темата „Сравняване на числа по модул“, реших да сравня как е представена в различни учебници.

• Алгебра и началото на математическия анализ. Напреднало ниво. 10 клас (Ю.М. Колягин и др.)
• Математика: алгебра, функции, анализ на данни. 7 клас (L.G. Peterson и други)
• Алгебра и началото на математическия анализ. Ниво на профил. 10 клас (E.P. Nelin и др.)
• Алгебра и началото на математическия анализ. Ниво на профил. 10 клас (G.K. Muravin и др.)

Както разбрах, някои учебници дори не засягат тази тема, въпреки нивото за напреднали. А темата е представена най-ясно и достъпно в учебника на Л. Г. Питърсън (Глава: Въведение в теорията на делимостта), така че нека се опитаме да разберем „Сравнение на числата по модул“, опирайки се на теорията от този учебник.

Сравнения и техните свойства.

определение: Ако две цели числа a и b имат еднакви остатъци, когато са разделени на някакво цяло число m (m>0), тогава се казва, чеa и b са сравними по модул m, и напишете:

Теорема: тогава и само ако разликата на a и b се дели на m.

Имоти:

1. Рефлексивност на сравненията.Всяко число a е сравнимо със себе си по модул m (m>0; a,m са цели числа).
2. Симетрични сравнения.Ако числото a е сравнимо с числото b по модул m, тогава числото b е сравнимо с числото a по същия модул (m>0; a,b,m са цели числа).
3. Преходност на сравненията.Ако числото a е сравнимо с числото b по модул m, а числото b е сравнимо с числото c по модул на същия модул, тогава числото a е сравнимо с числото c по модул m (m>0; a,b,c ,m са цели числа).
4. Ако числото a е сравнимо с числото b по модул m, то числото aн съпоставими по число bн по модул m(m>0; a,b,m-цели числа; n-естествено число).

Примери за задачи и техните решения.

1. Намерете последната цифра на числото 3 999 .

Решение:

защото Последната цифра на числото е остатъкът при разделяне на 10, тогава

3 999 =3 3 *3 996 =3 3 *(3 4 ) 249 =7*81 249 7(mod 10)

(Тъй като 34=81 1(mod 10);81 n 1(mod10) (по собственост))

Отговор: 7.

2.Докажете, че 2 4n -1 се дели на 15 без остатък. (Phystech2012)

Решение:

защото 16 1(mod 15), тогава

16n-1 0(mod 15) (по свойство); 16n= (2 4) n

2 4n -1 0 (mod 15)

3. Докажете, че 12 2n+1 +11 n+2 Дели се на 133 без остатък.

Решение:

12 2n+1 =12*144 n 12*11 n (mod 133) (по собственост)

12 2n+1 +11 n+2 =12*11 n +11 n *121=11 n *(12+121) =11 n *133

Число (11n *133) се дели на 133 без остатък, следователно (12 2n+1 +11 n+2 ) се дели на 133 без остатък.

4. Намерете остатъка от числото 2 делено на 15 2015 .

Решение:

От 16 1(mod 15), тогава

2 2015 8 (мод. 15)

Отговор:8.

5. Намерете остатъка от деленето на 17-то число 2 2015 г. (Phystech2015)

Решение:

2 2015 =2 3 *2 2012 =8*16 503

От 16 -1(mod 17), тогава

2 2015 -8 (мод. 15)

8 9 (мода 17)

Отговор:9.

6. Докажете, че числото е 11 100 -1 се дели на 100 без остатък. (Phystech2015)

Решение:

11 100 =121 50

121 50 21 50 (mod 100) (по собственост)

21 50 =441 25

441 25 41 25 (mod 100) (по собственост)

41 25 =41*1681 12

1681 12 (-19) 12 (mod 100) (по собственост)

41*(-19) 12 =41*361 6

361 6 (-39) 6 (mod 100) (по собственост)

41*(-39) 6 =41*1521 3

1521 3 21 3 (mod100) (по собственост)

41*21 3 =41*21*441

441 41(mod 100) (по собственост)

21*41 2 =21*1681

1681 -19(mod 100) (по собственост)

21*(-19)=-399

399 1(mod 100) (по собственост)

Така че 11 100 1 (mod 100)

11 100 -1 0(mod 100) (по собственост)

7. Дадени са три числа: 1771,1935,2222. Намерете такова число, че при деление на него остатъците от трите дадени числа ще бъдат равни. (HSE2016)

Решение:

Тогава нека неизвестното число е равно на a

2222 1935 (мод а); 1935 1771 (мод а); 2222 1771 (mod a)

2222-1935 0(moda) (по свойство); 1935-17710(moda) (по свойство); 2222-17710(moda) (по собственост)

287 0 (mod a); 164 0 (mod a); 451 0 (mod a)

287-164 0(moda) (по свойство); 451-2870(moda)(по собственост)

123 0 (mod a); 164 0 (mod a)

164-123 0(mod a) (по свойство)

41

Сравнението от първа степен с едно неизвестно има формата:

f(х) 0 (мод м); f(х) = о + и н. (1)

Решете сравнение- означава намиране на всички стойности на x, които го удовлетворяват. Извикват се две сравнения, които отговарят на еднакви стойности на x еквивалентен.

Ако сравнение (1) е удовлетворено от някое х = х 1, след това (според 49) всички числа, сравними с х 1, по модул м: x x 1 (мод м). Целият този клас числа се счита за едно решение. При такова споразумение може да се направи следният извод.

66.C подравняване (1) ще има толкова решения, колкото е броят на остатъците от пълната система, които го удовлетворяват.

Пример. Сравнение

6х– 4 0 (мод. 8)

Сред числата 0, 1,2, 3, 4, 5, 6, 7 две числа отговарят на пълната система от остатъци по модул 8: х= 2 и х= 6. Следователно това сравнение има две решения:

х 2 (мода 8), х 6 (мод 8).

Сравнението на първа степен чрез преместване на свободния член (с противоположния знак) в дясната страна може да се сведе до формата

брадва b(мод м). (2)

Помислете за сравнение, което отговаря на условието ( А, м) = 1.

Според 66 нашето сравнение има толкова решения, колкото има остатъци от цялата система, които го удовлетворяват. Но когато хминава през пълната система от модулни остатъци T,Че оминава през цялата система от удръжки (от 60). Следователно за една и само една стойност Х,взети от цялата система, още бъде сравнимо с b.Така,

67. Когато (a, m) = 1 брадва за сравнение b(мод м)има едно решение.

нека сега ( а, м) = д> 1. Тогава за сравнение (2) да има решения е необходимо (от 55) това bразделена на д,в противен случай сравнението (2) е невъзможно за всяко цяло число x . Ако приемем следователно bкратни д,нека сложим а = а 1 д, b = b 1 д, м = м 1 д.Тогава сравнение (2) ще бъде еквивалентно на това (съкратено от д): а 1 х b 1 (мод м), в който вече ( А 1 , м 1) = 1, и следователно ще има едно решение по модул м 1 . Позволявам х 1 – най-малкият неотрицателен остатък на това решение по модул m 1 , тогава всички числа са х , образуващи това решение се намират във формата

х х 1 (мод м 1). (3)

По модул m, числата (3) образуват не едно решение, а повече, точно толкова решения, колкото са числата (3) в редицата 0, 1, 2, ..., m – 1 най-малко неотрицателни модулни остатъци м.Но тук ще паднат следните числа (3):

х 1 , х 1 + м 1 , х 1 + 2м 1 , ..., х 1 + (д – 1) м 1 ,

тези. Обща сума дчисла (3); следователно сравнение (2) има дрешения.

Получаваме теоремата:

68. Нека (a, m) = d. Сравнение ax b (мод m) е невъзможно, ако b не се дели на d. Когато b е кратно на d, сравнението има d решения.

69. Метод за решаване на сравнения от първа степен, базиран на теорията на непрекъснатите дроби:

Развиване на връзката в продължителна дроб м:а,

и гледайки последните две съвпадащи дроби:

според свойствата на непрекъснатите дроби (според 30 ) ние имаме

Така че сравнението има решение

за намиране, което е достатъчно за изчисляване P n– 1 по метода, посочен в 30.

Пример. Нека решим сравнението

111х= 75 (мод. 321). (4)

Тук (111, 321) = 3 и 75 е кратно на 3. Следователно сравнението има три решения.

Разделяйки двете страни на сравнението и модула на 3, получаваме сравнението

37х= 25 (mod 107), (5)

които първо трябва да решим. Ние имаме

И така, в този случай н = 4, P n – 1 = 26, b= 25 и имаме решение за сравнение (5) във формата

х–26 ∙ 25 99 (мод. 107).

Следователно решенията за сравнение (4) са представени, както следва:

х 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),

хº99; 206; 313 (мод. 321).

Изчисляване на обратен елемент по зададен модул

70.Ако числата са цели числа аИ нса взаимно прости, тогава има число а′, удовлетворяващ сравнението a ∙ a′ ≡ 1 (мод н). Номер а′Наречен мултипликативно обратно на модул nи нотацията, използвана за него, е а- 1 (мод н).

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

За да намерите решение за сравнение

a∙x≡ 1 (мод м),

Където ( a,m)= 1,

можете да използвате алгоритъма на Евклид (69) или теоремата на Ферма-Ойлер, която гласи, че ако ( a,m) = 1, тогава

а φ( м) ≡ 1(мод м).

х ≡ а φ( м)–1 (мод м).

Групи и техните свойства

Групите са един от таксономичните класове, използвани при класификацията на математически структури с общи характерни свойства. Групите имат два компонента: няколко (Ж) И операции(), дефинирани в този набор.

Понятията множество, елемент и принадлежност са основните недефинирани понятия на съвременната математика. Всяко множество се определя от елементите, включени в него (които от своя страна също могат да бъдат множества). Така казваме, че едно множество е дефинирано или дадено, ако за всеки елемент можем да кажем дали принадлежи към това множество или не.

За два комплекта А, Бзаписи б А, б А, б∩ А, б А, б \ А, А × бсъответно означават това бе подмножество на множеството А(т.е. всеки елемент от бсъщо се съдържа в А, например множеството от естествени числа се съдържа в множеството от реални числа; освен това винаги А А), бе правилно подмножество на множеството А(тези. б АИ б ≠ А), пресечна точка на много бИ А(т.е. всички такива елементи, които се намират едновременно в А, и в б, например пресечната точка на цели числа и положителни реални числа е набор от естествени числа), обединението на множества бИ А(т.е. набор, състоящ се от елементи, които се намират или в А, или в б), задайте разлика бИ А(т.е. набор от елементи, които се намират в б, но не лягайте А), декартово произведение на множества АИ б(т.е. набор от двойки от формата ( а, b), Където а А, b б). Чрез | А| силата на множеството винаги се обозначава А, т.е. брой елементи в комплекта А.

Операцията е правило, според което всеки два елемента от множество Ж(аИ b) съвпада с третия елемент от G: а б.

Много елементи Жс операция се нарича група, ако са изпълнени следните условия.