Решавање споредби од прв степен. Решавање на конгруенции и нивна примена Деливост и споредби на модули

Содржина.

Вовед

§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. Претворање на обична дропка во конечна

децимална дропка

Заклучок

Литература

Вовед

Во нашиот живот честопати треба да се занимаваме со цели броеви и задачи поврзани со нив. Во оваа теза ја разгледувам теоријата на споредба на цели броеви.

Два цели броја чија разлика е множител на даден природен бројм се нарекуваат споредливи модулим.

Зборот „модул“ доаѓа од латинскиот модул, што на руски значи „мерење“, „вредност“.

Исказот „a е складен со b modulo m“ обично се пишува како ab (mod m) и се нарекува споредба.

Дефиницијата за споредба беше формулирана во книгата на К. Гаус „Аритметички истражувања“. Ова дело, напишано на латински, започнало да се печати во 1797 година, но книгата била објавена дури во 1801 година поради фактот што процесот на печатење во тоа време бил исклучително макотрпен и долг. Првиот дел од книгата на Гаус е наречен „За споредбата на броевите воопшто“.

Споредбите се многу погодни за употреба во оние случаи кога е доволно да се знаат во секое истражување броеви до множители на одреден број.

На пример, ако нè интересира со која цифра завршува коцката на цел број a, тогаш доволно е да знаеме само до множители на 10 и можеме да користиме споредбен модуло 10.

Целта на оваа работа е да се разгледа теоријата на споредби и да се проучат главните методи за решавање споредби со непознати, како и да се проучува примената на теоријата на споредби во училишната математика.

Тезата се состои од три поглавја, а секое поглавје е поделено на параграфи, а параграфи во параграфи.

Првото поглавје се занимава со општи прашања од теоријата на споредби. Овде го разгледуваме концептот на модуло споредба, својствата на споредбите, целосниот и редуциран систем на остатоци, Ојлеровата функција, Ојлеровата и Ферматовата теорема.

Второто поглавје е посветено на теоријата на споредби со непознатото. Ги истакнува основните концепти поврзани со решението на споредбите, разгледува методи за решавање споредби од прв степен (метод на селекција, Ојлеровиот метод, Евклидовиот алгоритам метод, методот на продолжени дропки, користење на индекси), системи на споредби од прв степен со една непозната, споредби на повисоки степени итн.

Третото поглавје содржи неколку примени на теоријата на броеви во училишната математика. Се разгледуваат знаците на деливост, проверка на резултатите од дејствата, претворање на обичните дропки во систематски децимални дропки.

Презентирањето на теоретскиот материјал е проследено со голем број примери кои ја откриваат суштината на воведените поими и дефиниции.

Поглавје 1. Општи прашања на теоријата на споредби

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

Нека z-прстен од цели броеви, m-фиксен цел број и m z-множество од сите цели броеви деливи со m.

Дефиниција 1. Два цели броја a и b се вели дека се складни модуло m ако m го дели a-b.

Ако броевите a и b се споредливи модуло m, тогаш запишете aб (мод м).

Состојба а 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=mq1+r,(1)

B=mq2+r, (2)

Каде 0≤r≥m.

Одземаме (2) од (1), добиваме a-b= m(q1- q2), т.е. a-b m или a b (мод 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

gcd(4,10) = 2, gcd(25,10) = 5, така што нашата споредба е погрешна.

§2. Својства за споредба

1. Споредбени својства независни од модул.

Многу својства на споредбите се слични на оние на еднаквостите.

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

В) симетрија: ако а b (mod m), потоа b a (mod m);

В) транзитивност: ако а 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 (мод m).

Примери.

Најдете остаток при делењево 13.

Решение: -1 (мод 13) и 1 (мод 13), потоа (-1)+1 0 (мод 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 (мод m).

1. (последица на својствата 1, 2, 3). Можете да додадете ист цел број на двата дела од споредбата.

Доказ.

Нека а b (mod m) и k е кој било цел број. Со својството на рефлексивност

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

Последица. Двата дела од споредбата може да се подигнат на иста цел број ненегативна моќност: ако ab (mod m) и s е ненегативен цел број, а потоа a s b s (мод m).

Примери.

Решение: очигледно 13 1 (мод 3)

2-1 (мод 3)

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

- 1-1 0 (мод 13)

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

Решение:

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

1+ =1+ 1+ =

Бидејќи 27 е 1 (мод 13), следува дека 1+ 1+1 3+1 9 (мод 13).

h.t.d.

3. Најдете го остатокот при делење со остатокот од бројна 24.

Имаме: 1 (мод 24), значи

1 (мод 24)

Додавајќи 55 на двата дела од споредбата, добиваме:

(мод 24).

Имаме: (мод 24), така

(мод 24) за кое било k є N.

Оттука (мод 24). Од (-8)16 (мод 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 (мод 7), односно 196 7.

1. И двата дела на споредбата и модулот може да се помножат со истиот позитивен цел број.

Доказ.

Нека a b (mod m ) и c е позитивен цел број. Тогаш a-b = mt и ac-bc=mtc, или acп.н.е. (mod mc).

Пример.

Проверете дали вредноста на изразот ецел број.

Решение:

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

1 (мод 9)

31 (мод 27)

Ги додаваме овие споредби термин по член (својство 2), добиваме 124(мод 27) Гледаме дека 124 не е цел број делив со 27, па оттука и вредноста на изразотисто така не е цел број.

1. Двата дела од споредбата може да се поделат со нивниот заеднички фактор ако е релативно прв на модулот.

Доказ.

Ако околу cb (mod m), т.е. m/c(a-b) и бројСо копримерок на m, (c,m)=1, потоа m дели a-b. Оттука, a b (мод т ).

Пример.

60 9 (мод 17), откако ќе ги поделиме двата дела од споредбата со 3, добиваме:

20 (мод 17).

Општо земено, невозможно е двата дела од споредбата да се поделат со број кој не е копрост со модулот, бидејќи по делењето може да се добијат броеви кои се неспоредливи во овој модул.

Пример.

8 (мод 4) но 2 (мод 4).

1. И двата дела на споредбата и модулот може да се поделат со нивниот заеднички делител.

Доказ.

Ако ка kb (mod km), тогаш k (a-b) се дели со km. Според тоа, a-b е делив со m, т.е a b (мод т ).

Доказ.

Нека P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n . Според условот a b (мод 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 (а) P(b) (mod m). Ако a (mod m) и c i d i (mod m), 0 ≤ i ≤ n, тогаш

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

Во исто време, треба да се обрне внимание на фактот дека експонентите што се среќаваат во споредбите не можат да се заменат на овој начин: од

a n c(mod m) и n k(mod m) не значи дека aк со (мод м).

Имотот 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 (мод 3), потоа според својството 10 f (10) f(1) (мод 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 (мод 3), т.е., за N да се дели со 3, потребно е и доволно збирот на цифрите на овој број да се дели со 3.

§3. Системи за одбивање

1. Комплетен систем за наплата.

Еквидалечните броеви или, што е исто, споредливиот модуло m, формираат класа на броеви модуло m.

Од оваа дефиниција произлегува дека истиот остаток r одговара на сите броеви од класата, а сите броеви од класата ги добиваме ако го принудиме q да помине низ сите цели броеви во форма mq + r.

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

Секој број на класа се нарекува резидуален модуло m во однос на сите броеви од иста класа. Остатокот добиен при q=0, еднаков на остатокот r, се нарекува најмал ненегативен остаток.

Остатокот ρ, најмал по апсолутна вредност, се нарекува апсолутно најмал остаток.

Очигледно, за r имаме ρ=r; кога r> имаме ρ=r-m; конечно, ако m е парен и r=, тогаш за ρ може да се земе кој било од двата бројаи -m= - .

Ние избираме од секоја класа на модули за остатоциТ со еден број. Добијте m цели броеви: x 1 ,…, x m . Се нарекува множеството (x 1, ..., x t). комплетен систем на остатоци modulo m.

Бидејќи секоја класа содржи неброиво збир на остатоци, можно е да се состави неброиво збир од различни целосни системи на остатоци модуло m, од кои секоја содржит одбитоци.

Пример.

Составете неколку целосни системи на модули за остатоциТ = 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, т -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 ,…,х m (1)

парно неспоредлив модуло м, формира целосен систем на остатоци модуло м.

Доказ.

1. Секој од броевите во множеството (1) припаѓа на некоја класа.
2. Било кои два броја x i и x j од (1) се неспоредливи меѓу себе, т.е. припаѓаат на различни класи.
3. Севкупно, има m броеви во (1), т.е. колку што има модуло за класиТ.

x 1, x 2,…, x t е комплетен систем на остатоци modulo m.

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

Доказ.

Да се ​​разгледа

Axe 1 + b, ax 2 + b, ..., ax m + b (2)

1. Секој од броевите во множеството (2) припаѓа на некоја класа.
2. Било кои два броја ax i +b и ax j + b од (2) се неспоредливи меѓу себе, односно припаѓаат на различни класи.

Навистина, ако има два броја во (2) такви што

секира i + б секира ј + б (mod m), (i = j), тогаш ќе добиемесекира и секира ј (мод м). Бидејќи (а, т) = 1, тогаш својството на споредби може да ги намали двата дела од споредбата заА . Добиваме x i x j (mod m).

По услов, x i x j (mod m) за (i = j) , бидејќи x 1 , x 2 , ..., x m - целосен систем на одбитоци.

1. Множеството броеви (2) содржиТ броеви, односно колку што има класи модуло m.

Значи, секира 1 + б, секира 2 + б, ..., секира м + 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: акоа б (mod m), потоа (a, m) = (b, m).

Доказ.

Нека a b (мод m). Тогаш a = b + mt, каде т з. Од оваа еднаквост произлегува дека (а, m) = (b, m).

Навистина, нека δ-заеднички делител на 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. Најголем заеднички делител на модулт и кој било број a од оваа класа на одбитоци заТ наречен најголем заеднички делителТ и оваа класа на остатоци.

Дефиниција 2. Класа на остатоци a modulo m се нарекува коприм со модулом ако најголемиот заеднички делитела и т е еднакво на 1 (односно, ако m и кој било број од a се сопрост).

Пример.

Нека т = 6. Класата на остатоци 2 се состои од броеви (..., -10, -4, 2, 8, 14, ...). Најголемиот заеднички делител на кој било од овие броеви и модул 6 е 2. Оттука, (2, 6) = 2. Најголемиот заеднички делител на кој било број од класата 5 и модулот 6 е ​​1. Оттука, класата 5 е релативно прост до модулот 6.

Дозволете ни да одбереме од секоја класа на остатоци коприм со модуло m еден број. Добиваме систем на одбитоци, кој е дел од целосниот систем на одбитоци. Ја викаатредуциран систем на остатоци modulo m.

Дефиниција 3. Множеството на остатоци модуло m, земено едно по едно од секоја коприм соТ класа на остатоци модуло овој модул се нарекува систем со намалени остатоци.

Дефиницијата 3 подразбира метод за добивање на намален систем на модули на остатоциТ: потребно е да се напише некој целосен систем на остатоци и од него да се отстранат сите остатоци што не се комплементарни со m. Преостанатиот сет на одбитоци е намалениот систем на одбитоци. Очигледно има бесконечен број на намалени системи на остатоци modulo m.

Ако за почетен го земеме целосниот систем на најмалку ненегативни или апсолутно најмали остатоци, тогаш на посочениот начин го добиваме соодветно намалениот систем на најмалку ненегативни или апсолутно најмали остатоци модуло m.

Пример.

Доколку Т = 8, потоа 1, 3, 5, 7 - намален систем на најмалку ненегативни остатоци, 1, 3, -3, -1- намален систем на апсолутно најмалку остатоци.

Теорема 2.

Нека бројот на класи релативно прости на m е еднаков на k.Потоа која било збирка од k цели броеви

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

Доказ

А) Секој број во множеството (1) припаѓа на некоја класа.

1. Сите броеви од (1) се неспоредливи модули по паровиТ, односно припаѓаат на различни класи modulo m.
2. Секој број од (1) е копрост соТ, односно сите овие броеви припаѓаат на различни класи копримерни со модул m.
3. Вкупно, (1) имак броеви, односно онолку колку што треба да содржи намалениот систем на остатоци модуло m.

Затоа, множеството броеви(1) - намален систем на резидуи модулоТ.

§4. Ојлерова функција.

Ојлерови и Ферматови теореми.

1. Ојлерова функција.

Означи со φ(Т) бројот на класи на остатоци модуло m коприм со m, односно бројот на елементи на намалениот систем на остатоци модулот. Функција φ (t) е нумеричка. Ја викаатОјлерова функција.

Избираме како претставници на модуло на класите на остатоци t броеви 1, ... , t - 1, t. Потоа φ (t) е бројот на таквите броеви со копромит t. Со други зборови, φ (t) - бројот на позитивни броеви што не надминуваат m и релативно прости до m.

Примери.

1. Нека т = 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.

На т = 1, целосниот систем на остатоци се состои од една класа 1. Заедничкиот природен делител на броевите 1 и 1 е 1, (1, 1) = 1. Врз основа на тоа, ставаме φ(1) = 1.

Ајде да продолжиме со пресметката на Ојлеровата функција.

1) Ако m = стр е прост број, а потоа φ(p) = p- 1.

Доказ.

Остатоци 1, 2, ... , стр-1 а само тие се копрости со прост бројР. Затоа φ (p) = p - 1.

2) Ако m = p k - моќност на прост бројстр, тогаш

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

Доказ.

Комплетен систем на модули за остатоци t = p k се состои од броеви 1,..., p k - 1, p k природни делителиТ се степениР. Затоа бројот Аможе да има заеднички делител со m различен од 1, само когаАподелено соР.Но, меѓу броевите 1, ... , стрк -1 наРделејќи само броевистр, 2p, ... , стр2 , ... РДо, чиј број еРДо: p = стрк-1. Оттука, coprime соt = стрДоодморРДо- Рк-1=стрkl(стр-1)броеви. Така, се докажува дека

φ (РДо) = стрк-1(r-1).

Теорема1.

Ојлеровата функција е мултипликативна, односно за сопростите броеви m и n имаме φ (mn) = φ(m) φ (n).

Доказ.

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

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

Наредете го целосниот систем на модули за остатоциtpкакоПXТ -матрици

1 2 Т

t+1 t+2 2 т

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

(P -1) t+1 (P -1) m +2 петок

Затоа штоТИПкопример, потоа бројотXмеѓусебно едноставно соtpако и само акоXмеѓусебно едноставно соТИXмеѓусебно едноставно соП. Но, бројотkm + tмеѓусебно едноставно соТако и само акотмеѓусебно едноставно соТ.Затоа, броевите релативно прости до m се наоѓаат во оние колони за коитпоминува низ намалениот систем на резидуи модулоТ.Бројот на таквите колони е φ(Т).Секоја колона го прикажува целосниот систем на модули за остатоциП.Од овие остатоци φ(P)coprime соП.Оттука, вкупниот број на броеви копрости и соТи со n, е еднакво на φ(Т)φ(n)

(φ (Т)колони, од кои секоја зема φ(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)=.

Но, според формулата (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.

Одговор:x= 143

2. Ојлеровата теорема и Фермат.

Во теоријата на споредби, Ојлеровата теорема игра важна улога.

Ојлерова теорема.

Ако цел број a е релативно прост на m, тогаш

(1)

Доказ.Нека

(2)

е редуциран систем на остатоци modulo m.

Акоае цел број релативно прост на m, тогаш

(3)

Во n тие го даваат истиот остаток.

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

Изјавата „a и b се складни модуло n“ е напишана како:

Својства за еднаквост на модуло

Модуло споредбената релација ги има својствата

Било кои два цели броја аИ бсе споредливи модуло 1.

Со цел за бројките аИ ббеа споредливи модули n, потребно е и доволно нивната разлика да се дели со n.

Ако броевите и се споредливи модуло по парови n, потоа нивните суми и , како и производите и се исто така споредливи модули n.

Ако бројките аИ бспоредлив модул n, потоа нивните дипломи а кИ б ксе исто така споредливи модули nза секој природен к.

Ако бројките аИ бспоредлив модул n, И nподелено со м, Тоа аИ бспоредлив модул м.

Со цел за бројките аИ ббеа споредливи модули n, претставена како негово канонско распаѓање на прости множители стр јас

неопходно и доволно за да

Споредбената релација е еквивалентна релација и има многу од својствата на обичните еднаквости. На пример, тие можат да се собираат и множат: ако

Споредбите, сепак, не можат, општо земено, да се поделат една со друга или со други броеви. Пример: , сепак, намалувајќи за 2, добиваме погрешна споредба: . Правилата за намалување за споредби се како што следува.

Исто така, не можете да вршите операции на споредби ако нивните модули не се совпаѓаат.

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

Поврзани дефиниции

Часови за одбивање

Множеството на сите броеви споредливи со амодуло nповикани одбитна класа амодуло n , и обично се означува со [ а] nили . Така, споредбата е еквивалентна на еднаквоста на класите на остатоци [а] n = [б] n .

Бидејќи модуло споредба nе еквивалентна врска на множеството цели броеви, потоа класите на остаток модуло nсе еквивалентни класи; нивниот број е n. Множество од модуло од сите класи на остатоци nозначено со или .

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

[а] n + [б] n = [а + б] n

Во однос на овие операции, множеството е конечен прстен, и ако nедноставно - конечно поле .

Системи за одбивање

Системот за остаток ви овозможува да вршите аритметички операции на конечно множество броеви без да одите подалеку од него. Комплетен систем на одбитоци modulo n е секое множество од n цели броеви кои се неспоредливи модуло n. Вообичаено, како целосен систем на модули на остатоци, се земаат најмалите не-негативни остатоци

0,1,...,n − 1

или апсолутно најмали остатоци што се состојат од броеви

,

во случај на непарни nи бројки

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

Одлука за споредба

Споредби од прв степен

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

Решението на ваквата споредба започнува со пресметката на gcd (а, м)=г. Во овој случај, можни се 2 случаи:

• Ако бне повеќекратна г, тогаш споредбата нема решенија.
• Ако бповеќекратни г, тогаш споредбата има единствен модуло за решение м / г, или, што е исто, гмодуло решенија м. Во овој случај, како резултат на намалување на оригиналната споредба со гспоредбени резултати:

Каде а 1 = а / г , б 1 = б / г И м 1 = м / г се цели броеви и а 1 и м 1 се компактни. Затоа бројот а 1 може да се преврти модуло м 1, односно најдете таков број втоа (со други зборови, ). Сега решението се наоѓа со множење на добиената споредба со в:

Практична пресметка на вредноста вможе да се направи на различни начини: користејќи ја теоремата на Ојлер, Евклидовиот алгоритам, теоријата на продолжени дропки (види алгоритам) итн. Особено, теоремата на Ојлер ви овозможува да ја напишете вредноста вкако:

Пример

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

Бидејќи 2 е релативно прост на модуло 11, можеме да ги намалиме левата и десната страна за 2. Како резултат на тоа, добиваме едно решение модуло 11: , што е еквивалентно на две решенија модуло 22: .

Споредби од втор степен

Решавањето на споредбите на вториот степен се сведува на откривање дали даден број е квадратен остаток (со користење на законот за квадратен реципроцитет) и потоа пресметување на квадратниот корен модуло.

Приказна

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

Размислете за споредба на формата x 2 ≡а(мод стрα), каде стре едноставен непарен број. Како што е прикажано во Дел 4 §4, решението за оваа конгруенција може да се најде со решавање на конгруентноста x 2 ≡а(мод стр). И споредбата x 2 ≡а(мод стрα) ќе има две решенија ако ае квадратен резидуален модул стр.

Пример:

Решавање на квадратна споредба x 2 ≡86 (мод 125).

125 = 5 3 , 5 е прост број. Ајде да провериме дали 86 е квадратен модуло 5.

Оригиналната споредба има 2 решенија.

Ајде да најдеме споредбено решение x 2 ≡86 (мод 5).

x 2 ≡1 (мод 5).

Оваа споредба може да се реши на начин наведен во претходниот пасус, но ќе го искористиме фактот дека квадратниот корен на 1 модул е ​​±1, а споредбата има точно две решенија. Така, решението за конгруентност модуло 5 е

x≡±1 (мод 5) или, во спротивно, x=±(1+5 т 1).

Заменете го добиеното решение во споредбениот модул 5 2 =25:

x 2 ≡86 (мод 25)

x 2 ≡11 (мод 25)

(1+5т 1) 2 ≡11 (мод 25)

1+10т 1 +25т 1 2 ≡11 (мод 25)

10т 1 ≡10 (мод 25)

2т 1 ≡2 (мод 5)

т 1 ≡1 (мод 5), или еквивалентно, т 1 =1+5т 2 .

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

x 2 ≡86 (мод 125)

(6+25т 2) 2 ≡86 (мод 125)

36+12 25 т 2 +625т 2 2 ≡86 (мод 125)

12 25 т 2 ≡50 (мод 125)

12т 2 ≡2 (мод 5)

2т 2 ≡2 (мод 5)

т 2 ≡1 (мод 5), или т 2 =1+5т 3 .

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

Одговор: x≡±31 (мод 125).

Размислете сега за споредба на формата x 2 ≡а(mod2α). Ваквата споредба не секогаш има две решенија. За таков модул, можни се следниве случаи:

1) α=1. Тогаш споредбата има решение само кога а≡1 (мод 2), а решението е x≡1 (мод 2) (едно решение).

2) α=2. Споредбата има решенија само кога а≡1 (мод 4), а решението е x≡±1 (мод 4) (две решенија).

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

Пример:

Решавање на споредба x 2 ≡33 (мод 64)

64=26. Ајде да провериме дали оригиналната споредба има решение. 33≡1(мод 8), па споредувањето има 4 решенија.

Modulo 8 овие решенија ќе бидат: x≡±1 (мод 8) и x≡±3 (мод 8), што може да се претстави како x=±(1+4 т 1). Заменете го овој израз во споредбениот модул 16

x 2 ≡33 (мод 16)

(1+4т 1) 2 ≡1 (мод 16)

1+8т 1 +16т 1 2 ≡1 (мод 16)

8т 1 ≡0 (мод 16)

т 1 ≡0 (мод 2)

Тогаш решението ќе добие форма x=±(1+4 т 1)=±(1+4(0+2 т 2))=±(1+8 т 2). Заменете го добиеното решение во модулот на конгруентност 32:

x 2 ≡33 (мод 32)

(1+8т 2) 2 ≡1 (мод 32)

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

16т 2 ≡0 (мод 32)

т 2 ≡0 (мод 2)

Тогаш решението ќе добие форма x=±(1+8 т 2) =±(1+8(0+2t 3)) =±(1+16 т 3). Заменете го добиеното решение во споредбениот модул 64:

x 2 ≡33 (мод 64)

(1+16т 3) 2 ≡33 (мод 64)

1+32т 3 +256т 3 2 ≡33 (мод 64)

32т 3 ≡32 (мод 64)

т 3 ≡1 (мод 2)

Тогаш решението ќе добие форма x=±(1+16 т 3) =±(1+16(1+2t 4)) =±(17+32 т 4). Значи, модуло 64, оригиналната споредба има четири решенија: x≡±17 (мод 64) и x≡±49 (мод 64).

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

Ако секоја споредба на овој систем може да се реши, тогаш целиот систем може да се реши. Откако го најдовме решението за секоја споредба на овој систем, добиваме систем на споредби од прв степен, решавајќи го, користејќи ја кинеската теорема за остаток, го добиваме решението на првобитната споредба. Покрај тоа, бројот на различни решенија на првобитната споредба (ако е решлив) е 2 к, ако α=1, 2 к+1 ако α=2, 2 к+2 ако α≥3.

Пример:

Решавање на споредба x 2 ≡4 (мод 21).

Споредба со една непозната xја има формата

Каде. Ако а n не се дели со м, тогаш се нарекува степенспоредби.

Одлукаспоредба е кој било цел број x 0 , за кои

Ако X 0 ја задоволува споредбата, тогаш, според својството 9 на споредбите, оваа споредба ќе ги задоволи сите цели броеви споредливи со x 0 модуло м. Затоа, сите споредбени решенија кои припаѓаат на истата класа на модуло-остатоци Т, ќе го разгледаме како едно решение. Така, споредбата има онолку решенија колку што има елементи од целосниот систем на остатоци што ја задоволуваат.

Се нарекуваат споредби чии множества решенија се исти еквивалент.

2.2.1 Споредби од прв степен

Споредба на прв степен со една непозната Xја има формата

(2.2)

Теорема 2.4. За споредба да има барем едно решение, потребно е и доволно бројот б поделено со GCD( а, м).

Доказ.Прво ја докажуваме неопходноста. Нека г = GCD( а, м) И X 0 - споредбено решение. Потоа , односно разликата О 0 − б поделено со Т.Значи има цел број q, Што О 0 − б = qm. Од тука б= ах 0 − qm. И бидејќи г, како заеднички делител, дели броеви АИ Т,тогаш минуендот и подтрахендот се делат со г, и оттука б поделено со г.

Сега да ја докажеме доволноста. Нека г- најголем заеднички делител на броеви АИ Т,И б поделено со г. Потоа, според дефиницијата за деливост, постојат цели броеви а 1 , б 1 , Т 1 , Што .

Користејќи го проширениот Евклидов алгоритам, наоѓаме линеарна претстава на бројот 1 = gcd( а 1 , м 1 ):

за некои x 0 , y 0 . Ги множиме двата дела од последното равенство со б 1 г:

или, што е исто,

,

односно , и е решението на споредбата. □

Пример 2.10. Споредба 9 X= 6 (мод 12) има решение бидејќи gcd(9, 12) = 3 и 6 е делив со 3. □

Пример 2.11. Споредба 6x= 9 (мод 12) нема решенија бидејќи gcd(6, 12) = 6 и 9 не е делив со 6. □

Теорема 2.5. Нека конгруентноста (2.2) може да се реши и г = GCD( а, м). Тогаш множеството споредбени решенија (2.2) се состои од г модуло класи на остатоци Т,имено, ако X 0 е едно од решенијата, тогаш сите други решенија се

Доказ.Нека X 0 е решението за споредба (2.2), т.е. И , . Значи има и такво q, Што О 0 − б = qm. Замена сега во последната еднаквост наместо X 0 произволно решение на формата, каде што го добиваме изразот

, делив со м. □

Пример 2.12. Споредба 9 X=6 (мод 12) има точно три решенија бидејќи gcd(9, 12)=3. Овие решенија се: X 0 \u003d 2, x 0 + 4 \u003d 6, X 0 + 2∙4=10.□

Пример 2.13. Споредба 11 X=2 (мод 15) има уникатно решение X 0 = 7 бидејќи gcd(11,15)=1.□

Дозволете ни да покажеме како да се реши споредбата од прв степен. Без губење на општоста, ќе претпоставиме дека GCD( а, т) = 1. Тогаш може да се бара решението на конгруентноста (2.2), на пример, со користење на Евклидов алгоритам. Навистина, користејќи го проширениот Евклидов алгоритам, го претставуваме бројот 1 како линеарна комбинација на броеви аИ Т:

Помножете ги двете страни на оваа равенка со б, добиваме: б = abq + мрб, каде abq - б = - мрб, тоа е а ∙ (bq) = б(мод м) И bqе решението за споредба (2.2).

Друг начин за решавање е да се користи Ојлеровата теорема. Повторно, претпоставуваме дека GCD(a, Т)= 1. Ја применуваме Ојлеровата теорема: . Помножете ги двете страни на споредбата со б: . Препишување на последниот израз како , добиваме дека е решението на конгруенција (2.2).

Ајде сега GCD( а, м) = г>1. Потоа а = атг, м = мтг, каде gcd( А 1 , м 1) = 1. Покрај тоа, потребно е б = б 1 г, за споредбата да биде решлива. Ако X 0 - споредбено решение А 1 x = б 1 (мод м 1), и единствениот, бидејќи GCD ( А 1 , м 1) = 1, тогаш X 0 ќе биде одлуката и споредбата А 1 xd = db 1 (мод м 1), односно оригиналната споредба (2.2). Одмор г- 1 решенија се најдени со теорема 2.5.

Модуло за споредување на броеви

Проект подготвен од: Ирина Жутикова

MAOU "Лицеум №6"

Класа: 10 "а"

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

Тамбов

2016

• Проблем
• Цел на проектот
• Хипотеза
• Цели на проектот и план за нивно постигнување
• Споредби и нивните својства
• Примери на задачи и нивни решенија
• Користени страници и литература

Проблем:

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

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

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

Хипотеза:

Подлабоко проучување на темата „Модуло споредување на броеви“ ќе им помогне на учениците да решат некои нестандардни и олимпијадни задачи.

Цели на проектот и план за нивно постигнување:

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

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

3.Креирај белешка за учениците на тема „Споредба на броеви модуло“.

4. Спроведување на час на тема „Модуло споредување на броеви“ во класа 10 „а“.

5. Зададете домашна задача на часот на тема „Споредба на модули“.

6. Споредете го времето на завршување на задачата пред и по изучувањето на темата „Споредба на модуло“.

7. Извлечете заклучоци.

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

• Алгебра и почеток на математичка анализа. Длабоко ниво. 10 одделение (Ју.М. Кољагин и други)
• Математика: алгебра, функции, анализа на податоци. 7 одделение (Л.Г. Петерсон и други)
• Алгебра и почеток на математичка анализа. ниво на профил. Одделение 10 (Е.П. Нелин и други)
• Алгебра и почеток на математичка анализа. ниво на профил. 10 одделение (Г.К. Муравин и други)

Како што дознав, во некои учебници оваа тема не се ни допира, и покрај длабинското ниво. А најразбирливата и најпристапната тема е претставена во учебникот од Л.Г.

Споредби и нивните својства.

Дефиниција: Ако два цели броеви 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 (m>0; a,b,m се цели броеви).
3. Транзитивност на споредбите.Ако бројот a е складен на b модуло m, а b е складен на c модуло m, тогаш a е складен на c модуло m(m>0; a,b,c,m се цели броеви).
4. Ако бројот a е складен со бројот b модуло m, тогаш бројот a n споредлив со бројот б n модуло 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 (мод 10)

(Бидејќи 34=81 1 (мод 10);81 n 1 (mod10) (по имот))

Одговор: 7.

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

Решение:

Бидејќи 16 1 (мод 15), тогаш

16n-1 0 (мод 15) (по имот); 16n= (2 4) n

2 4n -1 0 (мод 15)

3. Докажи дека 12 2n+1 +11n+2 делив без остаток со 133.

Решение:

12 2n+1 =12*144n 12*11n (мод 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 +11n+2 ) се дели со 133 без остаток.

4. Најдете го остатокот од делењето со 15 од бројот 2 2015 .

Решение:

Од 16 1 (мод 15), тогаш

2 2015 8 (мод 15)

Одговор: 8.

5. Најдете го остатокот од делењето со 17 од бројот 2 2015 година. (Phystech 2015)

Решение:

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

Од 16 -1 (мод 17), тогаш

2 2015-8 (мод 15)

8 9 (мод 17)

Одговор: 9.

6. Докажете дека бројот е 11 100 -1 се дели со 100 без остаток. (Phystech 2015)

Решение:

11 100 =121 50

121 50 21 50 (мод 100) (по имот)

21 50 =441 25

441 25 41 25 (мод 100) (по имот)

41 25 =41*1681 12

1681 12 (-19) 12 (мод 100) (по имот)

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

361 6 (-39) 6 (мод 100) (по имот)

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

1521 3 21 3 (mod100) (по имот)

41*21 3 =41*21*441

441 41 (мод 100) (по имот)

21*41 2 =21*1681

1681 -19 (мод 100) (по имот)

21*(-19)=-399

399 1 (мод 100) (по имот)

Значи 11 100 1 (мод 100)

11 100 -1 0 (мод 100) (по имот)

7. Дадени се три броја: 1771,1935,2222. Најдете го бројот што кога ќе се подели со кој остатокот од трите дадени броеви ќе биде еднаков. (HSE2016)

Решение:

Нека непознатиот број е еднаков на a, тогаш

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

2222-1935 0 (мода) (сопственост); 1935-1771 година0 (мода) (по имот); 2222-1771 година0 (мода) (по имот)

287 0 (мод а); 164 0 (мод а); 451 0 (мод а)

287-164 0 (мода) (по имот); 451-2870 (мода) (по имот)

123 0 (мод а); 164 0 (мод а)

164-123 0 (мод а) (својство)

41

HSE Олимпијада 2016 година