Kutatua mifano ya modulo za kulinganisha. Ulinganisho wa modulo

Kulinganisha moduli ya nambari

Imetayarishwa na: Irina Zutikova

MAOU "Lyceum No. 6"

Darasa: 10 "a"

Msimamizi wa kisayansi: Zheltova Olga Nikolaevna

Tambov

2016

• Tatizo
• Lengo la mradi
• Nadharia
• Malengo ya mradi na mpango wa kuyafikia
• Ulinganisho na mali zao
• Mifano ya matatizo na ufumbuzi wao
• Maeneo yaliyotumika na fasihi

Tatizo:

Wanafunzi wengi mara chache hutumia ulinganishi wa modulo wa nambari kutatua kazi zisizo za kawaida na za olimpidi.

Lengo la mradi:

Onyesha jinsi unavyoweza kutatua kazi zisizo za kawaida na za olympiad kwa kulinganisha modulo ya nambari.

Nadharia:

Utafiti wa kina wa mada "Kulinganisha modulo ya nambari" utasaidia wanafunzi kutatua baadhi ya kazi zisizo za kawaida na za olympiad.

Malengo ya mradi na mpango wa kuyafikia:

1. Jifunze kwa undani mada "Ulinganisho wa nambari za modulo".

2. Tatua kazi kadhaa zisizo za kawaida na za olympiad kwa kutumia modulo ya kulinganisha nambari.

3.Unda memo kwa wanafunzi kuhusu mada "Kulinganisha modulo ya nambari."

4. Endesha somo kuhusu mada "Kulinganisha modulo ya nambari" katika daraja la 10 "a".

5. Lipe darasa kazi ya nyumbani juu ya mada "Kulinganisha kwa moduli."

6.Linganisha muda wa kukamilisha kazi kabla na baada ya kujifunza mada "Kulinganisha na Moduli".

7.Fanya hitimisho.

Kabla ya kuanza kujifunza kwa undani mada "Kulinganisha nambari za modulo", niliamua kulinganisha jinsi inavyowasilishwa katika vitabu mbalimbali vya kiada.

• Algebra na mwanzo wa uchambuzi wa hisabati. Kiwango cha juu. Daraja la 10 (Yu.M. Kolyagin na wengine)
• Hisabati: algebra, kazi, uchambuzi wa data. Darasa la 7 (L. G. Peterson na wengine)
• Algebra na mwanzo wa uchambuzi wa hisabati. Kiwango cha wasifu. Daraja la 10 (E.P. Nelin na wengine)
• Algebra na mwanzo wa uchambuzi wa hisabati. Kiwango cha wasifu. Daraja la 10 (G.K. Muravin na wengine)

Kama nilivyogundua, vitabu vingine vya kiada havigusi hata mada hii, licha ya kiwango cha juu. Na mada imewasilishwa kwa njia iliyo wazi zaidi na inayoweza kupatikana katika kitabu cha kiada na L.G Peterson (Sura: Utangulizi wa nadharia ya mgawanyiko), kwa hivyo hebu tujaribu kuelewa "Ulinganisho wa modulo ya nambari", tukitegemea nadharia kutoka kwa kitabu hiki.

Ulinganisho na mali zao.

Ufafanuzi: Ikiwa nambari mbili kamili a na b zina masalio sawa zinapogawanywa na nambari kamili ya m (m>0), basi wanasema hivyo.a na b zinalinganishwa modulo m, na kuandika:

Nadharia: ikiwa na tu ikiwa tofauti ya a na b inaweza kugawanywa na m.

Sifa:

1. Reflexivity ya kulinganisha.Nambari yoyote a inalinganishwa na yenyewe modulo m (m>0; a,m ni nambari kamili).
2. Ulinganisho wa ulinganifu.Ikiwa nambari a inalinganishwa na nambari b modulo m, basi nambari b inalinganishwa na nambari a modulo sawa (m>0; a,b,m ni nambari kamili).
3. Transitivity ya kulinganisha.Ikiwa nambari a inalinganishwa na nambari b modulo m, na nambari b inalinganishwa na nambari c modulo modulo sawa, basi nambari a inalinganishwa na nambari c modulo m (m>0; a,b,c) ,m ni nambari kamili).
4. Ikiwa nambari a inalinganishwa na nambari b modulo m, basi nambari a n kulinganishwa na nambari b n modulo m(m>0; a,b,m-integer; n-nambari asilia).

Mifano ya matatizo na ufumbuzi wao.

1. Tafuta nambari ya mwisho ya nambari 3 999 .

Suluhisho:

Kwa sababu Nambari ya mwisho ya nambari ni salio inapogawanywa na 10, basi

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

(Kwa sababu 34=81 1(mod 10);81 n 1(mod10) (kwa mali))

Jibu: 7.

2. Thibitisha kuwa 2 4n -1 inaweza kugawanywa na 15 bila salio. (Phystech2012)

Suluhisho:

Kwa sababu 16 1 (mod 15), basi

16n-1 0 (mod 15) (kwa mali); 16n= (2 4) n

2 4n -1 0(mod 15)

3. Thibitisha kuwa 12 2n+1 +11 n+2 Inaweza kugawanywa na 133 bila salio.

Suluhisho:

12 2n+1 =12*144 n 12*11 n (mod 133) (kwa mali)

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

Nambari (11n *133) inagawanya kwa 133 bila salio 2n+1 +11 n+2 ) inaweza kugawanywa na 133 bila salio.

4. Tafuta salio la nambari 2 iliyogawanywa na 15 2015 .

Suluhisho:

Tangu 16 1 (mod 15), basi

2 2015 8(mod 15)

Jibu:8.

5.Tafuta sehemu iliyobaki kwa nambari ya 17 ya 2 2015. (Phystech2015)

Suluhisho:

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

Tangu 16 -1 (mod 17), basi

2 2015 -8(mod 15)

8 9 (moduli 17)

Jibu:9.

6. Thibitisha kuwa nambari ni 11 100 -1 inaweza kugawanywa na 100 bila salio. (Phystech2015)

Suluhisho:

11 100 =121 50

121 50 21 50 (mod 100) (kwa mali)

21 50 =441 25

441 25 41 25 (mod 100) (kwa mali)

41 25 =41*1681 12

1681 12 (-19) 12 (mod 100) (kwa mali)

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

361 6 (-39) 6 (mod 100) (kwa mali)

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

1521 3 21 3 (mod100) (kwa mali)

41*21 3 =41*21*441

441 41(mod 100) (kwa mali)

21*41 2 =21*1681

1681 -19(mod 100) (kwa mali)

21*(-19)=-399

399 1 (mod 100) (kwa mali)

Kwa hivyo 11 100 1 (mod 100)

11 100 -1 0 (mod 100) (kwa mali)

7. Nambari tatu zimetolewa: 1771,1935,2222. Tafuta nambari ili, ikigawanywa nayo, mabaki ya nambari tatu ulizopewa zitakuwa sawa. (HSE2016)

Suluhisho:

Hebu nambari isiyojulikana iwe sawa na a, basi

2222 1935 (mod a); 1935 1771 (mod a); 2222 1771 (mod a)

2222-1935 0(moda) (kwa mali); 1935-17710(moda) (kwa mali); 2222-17710(moda) (kwa mali)

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

287-164 0(moda) (kwa mali); 451-2870(moda)(kwa mali)

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

164-123 0 (mod a) (kwa mali)

41

Olympiad ya HSE 2016

Maudhui.

Utangulizi

§1. Ulinganisho wa modulo

§2. Sifa za Kulinganisha

1. Sifa za Kulinganisha za Moduli-Kujitegemea
2. Sifa zinazotegemea moduli za kulinganisha

§3. Mfumo wa kupunguzwa

1. Mfumo kamili wa makato
2. Kupunguzwa kwa mfumo wa makato

§4. Nadharia ya Euler na Fermat

1. Kazi ya Euler
2. Nadharia ya Euler na Fermat

Sura ya 2. Nadharia ya kulinganisha na kutofautiana

§1. Dhana za kimsingi zinazohusiana na utatuzi wa kulinganisha

1. Mizizi ya Kulinganisha
2. Usawa wa kulinganisha
3. Nadharia ya Wilson

§2. Ulinganisho wa shahada ya kwanza na suluhisho zao

1. Mbinu ya uteuzi
2. Mbinu za Euler
3. Njia ya algorithm ya Euclid
4. Mbinu ya Sehemu Inayoendelea

§3. Mifumo ya kulinganisha ya shahada ya 1 na isiyojulikana

§4. Mgawanyiko wa kulinganisha wa digrii za juu

§5. Mizizi ya antiderivative na fahirisi

1. Agizo la darasa la kupunguzwa
2. Mizizi primitive modulo mkuu
3. Fahirisi modulo mkuu

Sura ya 3. Utumiaji wa nadharia ya kulinganisha

§1. Ishara za mgawanyiko

§2. Kuangalia matokeo ya shughuli za hesabu

§3. Kubadilisha sehemu ya kawaida kuwa sehemu ya mwisho

sehemu ya utaratibu wa decimal

Hitimisho

Fasihi

Utangulizi

Katika maisha yetu mara nyingi tunapaswa kushughulika na nambari kamili na shida zinazohusiana nazo. Katika tasnifu hii ninazingatia nadharia ya ulinganishi wa nambari kamili.

Nambari kamili mbili ambazo tofauti yake ni mgawo wa nambari asilia fulani m huitwa kulinganishwa katika moduli m.

Neno "moduli" linatokana na moduli ya Kilatini, ambayo kwa Kirusi ina maana "kipimo", "ukubwa".

Kauli "a inalinganishwa na b modulo m" kwa kawaida huandikwa kama ab (mod m) na inaitwa kulinganisha.

Ufafanuzi wa kulinganisha uliandaliwa katika kitabu na K. Gauss "Masomo ya Hesabu". Kazi hii, iliyoandikwa kwa Kilatini, ilianza kuchapishwa mnamo 1797, lakini kitabu hicho kilichapishwa mnamo 1801 tu kwa sababu ya ukweli kwamba mchakato wa uchapishaji wakati huo ulikuwa wa kazi kubwa na wa muda mrefu. Sehemu ya kwanza ya kitabu cha Gauss inaitwa: "Katika kulinganisha nambari kwa ujumla."

Ulinganisho ni rahisi sana kutumia katika hali ambapo inatosha kujua katika baadhi ya nambari za tafiti sahihi hadi zidishi za nambari fulani.

Kwa mfano, ikiwa tunataka kujua mchemraba wa nambari kamili huishia na tarakimu gani, basi inatosha kwetu kujua hadi zidishi 10 na tunaweza kutumia ulinganisho wa modulo 10.

Kusudi la kazi hii ni kuzingatia nadharia ya kulinganisha na kusoma njia za kimsingi za kutatua kulinganisha na zisizojulikana, na pia kusoma utumiaji wa nadharia ya kulinganisha na hesabu ya shule.

Thesis ina sura tatu, na kila sura imegawanywa katika aya, na aya katika aya.

Sura ya kwanza inaangazia masuala ya jumla ya nadharia ya ulinganishi. Hapa tunazingatia dhana ya ulinganishi wa modulo, sifa za ulinganishi, mfumo kamili na uliopunguzwa wa mabaki, kazi ya Euler, nadharia ya Euler na Fermat.

Sura ya pili imejitolea kwa nadharia ya kulinganisha na isiyojulikana. Inaangazia dhana za kimsingi zinazohusiana na usuluhishi wa ulinganisho, inajadili njia za kutatua ulinganisho wa digrii ya kwanza (njia ya uteuzi, njia ya Euler, njia ya algorithm ya Euclid, njia ya sehemu zinazoendelea, kwa kutumia fahirisi), mifumo ya kulinganisha ya shahada ya kwanza. na moja isiyojulikana, kulinganisha kwa digrii za juu, nk.

Sura ya tatu ina matumizi ya nadharia ya nambari kwa hisabati ya shule. Ishara za mgawanyiko, kuangalia matokeo ya vitendo, na kubadilisha sehemu za kawaida kuwa sehemu za decimal za utaratibu huzingatiwa.

Uwasilishaji wa nyenzo za kinadharia unaambatana na idadi kubwa ya mifano inayofunua kiini cha dhana na ufafanuzi ulioletwa.

Sura ya 1. Maswali ya jumla ya nadharia ya kulinganisha

§1. Ulinganisho wa modulo

Acha z iwe nambari kamili, m iwe nambari kamili isiyobadilika, na m·z iwe seti ya nambari kamili ambazo ni zidishi za m.

Ufafanuzi 1. Nambari kamili mbili a na b zinasemekana kulinganishwa modulo m ikiwa m inagawanya a-b.

Ikiwa nambari a na b zinalinganishwa modulo m, basi andika a b (mod m).

Hali a b (mod m) inamaanisha a-b inaweza kugawanywa na m.

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

Hebu tufafanue kwamba modulo ya ulinganifu ya uhusiano inapatana na modulo ya ulinganifu ya uhusiano (-m) (mgawanyiko kwa m ni sawa na mgawanyiko kwa -m). Kwa hivyo, bila upotezaji wa jumla, tunaweza kudhani kuwa m>0.

Mifano.

Nadharia. (ishara ya ulinganifu wa nambari za roho modulo m): Nambari kamili mbili a na b zinaweza kulinganishwa modulo m ikiwa na tu ikiwa a na b zina masalio sawa zinapogawanywa na m.

Ushahidi.

Acha masalio wakati wa kugawanya a na b kwa m yawe sawa, yaani, a=mq₁+r,(1)

B=mq₂+r, (2)

Ambapo 0≤r≥m.

Ondoa (2) kutoka (1), tunapata a-b= m(q₁- q₂), yaani, a-b m au b (mod m).

Kinyume chake, acha a b (mod m). Hii ina maana kwamba a-b m au a-b=mt, t z (3)

Gawanya b kwa m; tunapata b=mq+r katika (3), tutakuwa na =m(q+t)+r, yaani, wakati wa kugawanya a kwa m, salio sawa hupatikana kama wakati wa kugawanya b kwa m.

Mifano.

5=4·(-2)+3

23=4 · 5+3

24=3·8+0

10=3·3+1

Ufafanuzi 2. Nambari mbili au zaidi zinazotoa masalio yanayofanana zikigawanywa na m huitwa masalio sawa au modulo m inayolingana.

Mifano.

Tunayo: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², na (- m²) imegawanywa na m => ulinganisho wetu ni sahihi.

1. Thibitisha kuwa ulinganisho ufuatao ni wa uwongo:

Ikiwa nambari zinalinganishwa modulo m, basi zina gcd sawa nayo.

Tunayo: 4=2 · 2, 10=2 · 5, 25=5 · 5

GCD (4,10) = 2, GCD (25,10) = 5, kwa hiyo kulinganisha kwetu si sahihi.

§2. Sifa za Kulinganisha

1. Sifa zinazojitegemea za moduli za kulinganisha.

Sifa nyingi za kulinganisha ni sawa na sifa za usawa.

a) unyumbufu: aa (mod m) (nambari kamili yoyote a kulinganishwa na yenyewe modulo m);

B) ulinganifu: ikiwa a b (mod m), kisha b a (mod m);

C) mpito: ikiwa a b (mod m), na b na (mod m), kisha a na (mod m).

Ushahidi.

Kwa sharti m/(a-b) na m/ (c-d). Kwa hiyo, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b+d (mod m).

Mifano.

Tafuta iliyobaki wakati wa kugawanya saa 13.

Suluhisho: -1 (mod 13) na 1 (mod 13), kisha (-1)+1 0 (mod 13), yaani, salio la mgawanyiko kwa 13 ni 0.

a-c b-d (mod m).

Ushahidi.

Kwa sharti m/(a-b) na m/(c-d). Kwa hivyo, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

1. (matokeo ya mali 1, 2, 3). Unaweza kuongeza nambari sawa kwa pande zote mbili za ulinganisho.

Ushahidi.

Hebu a b (mod m) na k ni nambari yoyote kamili. Kwa mali ya reflexivity

k=k (mod m), na kulingana na mali 2 na 3 tuna a+k b+k (mod m).

a·c·d (mod m).

Ushahidi.

Kwa hali, a-b є mz, c-d є mz. Kwa hiyo a·c-b·d = (a·c - b·c)+(b·c- b·d)=(a-b)·c+b·(c-d) є mz, yaani, a·c·d (mod m).

Matokeo. Pande zote mbili za ulinganisho zinaweza kuinuliwa kwa nguvu kamili isiyo hasi: ikiwa ab (mod m) na s ni nambari kamili isiyo hasi, kisha a s b s (mod m).

Mifano.

Suluhisho: dhahiri 13 1 (mod 3)

2 -1 (mod 3)

5 -1 (mod 3), basi

- · 1-1 0 (mod 13)

Jibu: salio linalohitajika ni sifuri, na A inaweza kugawanywa na 3.

Suluhisho:

Hebu tuthibitishe kuwa 1+ 0(mod13) au 1+ 0(mod 13)

1+ =1+ 1+ =

Tangu 27 1 (mod 13), basi 1+ 1+1·3+1·9 (mod 13).

nk.

3. Tafuta salio unapogawanya na salio la nambari saa 24.

Tunayo: 1 (mod 24), hivyo

1 (moduli 24)

Kuongeza 55 kwa pande zote mbili za kulinganisha, tunapata:

(Moduli 24).

Tunayo: (mod 24), kwa hivyo

(mod 24) kwa k є N yoyote.

Kwa hivyo (Moduli 24). Tangu (-8)16(mod 24), salio linalohitajika ni 16.

1. Pande zote mbili za ulinganisho zinaweza kuzidishwa kwa nambari kamili sawa.

2.Sifa za kulinganisha kulingana na moduli.

Ushahidi.

Kwa kuwa a b (mod t), basi (a - b) t Na tangu t n , basi kutokana na mpito wa uhusiano wa mgawanyiko(a - b n), yaani, a b (mod n).

Mfano.

Tafuta salio wakati 196 imegawanywa na 7.

Suluhisho:

Kujua kwamba 196= , tunaweza kuandika 196(Moduli 14). Wacha tutumie mali iliyotangulia, 14 7, tunapata 196 (mod 7), yaani, 196 7.

1. Pande zote mbili za ulinganisho na moduli zinaweza kuzidishwa kwa nambari chanya sawa.

Ushahidi.

Wacha a b (mod t ) na c ni nambari kamili chanya. Kisha a-b = mt na ac-bc=mtc, au ac bc (mod mc).

Mfano.

Amua ikiwa thamani ya usemi ni nambari kamili.

Suluhisho:

Wacha tuwakilishe sehemu kwa njia ya kulinganisha: 4(Moduli 3)

1 (moduli 9)

31 (mod 27)

Wacha tuongeze ulinganisho huu kwa muhula (mali 2), tunapata 124(mod 27) Tunaona kuwa 124 sio nambari kamili inayoweza kugawanywa na 27, kwa hivyo maana ya usemi huo.pia sio nambari kamili.

1. Pande zote mbili za kulinganisha zinaweza kugawanywa na sababu yao ya kawaida ikiwa ni coprime kwa moduli.

Ushahidi.

Ikiwa ca cb (mod m), yaani, m/c(a-b) na nambari Na coprime hadi m, (c,m)=1, kisha m hugawanya a-b. Kwa hivyo, a b (mod t).

Mfano.

60 9 (mod 17), baada ya kugawanya pande zote mbili za kulinganisha na 3 tunapata:

20 (mod 17).

Kwa ujumla, haiwezekani kugawanya pande zote mbili za kulinganisha kwa nambari ambayo haifai kwa moduli, kwani baada ya mgawanyiko nambari zinaweza kupatikana ambazo hazifananishwi kwa heshima na moduli iliyotolewa.

Mfano.

8 (mod 4), lakini 2 (mod 4).

1. Pande zote mbili za kulinganisha na moduli zinaweza kugawanywa na kigawanyiko chao cha kawaida.

Ushahidi.

Kama kb (mod km), kisha k (a-b) imegawanywa na km. Kwa hivyo, a-b inaweza kugawanywa na m, ambayo ni a b (mod t).

Ushahidi.

Hebu P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n. Kwa hali a b (mod t), basi

a k b k (mod m) kwa k = 0, 1, 2, ...,n. Kuzidisha pande zote mbili za kila moja ya matokeo ya ulinganisho wa n+1 kwa c n-k , tunapata:

c n-k a k c n-k b k (mod m), ambapo k = 0, 1, 2, ...,n.

Kwa kuongeza ulinganisho wa mwisho, tunapata: P (a) P (b) (mod m). Ikiwa a (mod m) na c i d i (mod m), 0 ≤ i ≤n, basi

(mod m). Kwa hivyo, kwa kulinganisha modulo m, masharti na vipengele vya mtu binafsi vinaweza kubadilishwa na nambari zinazolingana na modulo m.

Wakati huo huo, unapaswa kuzingatia ukweli kwamba wafadhili wanaopatikana kwa kulinganisha hawawezi kubadilishwa kwa njia hii: kutoka.

a n c(mod m) na n k(mod m) haifuati hiyo a k s (mod m).

Mali 11 ina idadi ya maombi muhimu. Hasa, kwa msaada wake inawezekana kutoa uhalali wa kinadharia kwa ishara za mgawanyiko. Kwa mfano, kama mfano, tutatoa utokezi wa jaribio la mgawanyiko kwa 3.

Mfano.

Kila nambari asilia N inaweza kuwakilishwa kama nambari ya utaratibu: N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n.

Fikiria neno la polynomial f(x) = a 0 x n + a 1 x n-1 + ... + a n-1 x+a n . Kwa sababu

10 1 (mod 3), kisha kwa mali 10 f (10) f(1) (mod 3) au

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), i.e. ili N igawanywe na 3, ni muhimu na inatosha kwamba jumla ya nambari za nambari hii igawanywe na 3.

§3. Mifumo ya kupunguzwa

1. Mfumo kamili wa makato.

Nambari zilizosalia sawa, au, ni kitu gani sawa, modulo m inayolingana, huunda darasa la nambari modulo m.

Kutoka kwa ufafanuzi huu inafuata kwamba nambari zote katika darasa zinalingana na salio sawa r, na tunapata nambari zote katika darasa ikiwa, kwa fomu mq+r, tunafanya q kukimbia kupitia nambari zote.

Ipasavyo, na m maadili tofauti ya r, tuna m madarasa ya nambari modulo m.

Nambari yoyote ya darasa inaitwa mabaki modulo m kwa heshima na nambari zote za darasa moja. Mabaki yaliyopatikana kwa q=0, sawa na salio r, inaitwa mabaki madogo zaidi yasiyo hasi.

Salio ρ, iliyo ndogo zaidi katika thamani kamili, inaitwa mabaki madogo kabisa.

Ni wazi, kwa r tuna ρ=r; kwa r> tuna ρ=r-m; mwishowe, ikiwa m ni sawa na r=, basi nambari yoyote kati ya hizo mbili inaweza kuchukuliwa kama ρ na -m= - .

Wacha tuchague kutoka kwa kila darasa la modulo ya mabaki T nambari moja kwa wakati mmoja. Tunapata nambari kamili za t: x 1,…, x m. Seti (x 1,…, x t) inaitwa mfumo kamili wa makato modulo m.

Kwa kuwa kila darasa lina idadi isiyo na kikomo ya mabaki, inawezekana kutunga idadi isiyo na kikomo ya mifumo tofauti kamili ya mabaki kwa moduli fulani m, ambayo kila moja ina t makato.

Mfano.

Kusanya mifumo kadhaa kamili ya makato ya modulo T = 5. Tuna madarasa: 0, 1, 2, 3, 4.

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

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

Wacha tuunde mifumo kadhaa kamili ya makato, tukichukua punguzo moja kutoka kwa kila darasa:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

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

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

nk.

Ya kawaida zaidi:

1. Mfumo kamili wa mabaki angalau yasiyo hasi: 0, 1, t -1 Katika mfano hapo juu: 0, 1, 2, 3, 4. Mfumo huu wa mabaki ni rahisi kuunda: unahitaji kuandika mabaki yote yasiyo ya hasi yaliyopatikana wakati wa kugawanya kwa m.
2. Mfumo kamili wa mabaki chanya(kipunguzo kidogo cha chanya kinachukuliwa kutoka kwa kila darasa):

1, 2, ..., m. Katika mfano wetu: 1, 2, 3, 4, 5.

1. Mfumo kamili wa makato kidogo kabisa.Katika kesi ya m isiyo ya kawaida, mabaki madogo kabisa yanawakilishwa kando.

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

na katika kesi ya m, moja ya safu mbili

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

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

Katika mfano uliotolewa: -2, -1, 0, 1, 2.

Hebu sasa tuchunguze mali ya msingi ya mfumo kamili wa mabaki.

Nadharia 1 . Mkusanyiko wowote wa nambari za m:

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

pairwise modulo m isiyoweza kulinganishwa, huunda mfumo kamili wa mabaki modulo m.

Ushahidi.

1. Kila moja ya nambari katika mkusanyiko (1) ni ya darasa fulani.
2. Nambari zozote mbili x i na x j kutoka (1) hazilinganishwi na kila mmoja, yaani, ni za tabaka tofauti.
3. Kuna nambari za m katika (1), yaani, nambari sawa na kuna madarasa ya modulo T.

x 1, x 2,…, x t - mfumo kamili wa makato modulo m.

Nadharia 2. Acha (a, m) = 1, b - nambari kamili ya kiholela; basi ikiwa x 1, x 2,…, x t ni mfumo kamili wa mabaki modulo m, kisha mkusanyiko wa namba shoka 1 + b, shoka 2 + b,…, shoka m + b pia ni mfumo kamili wa mabaki modulo m.

Ushahidi.

Hebu tuzingatie

Shoka 1 + b, shoka 2 + b,…, shoka m + b (2)

1. Kila moja ya nambari katika mkusanyiko (2) ni ya darasa fulani.
2. Nambari zozote mbili shoka i +b na shoka j + b kutoka (2) hazilinganishwi na kila mmoja, yaani, ni wa tabaka tofauti.

Hakika, ikiwa katika (2) kulikuwa na nambari mbili kama hizo

shoka i +b shoka j + b (mod m), (i = j), basi tungepata shoka i ax j (mod t). Kwa kuwa (a, t) = 1, basi mali ya kulinganisha inaweza kupunguza sehemu zote mbili za kulinganisha na A. Tunapata x i x j (mod m).

Kwa hali x i x j (mod t) saa (i = j) , kwani x 1, x 2, ..., x m - mfumo kamili wa makato.

1. Seti ya nambari (2) ina T nambari, yaani, nyingi kama kuna madarasa modulo m.

Kwa hivyo, shoka 1 + b, shoka 2 + b,…, shoka m + b - mfumo kamili wa mabaki modulo m.

Mfano.

Acha m = 10, a = 3, b = 4.

Wacha tuchukue mfumo kamili wa mabaki modulo 10, kwa mfano: 0, 1, 2,…, 9. Wacha tutunge nambari za fomu. shoka + b. Tunapata: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Seti inayotokana ya nambari ni mfumo kamili wa mabaki modulo 10.

1. Mfumo uliotolewa wa makato.

Wacha tuthibitishe nadharia ifuatayo.

Nadharia 1.

Nambari za darasa sawa la modulo m zina kigawanyiko kikubwa zaidi cha kawaida na m: if a b (mod m), kisha (a, m) = (b, m).

Ushahidi.

Acha b (mod m). Kisha a = b +mt, wapi є z. Kutokana na usawa huu inafuata kwamba (a, t) = (b, t).

Kwa kweli, acha δ iwe kigawanyo cha kawaida cha a na m, kisha aδ, m δ. Kwa kuwa a = b +mt, kisha b=a-mt, kwa hiyo bδ. Kwa hiyo, mgawanyiko wowote wa kawaida wa nambari a na m ni mgawanyiko wa kawaida wa m na b.

Kinyume chake, ikiwa m δ na b δ, basi a = b +mt hugawanywa kwa δ, na kwa hivyo kigawanyo chochote cha kawaida cha m na b ni kigawanyo cha kawaida cha a na m. Nadharia imethibitishwa.

Ufafanuzi 1. Kigawanyaji kikubwa zaidi cha moduli cha kawaida t na nambari yoyote a kutoka kwa darasa hili la makato na T inayoitwa mgawanyiko mkubwa zaidi wa kawaida T na darasa hili la makato.

Ufafanuzi 2. Darasa la mabaki modulo t inayoitwa coprime kwa modulus m , ikiwa mgawanyiko mkubwa zaidi wa kawaida a na t sawa na 1 (yaani, ikiwa m na nambari yoyote kutoka kwa ni coprime).

Mfano.

Hebu t = 6. Darasa la 2 la mabaki linajumuisha namba (..., -10, -4, 2, 8, 14, ...). Kigawanyo kikuu cha kawaida cha nambari zozote kati ya hizi na moduli 6 ni 2. Kwa hivyo, (2, 6) = 2. Kigawanyiko kikuu cha kawaida cha nambari yoyote kutoka darasa la 5 na moduli 6 ni 1. Kwa hivyo, darasa la 5 ni coprime hadi modulus 6. .

Wacha tuchague nambari moja kutoka kwa kila darasa la mabaki ambayo ni coprime na modulo m. Tunapata mfumo wa makato ambayo ni sehemu ya mfumo kamili wa makato. Wanamwitakupunguzwa mfumo wa mabaki modulo m.

Ufafanuzi 3. Seti ya mabaki modulo m, kuchukuliwa moja kutoka kwa kila coprime na T darasa la mabaki ya moduli hii inaitwa mfumo uliopunguzwa wa mabaki.

Kutoka kwa Ufafanuzi wa 3 hufuata njia ya kupata mfumo uliopunguzwa wa mabaki ya modulo T: ni muhimu kuandika baadhi ya mfumo kamili wa mabaki na kuondoa kutoka humo mabaki yote ambayo si coprime na m. Seti iliyobaki ya makato ni mfumo uliopunguzwa wa makato. Ni wazi, idadi isiyo na kikomo ya mifumo ya mabaki modulo m inaweza kutengenezwa.

Ikiwa tutachukua kama mfumo wa awali mfumo kamili wa mabaki yasiyo hasi au madogo kabisa, basi kwa kutumia njia iliyoonyeshwa tunapata, mtawalia, mfumo uliopunguzwa wa mabaki yasiyo hasi au machache kabisa modulo m.

Mfano.

Ikiwa t = 8, kisha 1, 3, 5, 7 ni mfumo uliopunguzwa wa mabaki yasiyo ya hasi, 1, 3, -3, -1- mfumo uliopunguzwa wa makato kidogo kabisa.

Nadharia 2.

Hebu idadi ya madarasa coprime kwa m ni sawa na k.Kisha mkusanyiko wowote wa nambari za k

pairwise incomparable modulo m na coprime kwa m, ni mfumo uliopunguzwa wa mabaki modulo m.

Ushahidi

A) Kila nambari katika idadi ya watu (1) ni ya tabaka fulani.

1. Nambari zote kutoka (1) hazilinganishwi kwa jozi katika moduli T, yaani, wao ni wa tabaka mbalimbali modulo m.
2. Kila nambari kutoka (1) ni coprime with T, yaani, nambari hizi zote ni za madarasa tofauti coprime hadi modulo m.
3. Jumla (1) inapatikana k nambari, yaani, nyingi kama mfumo uliopunguzwa wa mabaki modulo m unapaswa kuwa na.

Kwa hivyo, seti ya nambari(1) - Mfumo uliopunguzwa wa makato ya modulo T.

§4. Kazi ya Euler.

Nadharia za Euler na Fermat.

1. Kazi ya Euler.

Wacha tuashiria kwa φ(T) idadi ya madarasa ya mabaki modulo m coprime hadi m, yaani, idadi ya vipengele vya mfumo uliopunguzwa wa mabaki modulo. t. Kazi φ (t) ni nambari. WanamwitaKazi ya Euler.

Wacha tuchague kama wawakilishi wa madarasa ya mabaki ya modulo t nambari 1, ..., t - 1, t. - idadi ya nambari kama hizo ni pamoja na t. Kwa maneno mengine, φ (t) - idadi ya nambari chanya isiyozidi m na kiasi kikubwa kwa m.

Mifano.

1. Hebu t = 9. Mfumo kamili wa mabaki modulo 9 unajumuisha namba 1, 2, 3, 4, 5, 6, 7, 8, 9. Kati ya hizi, namba 1,2,4, 5, 7, 8 ni coprime. hadi 9. Kwa hivyo kwa kuwa nambari ya nambari hizi ni 6, basi φ (9) = 6.
2. Hebu t = 12. Mfumo kamili wa mabaki una nambari 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Kati ya hizi, nambari 1, 5, 7, 11 ni coprime hadi 12. Hii ina maana

φ(12) = 4.

Katika t = 1, mfumo kamili wa mabaki una darasa moja 1. Mgawanyiko wa kawaida wa asili wa nambari 1 na 1 ni 1, (1, 1) = 1. Kwa msingi huu, tunadhani φ(1) = 1.

Wacha tuendelee kuhesabu chaguo la kukokotoa la Euler.

1) Ikiwa t = p ni nambari kuu, kisha φ(p) = uk-1.

Ushahidi.

Makato 1, 2, ..., p- 1 na ni wao tu walio na idadi kuu r. Kwa hivyo φ (р) = р - 1.

2) Ikiwa t = p k - nguvu kuu p, basi

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

Ushahidi.

Mfumo kamili wa makato ya modulo t = p k ina nambari 1, ..., p k - 1, p k Vigawanyiko vya asili T ni digrii r. Kwa hivyo nambari Ainaweza kuwa na kigawanyiko cha kawaida na m zaidi ya 1, tu katika kesi wakatiAkugawanywa nar.Lakini kati ya nambari 1, ... , ukk -1 juurnambari pekee ndizo zinazoweza kugawanywap, 2p, ... , uk2 , ...rKwa, idadi ambayo ni sawarKwa: p = ukk-1. Hii ina maana kwamba wao ni coprime nat = ukKwapumzikarKwa- ukk-1= ukk-l(uk-1)nambari. Hii inathibitisha hilo

φ (ukKwa) = ukk-1(uk-1).

Nadharia1.

Kazi ya Euler ni ya kuzidisha, yaani, kwa nambari kuu kiasi m na n tuna φ (mn) = φ(m) φ (n).

Ushahidi.

Mahitaji ya kwanza katika ufafanuzi wa kazi ya kuzidisha inatimizwa kwa njia isiyo na maana: kazi ya Euler inaelezwa kwa namba zote za asili, na φ (1) = 1. Tunahitaji tu kuonyesha kwambaainanambari za coprime, basi

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

Wacha tupange mfumo kamili wa modulo ya makatotpkatika fomunXT -matrices

1 2 T

t +1 t +2 2t

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

(p-1) t+1 (p-1) m+2 Ijumaa

Kwa sababuTNanni kiasi mkuu, basi idadiXkwa usawa tu natpbasi na lini tuXkwa usawa tu naTNaXkwa usawa tu nan. Lakini idadikm+tkwa usawa tu naTikiwa na tu ikiwatkwa usawa tu naT.Kwa hivyo, nambari za coprime kwa m ziko kwenye safu wima ambazothupitia mfumo uliopunguzwa wa mabaki ya moduloT.Idadi ya safu wima kama hizo ni sawa na φ(T).Kila safu inawasilisha mfumo kamili wa makato ya modulouk.Kutoka kwa makato haya φ(p)coprime nauk.Hii ina maana kwamba jumla ya idadi ya nambari ambazo ni kuu na zenyeTna kwa n, sawa na φ(T)φ(n)

(φ (T)nguzo, katika kila moja ambayo φ inachukuliwa(p)nambari). Nambari hizi, na wao tu, ndizo zinazostahilink.Hii inathibitisha hilo

φ (tp)= φ (T) φ (p).

Mifano.

№1 . Thibitisha uhalali wa usawa ufuatao

φ(4n) =

Ushahidi.

№2 . Tatua mlinganyo

Suluhisho:kwa sababu(m)=, Hiyo= , yaani=600, =75, =3·, kisha x-1=1, x=2,

y-1=2, y=3

Jibu: x=2, y=3

Tunaweza kukokotoa thamani ya chaguo za kukokotoa za Euler(m), kujua uwakilishi wa kisheria wa nambari m:

m=.

Kutokana na wingi(m) tunayo:

(m)=.

Lakini kulingana na fomula (1) tunaona hivyo

-1), na kwa hivyo

(3)

Usawa (3) unaweza kuandikwa upya kama:

Kwa sababu=m, basi(4)

Mfumo (3) au, ambao ni sawa, (4) ndio tunatafuta.

Mifano.

№1 . Kiasi gani?

Suluhisho:,

, =18 (1- ) (1- =18 , Kisha= 1+1+2+2+6+6=18.

№2 . Kulingana na sifa za kazi ya nambari ya Euler, thibitisha kuwa katika mlolongo wa nambari za asili kuna seti isiyo na kikomo ya nambari kuu.

Suluhisho:Kwa kudhani kuwa idadi ya nambari kuu ni seti yenye kikomo, tunadhania hiyo- nambari kuu kubwa zaidi na acha a=ni bidhaa ya nambari zote kuu, kulingana na moja ya sifa za kazi ya nambari ya Euler

Tangu a≥, basi a ni nambari iliyojumuishwa, lakini kwa kuwa uwakilishi wake wa kisheria una nambari kuu zote, basi=1. Tunayo:

=1 ,

ambayo haiwezekani, na kwa hivyo inathibitishwa kuwa seti ya nambari kuu haina kikomo.

№3 .Tatua mlinganyo, wapi x=Na=2.

Suluhisho:Tunatumia mali ya kazi ya nambari ya Euler,

,

na kwa masharti=2.

Wacha tueleze kutoka=2 , tunapata, mbadala ndani

:

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

Kisha x=, x=11·13=143.

Jibu:x= 143

2. Nadharia ya Euler na Fermat.

Nadharia ya Euler ina jukumu muhimu katika nadharia ya kulinganisha.

Nadharia ya Euler.

Ikiwa nambari kamili a ni sawa kwa m, basi

(1)

Ushahidi.Hebu

(2)

kuna mfumo uliopunguzwa wa mabaki modulo m.

Kamaani integer coprime kwa m, basi

(3)

Ulinganisho wa shahada ya kwanza na usiyojulikana una fomu:

f(x) 0 ( mod m); f(X) = Oh + n. (1)

Tatua ulinganisho- inamaanisha kupata maadili yote ya x ambayo yanakidhi. Ulinganisho mbili ambazo zinakidhi maadili sawa ya x huitwa sawa.

Ikiwa ulinganisho (1) umeridhika na yoyote x = x 1, kisha (kulingana na 49) nambari zote kulinganishwa na x 1, moduli m: x x 1 ( mod m) Darasa hili lote la nambari linachukuliwa kuwa suluhisho moja. Kwa makubaliano kama haya, hitimisho lifuatalo linaweza kutolewa.

66.C alignment (1) itakuwa na suluhisho nyingi kama idadi ya mabaki ya mfumo kamili unaokidhi.

Mfano. Kulinganisha

6x- 4 0 (mod 8)

Kati ya nambari 0, 1, 2, 3, 4, 5, 6, 7, nambari mbili zinakidhi mfumo kamili wa mabaki modulo 8: X= 2 na X= 6. Kwa hivyo, ulinganisho huu una masuluhisho mawili:

x 2 (moduli 8), X 6 (moduli 8).

Ulinganisho wa shahada ya kwanza kwa kusonga neno la bure (na ishara kinyume) kwa upande wa kulia inaweza kupunguzwa kwa fomu.

shoka b( mod m). (2)

Fikiria ulinganisho unaokidhi hali ( A, m) = 1.

Kulingana na 66, ulinganisho wetu una masuluhisho mengi kama vile kuna mabaki ya mfumo kamili unaokidhi. Lakini lini x huendesha kupitia mfumo kamili wa mabaki ya modulo T, Hiyo Oh hupitia mfumo kamili wa makato (kati ya 60). Kwa hiyo, kwa thamani moja na moja tu X, kuchukuliwa kutoka kwa mfumo kamili, Oh italinganishwa na b. Kwa hiyo,

67. Wakati (a, m) = shoka 1 la kulinganisha b( mod m)ina suluhisho moja.

Wacha sasa ( a, m) = d> 1. Kisha, ili kulinganisha (2) kuwa na suluhu, ni muhimu (kati ya 55) kwamba. b kugawanywa na d, vinginevyo kulinganisha (2) haiwezekani kwa nambari yoyote x . Kwa kudhani b nyingi d, tuweke a = a 1 d, b = b 1 d, m = m 1 d. Kisha kulinganisha (2) itakuwa sawa na hii (iliyofupishwa na d): a 1 x b 1 ( mod m), ambayo tayari ( A 1 , m 1) = 1, na kwa hivyo itakuwa na modulo moja ya suluhisho m 1. Hebu X 1 – mabaki madogo yasiyo hasi ya modulo hii ya modulo m 1 , basi nambari zote ni x , kutengeneza suluhisho hili hupatikana katika fomu

x x 1 ( mod m 1). (3)

Modulo m, nambari (3) haziunda suluhisho moja, lakini zaidi, suluhisho nyingi kama vile kuna nambari (3) kwenye safu 0, 1, 2, ..., m - Masalio 1 angalau yasiyo hasi ya modulo m. Lakini nambari zifuatazo (3) zitaanguka hapa:

x 1 , x 1 + m 1 , x 1 + 2m 1 , ..., x 1 + (d – 1) m 1 ,

hizo. jumla d nambari (3); kwa hivyo kulinganisha (2) ina d maamuzi.

Tunapata nadharia:

68. Acha (a, m) = d. Axe ya kulinganisha b ( mod m) haiwezekani ikiwa b haijagawanywa na d. Wakati b ni mgawo wa d, ulinganisho una masuluhisho d.

69. Njia ya kutatua ulinganisho wa shahada ya kwanza, kwa kuzingatia nadharia ya sehemu zinazoendelea:

Kupanua katika sehemu inayoendelea uhusiano m:a,

na ukiangalia sehemu mbili za mwisho zinazolingana:

kulingana na mali ya sehemu zinazoendelea (kulingana na 30 ) tunayo

Kwa hivyo kulinganisha kuna suluhisho

kupata, ambayo inatosha kuhesabu P n- 1 kulingana na njia iliyoainishwa katika 30.

Mfano. Wacha tusuluhishe ulinganisho

111x= 75 (mod 321). (4)

Hapa (111, 321) = 3, na 75 ni nyingi ya 3. Kwa hiyo, kulinganisha kuna ufumbuzi tatu.

Kugawanya pande zote mbili za kulinganisha na moduli na 3, tunapata kulinganisha

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

ambayo tunapaswa kutatua kwanza. Tumepata

q
P 3

Kwa hiyo, katika kesi hii n = 4, P n - 1 = 26, b= 25, na tuna suluhisho la kulinganisha (5) katika fomu

x–26 ∙ 25 99 (mod 107).

Kwa hivyo masuluhisho ya kulinganisha (4) yanawasilishwa kama ifuatavyo:

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

Xº99; 206; 313 (mod 321).

Uhesabuji wa kipengele kinyume na modulo fulani

70.Kama nambari ni nambari kamili a Na n ni coprime, basi kuna idadi a′, kuridhisha kulinganisha a ∙ a′ ≡ 1 (moduli n) Nambari a′ kuitwa kinyume cha kuzidisha cha modulo n na nukuu iliyotumika kwake ni a- 1 ( mod n).

Hesabu ya viwango vya kubadilishana modulo thamani fulani inaweza kufanywa kwa kutatua ulinganisho wa shahada ya kwanza na ile isiyojulikana, ambayo x nambari imekubaliwa a′.

Ili kupata suluhisho la kulinganisha

a∙x≡ 1 (moduli m),

Wapi ( a,m)= 1,

unaweza kutumia kanuni ya Euclid (69) au nadharia ya Fermat-Euler, ambayo inasema kwamba ikiwa ( a,m) = 1, basi

a φ( m) ≡ 1(moduli m).

x ≡ a φ( m)-1 (moduli m).

Vikundi na mali zao

Vikundi ni mojawapo ya madarasa ya taxonomic yanayotumiwa kuainisha miundo ya hisabati yenye sifa bainifu za kawaida. Vikundi vina vipengele viwili: nyingi (G) Na shughuli() imefafanuliwa kwenye seti hii.

Dhana za kuweka, kipengele na uanachama ni dhana za msingi zisizofafanuliwa za hisabati ya kisasa. Seti yoyote inaelezwa na vipengele vilivyojumuishwa ndani yake (ambayo, kwa upande wake, inaweza pia kuweka). Kwa hivyo, tunasema kwamba seti imefafanuliwa au inatolewa ikiwa kwa kipengele chochote tunaweza kujua ikiwa ni ya seti hii au la.

Kwa seti mbili A, B kumbukumbu B A, B A, B∩ A, B A, B \ A, A × B kwa mtiririko huo maana yake B ni sehemu ndogo ya seti A(yaani kipengele chochote kutoka B pia yamo ndani A, kwa mfano, seti ya nambari za asili zinazomo katika seti ya nambari halisi; zaidi ya hayo, daima A A), B ni sehemu ndogo inayofaa ya seti A(hizo. B A Na B ≠ A), makutano ya seti B Na A(yaani vitu vyote kama hivyo ambavyo viko ndani kwa wakati mmoja A, na katika B, kwa mfano, makutano ya nambari na nambari chanya halisi ni seti ya nambari asilia), umoja wa seti. B Na A(yaani seti inayojumuisha vitu ambavyo viko ndani A, au ndani B), weka tofauti B Na A(yaani seti ya vipengele vilivyomo B, lakini usilale ndani A), Bidhaa ya Cartesian ya seti A Na B(yaani seti ya jozi za fomu ( a, b), Wapi a A, b B) Kupitia | A| daima inaashiria kardinali ya seti A, i.e. idadi ya vipengele katika seti A.

Operesheni ni sheria kulingana na ambayo vipengele viwili vya seti G(a Na b) inalinganishwa na kipengele cha tatu kutoka kwa G: a b.

Vipengele vingi G na operesheni inaitwa kikundi, ikiwa masharti yafuatayo yatatimizwa.

Ufafanuzi 1. Ikiwa nambari mbili ni 1) a Na b ikigawanywa na uk toa salio sawa r, basi nambari kama hizo huitwa equiremainder au kulinganishwa katika moduli uk.

Taarifa 1. Hebu uk nambari fulani chanya. Kisha kila nambari a daima na, zaidi ya hayo, kwa njia pekee inaweza kuwakilishwa katika fomu

Lakini nambari hizi zinaweza kupatikana kwa kuweka r sawa na 0, 1, 2,..., uk−1. Kwa hiyo sp+r=a itapata maadili yote kamili yanayowezekana.

Wacha tuonyeshe kuwa uwakilishi huu ni wa kipekee. Hebu tuchukulie hivyo uk inaweza kuwakilishwa kwa njia mbili a=sp+r Na a=s 1 uk+r 1. Kisha

(2)

Kwa sababu r 1 inakubali moja ya nambari 0,1, ..., uk−1, kisha thamani kamili r 1 −r kidogo uk. Lakini kutoka (2) inafuata hiyo r 1 −r nyingi uk. Kwa hiyo r 1 =r Na s 1 =s.

Nambari r kuitwa kuondoa nambari a moduli uk(kwa maneno mengine, nambari r aliita nambari iliyobaki a juu uk).

Taarifa 2. Ikiwa nambari mbili a Na b kulinganishwa katika moduli uk, Hiyo a-b kugawanywa na uk.

Kweli. Ikiwa nambari mbili a Na b kulinganishwa katika moduli uk, basi ikigawanywa na uk kuwa na salio sawa uk. Kisha

kugawanywa na uk, kwa sababu upande wa kulia wa equation (3) imegawanywa na uk.

Taarifa 3. Ikiwa tofauti ya nambari mbili inaweza kugawanywa na uk, basi nambari hizi zinalinganishwa katika moduli uk.

Ushahidi. Wacha tuonyeshe kwa r Na r Sehemu 1 iliyobaki a Na b juu uk. Kisha

Mifano 25≡39 (mod 7), −18≡14 (mod 4).

Kutoka kwa mfano wa kwanza inafuata kwamba 25 wakati imegawanywa na 7 inatoa salio sawa na 39. Hakika, 25 = 3 7 + 4 (salio 4). 39=3 · 7+4 (salio 4). Wakati wa kuzingatia mfano wa pili, unahitaji kuzingatia kwamba salio lazima iwe nambari isiyo hasi chini ya moduli (yaani 4). Kisha tunaweza kuandika: -18=−5·4+2 (salio 2), 14=3·4+2 (salio 2). Kwa hivyo, -18 ikigawanywa na 4 huacha salio 2, na 14 ikigawanywa na 4 huacha salio la 2.

Sifa za ulinganisho wa modulo

Mali 1. Kwa mtu yeyote a Na uk Daima

hakuna kulinganisha kila wakati

Wapi λ ndiye mgawanyiko mkubwa zaidi wa nambari m Na uk.

Ushahidi. Hebu λ mgawanyiko mkubwa zaidi wa nambari m Na uk. Kisha

Kwa sababu m(a-b) kugawanywa na k, Hiyo

Kwa hiyo

Na m ni moja ya vigawanyiko vya nambari uk, Hiyo

Wapi h=pqs.

Kumbuka kwamba tunaweza kuruhusu kulinganisha kulingana na moduli hasi, i.e. kulinganisha a≡b mod( uk) inamaanisha katika kesi hii kwamba tofauti a-b kugawanywa na uk. Sifa zote za kulinganisha zinabaki kutumika kwa moduli hasi.