Arvud võrreldavad moodul 7. Võrdlus moodul naturaalarv

Võrdlus ühe tundmatuga x paistab nagu

Kus. Kui a n ei jagatav m, seda nimetatakse kraadi võrdlused.

Otsuse järgi võrdlus on suvaline täisarv x 0 , mille jaoks

Kui X 0 rahuldab võrdlust, siis 9 võrdluse omaduse järgi on kõik täisarvud võrreldavad x 0 modulo m. Seega kõik võrdluslahendused, mis kuuluvad samasse jäägiklassi moodulisse T, käsitleme seda ühe lahendusena. Seega on võrdlusel nii palju lahendusi, kui palju on jääkide terviksüsteemi elemente, mis seda rahuldavad.

Võrdlusi, mille lahendushulgad langevad kokku, nimetatakse samaväärne.

2.2.1 Esimese astme võrdlused

Esimese astme võrdlus ühe tundmatuga X paistab nagu

(2.2)

Teoreem 2.4. Selleks, et võrdluses oleks vähemalt üks lahendus, on vajalik ja piisav, et arv b jagatud GCD( a, m).

Tõestus. Kõigepealt tõestame vajalikkust. Lase d = GCD( a, m) Ja X 0 - võrdluslahendus. Siis , see tähendab erinevust Oh 0 − b jagatuna T. Seega on selline täisarv q, Mida Oh 0 − b = qm. Siit b= ah 0 − qm. Ja sellest ajast peale d, ühisjagajana jagab numbreid A Ja T, siis minuend ja alajaotus jagatakse d, ning seetõttu b jagatuna d.

Nüüd tõestame piisavust. Lase d- arvude suurim ühisjagaja A Ja T, Ja b jagatuna d. Jaguvuse definitsiooni järgi on siis olemas järgmised täisarvud a 1 , b 1 ,T 1 , Mida .

Laiendatud Eukleidilise algoritmi abil leiame arvu 1 = gcd() lineaarse esituse a 1 , m 1 ):

mõne jaoks x 0 , y 0 . Korrutame viimase võrdsuse mõlemad pooled arvuga b 1 d:

või mis on sama,

see tähendab ja on võrdluse lahendus. □

Näide 2.10. Võrdlus 9 X= 6 (mod 12) omab lahendust, kuna gcd(9, 12) = 3 ja 6 jagub 3-ga. □

Näide 2.11. Võrdlus 6x= 9 (mod 12) ei sisalda lahendeid, kuna gcd(6, 12) = 6 ja 9 ei jagu 6-ga. □

Teoreem 2.5. Olgu võrdlus (2.2) lahendatav ja d = GCD( a, m). Siis koosneb võrdluslahendite hulk (2.2). d mooduli jäägiklassid T, nimelt kui X 0 - üks lahendustest, siis on kõik teised lahendused

Tõestus. Lase X 0 - võrdluslahend (2.2), st Ja , . Nii et selline asi on olemas q, Mida Oh 0 − b = qm. Nüüd asendades selle asemel viimase võrdsuse X 0 vormi suvaline lahend, kus, saame avaldise

, jagatav m. □

Näide 2.12. Võrdlus 9 X=6 (mod 12) omab täpselt kolm lahendit, kuna gcd(9, 12)=3. Need lahendused: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

Näide 2.13. Võrdlus 11 X=2 (mod 15) omab ainulaadset lahendust X 0 = 7, kuna GCD(11,15)=1,□

Näitame teile, kuidas lahendada esimese astme võrdlusi. Ilma üldistust kaotamata eeldame, et GCD( a, t) = 1. Seejärel saab otsida lahendust võrdlusele (2.2) näiteks eukleidilise algoritmi abil. Tõepoolest, kasutades laiendatud Eukleidilise algoritmi, esitame arvu 1 lineaarse numbrikombinatsioonina a Ja T:

Korrutame selle võrdsuse mõlemad pooled arvuga b, saame: b = abq + mrb, kus abq - b = - mrb, see on a ∙ (bq) = b(mod m) Ja bq- võrdluslahend (2.2).

Teine lahendus on kasutada Euleri teoreemi. Jällegi usume, et GCD(a, T)= 1. Rakendame Euleri teoreemi: . Korrutage võrdluse mõlemad pooled arvuga b: . Viimase avaldise ümberkirjutamine kui , saame, et on lahendus võrdlusele (2.2).

Las nüüd GCD( a, m) = d>1. Siis a = atd, m = mtd, kus GCD( A 1 , m 1) = 1. Lisaks on see vajalik b = b 1 d, et võrdlus oleks lahendatav. Kui X 0 - võrdluslahendus A 1 x = b 1 (mod m 1) ja ainus, kuna GCD( A 1 , m 1) = 1, siis X 0 on lahendus ja võrdlus A 1 xd = db 1 (mod m 1), ehk algne võrdlus (2.2). Puhka d- Lause 2.5 abil leitakse 1 lahendus.

Matemaatika projekt teemal

"Võrdlusmoodul"

Zaripova Aisylu

Kaasani Sovetski rajoon

MBOU "Keskkool nr 166", 7a klass

Teaduslik juhendaja: Antonova N.A.

Sisukord

Sissejuhatus_________________________________________________________________________3

Mis on võrdlused__________________________________________________4

Võrdluste rakendamine ülesannete lahendamisel___________________________________6

Moodulite võrdluste lihtsaim kasutamine on arvude jaguvuse määramine___________________________6
Üks võrdlusülesanne___________________________________8
Moodulite võrdluste kasutamine kutsetegevuses_____________________________________________________9

Järeldus______________________________________________________________________________________________________________________________________________________________________________________________________________10

Kasutatud kirjanduse loetelu_______________________________________________11

Sissejuhatus.

Teema: Modulo võrdlused.

Probleem: Paljud õpilased seisavad olümpiaadiks valmistumisel silmitsi probleemidega, mille lahendamise aluseks on teadmine jääkide kohta, mis saadakse täisarvude jagamisel naturaalarvuga. Meid huvitasid seda tüüpi probleemid ja nende lahendamise võimalikud meetodid. Selgub, et neid saab lahendada moodulvõrdluste abil.

Eesmärk: Selgitada välja moodulvõrdluste olemus, peamised meetodid moodulivõrdlustega töötamiseks.

Eesmärgid: leida sellel teemal teoreetilist materjali, kaaluda probleeme, mida lahendatakse moodulvõrdluste abil, näidata selliste probleemide lahendamise levinumaid meetodeid, teha järeldusi.

Õppeobjekt: arvuteooria.

Uurimisaine: moodulvõrdluste teooria.

Töö on seotud teoreetilise uurimistööga ja seda saab kasutada matemaatikaolümpiaadideks valmistumisel. Selle sisu paljastab moodulite võrdluse põhimõisted ja nende peamised omadused ning toob näiteid selleteemaliste probleemide lahendamisest.

I . Mis on võrdlused?

Arvud ja peetakse moodulis võrreldavateks, kui need on jagatavad ehk teisisõnu, a ja b jäägid on samad, kui need jagatakse.

Määramine

Näited:

12 ja 32 on võrreldavad mooduliga 5, kuna 12 jagatuna 5-ga on jääk 2 ja 32, kui jagatakse 2-ga, on jääk 2. See on kirjutatud12 ;

101 ja 17 on võrreldavad moodulid 21;

Jaguvuse teooria lõi suures osas Euler. Võrdluse definitsiooni sõnastas K.F.Gaussi raamatus “Aritmeetilised uuringud”. Seda ladina keeles kirjutatud teost hakati trükkima 1797. aastal, kuid raamat ilmus alles 1801. aastal, kuna tolleaegne trükiprotsess oli äärmiselt töömahukas ja pikk. Gaussi raamatu esimene osa kannab nime: "Arvude võrdlusest". Just Gauss pakkus välja matemaatikas kinnistunud moodulvõrdluste sümboolika.

Kui

Tõestus:

Kui liidame esimesele võrdsusele teise, saame

on kahe täisarvu summa, seega on see täisarv.

Kui lahutame esimesest võrdsusest teise, saame

see on kahe täisarvu erinevus, mis tähendab, et see on täisarv.

Mõelge väljendile:

See on täisarvude korrutiste erinevus, mis tähendab, et see on täisarv.

See on võrdluste kolmanda omaduse tagajärg.

Q.E.D.

5) Kui.

Tõestus: Leiame nende kahe avaldise summa:

on kahe täisarvu summa, seega on see täisarv, seega .

Q.E.D.

6) Kui on täisarv, siis

Tõestus: , kuslk– täisarv, korrutage see võrdus arvuga, saame: . Kuna see on täisarvude korrutis, tuli seda tõestada.

7) Kui

Tõestus: põhjendus sarnaneb vara tõendamisega 6.

8) Kui - koaprarvud siis

Tõestus: , jagame selle avaldise arvuga, saame: - koalgarvud, mis tähendab, et need jaguvad täisarvuga, s.t. =. Ja see tähendab, et mida oli vaja tõestada.

II . Võrdluste rakendamine probleemide lahendamisel.

2.1. Moodulite võrdluste lihtsaim kasutamine on arvude jaguvuse määramine.

Näide. Leia ülejäänud 2 2009 kell 7.

Lahendus: kaaluge 2 võimsusi:

tõstes võrdluse astmeni 668 ja korrutades sellega, saame: .

Vastus: 4.

Näide. Tõesta, et 7+7 2 +7 3 +…+7 4 n mis tahes jaoks jagub 100-gantäisarvude hulgast.

Lahendus: kaaluge võrdlusi

jne. Jääkide tsüklilisus on seletatav arvude korrutamise reeglitega veerus. Kui liita kokku neli esimest võrdlust, saame:

See tähendab, et see summa jagatakse 100-ga ilma jäägita. Samamoodi, lisades järgmised võrdlused umbes nelja kohta, saame, et iga selline summa jagub 100-ga ilma jäägita. See tähendab, et kogu summa, mis koosneb 4-stnterminid jaguvad 100-ga ilma jäägita. Q.E.D.

Näide. Määrake, mis väärtusesnavaldis jagub 19-ga ilma jäägita.

Lahendus:.

Korrutame selle võrdluse 20-ga. Saame.

Liidame siis võrdlused kokku. . Seega jagub võrdluse parem pool mis tahes naturaalarvu puhul alati 19-gan, mis tähendab, et algne avaldis jagub naturaalarvuga 19-gan.

Vastus n – mis tahes naturaalarv.

Näide. Mis numbriga number lõpeb?

Lahendus. Selle probleemi lahendamiseks jälgime ainult viimast numbrit. Mõelge arvu 14 jõududele:

Võite märgata, et kui astendaja on paaritu, lõpeb astme väärtus 4-ga ja kui astendaja on paaris, siis 6. Siis lõpeb see 6-ga, st. on paarisarv. Nii et see lõpeb 6.

Vastus 6.

2.2. Üks võrdlusülesanne.

N. Vilenkini artikkel “Jääkide võrdlused ja klassid” esitab probleemi, mille lahendas kuulus inglise füüsik Dirac oma tudengipõlves.

Sellele probleemile on ka lühike lahendus, kasutades moodulvõrdlusi. Kuid puutusime kokku mitmete sarnaste probleemidega. Näiteks.

Üks mööduja leidis puu juurest õunuhunniku, millel istus ahv. Pärast nende lugemist mõistis ta, et kui ahvile antakse 1 õun, jagatakse ülejäänud õunte arv n jäljetult. Andnud ahvile lisaõuna, võttis ta 1/ n ülejäänud õunad ja lahkus. Hiljem lähenes hunnikule järgmine mööduja, siis järgmine jne. Iga järgnev mööduja, olles õunu lugenud, märkas, et nende arv on jagatud n annab ülejäänu 1 ja pärast lisaõuna ahvile andmist võttis ta endale 1 n ülejäänud õunad ja liikus edasi. Pärast viimase lahkumist, n mööduja, jagati hunnikusse jäänud õunte arv arvuga n jäljetult. Mitu õuna oli alguses hunnikus?

Läbi samade arutluste nagu Dirac, saime üldvalemi sarnaste ülesannete klassi lahendamiseks: , kusn- naturaalarv.

2.3. Moodulite võrdluste rakendamine kutsetegevuses.

Võrdlusteooriat rakendatakse kodeerimise teooriale, nii et kõik inimesed, kes valivad arvutiga seotud elukutse, õpivad ja võimalusel rakendavad ka võrdlusi oma kutsetegevuses. Näiteks kasutatakse avaliku võtmega krüpteerimisalgoritmide väljatöötamiseks mitmeid arvuteooria kontseptsioone, sealhulgas moodulite võrdlusi.

Järeldus.

Töös tuuakse välja moodulvõrdluse põhimõisted ja omadused ning illustreeritakse näidetega moodulvõrdluse kasutamist. Materjali saab kasutada matemaatikaolümpiaadideks ja ühtseks riigieksamiks valmistumisel.

Antud kirjanduse loetelu võimaldab vajadusel kaaluda moodulvõrdluste teooria ja selle rakenduste mõningaid keerukamaid aspekte.

Kasutatud kirjanduse loetelu.

Alfutova N.B. Algebra ja arvuteooria./N.B.Alfutova, A.V.Ustinov. M.: MCNMO, 2002, 466 lk.

Bukhshtab A.A. Arvuteooria. /A.A.Bukhshtab. M.: Haridus, 1960.

Vilenkin N. Jääkide võrdlused ja klassid./N. Vilenkin.//Kvant. – 1978.- 10.

Fedorova N.E. Algebra ja matemaatilise analüüsi õpe. 10. klass.http:// www. prosv. ru/ e-raamatud/ Fedorova_ Algebra_10 kl/1/ xht

ru. wikipedia. org/ wiki/Võrdluse_moodul.

Definitsioon 1. Kui kaks numbrit on 1) a Ja b kui jagatud lk anna sama ülejääk r, siis nimetatakse selliseid arve equiremainderiks või mooduli poolest võrreldav lk.

avaldus 1. Lase lk mingi positiivne number. Siis iga number a alati ja pealegi ainsal viisil saab vormis esitada

Kuid neid numbreid saab seadistades r võrdne 0, 1, 2,..., lk−1. Seega sp+r=a saab kõik võimalikud täisarvud.

Näitame, et see esitus on ainulaadne. Teeskleme seda lk saab esitada kahel viisil a=sp+r Ja a=s 1 lk+r 1 . Siis

(2)

Sest r 1 aktsepteerib ühte numbritest 0,1, ..., lk−1, siis absoluutväärtus r 1 −r vähem lk. Kuid punktist (2) järeldub, et r 1 −r mitmekordne lk. Seega r 1 =r Ja s 1 =s.

Number r helistas miinus numbrid a modulo lk(teisisõnu number r kutsus numbri ülejäänud osa a peal lk).

avaldus 2. Kui kaks numbrit a Ja b mooduli poolest võrreldav lk, See a-b jagatuna lk.

Tõesti. Kui kaks numbrit a Ja b mooduli poolest võrreldav lk, siis jagamisel lk on sama ülejäänud lk. Siis

jagatuna lk, sest võrrandi (3) parem pool jagatakse lk.

avaldus 3. Kui kahe arvu erinevus jagub arvuga lk, siis on need arvud moodulites võrreldavad lk.

Tõestus. Tähistame tähisega r Ja r 1 jaotuse järelejäänud a Ja b peal lk. Siis

Näited 25≡39 (mod 7), -18≡14 (mod 4).

Esimesest näitest järeldub, et 25 jagamisel 7-ga annab sama jäägi kui 39. Tõepoolest, 25 = 3·7+4 (ülejäänud 4). 39=3·7+4 (ülejäänud 4). Teise näite kaalumisel peate arvestama, et jääk peab olema mittenegatiivne arv, mis on väiksem kui moodul (st 4). Siis saame kirjutada: −18=−5·4+2 (ülejäänud 2), 14=3·4+2 (ülejäänud 2). Seetõttu jääb −18 4-ga jagamisel jäägiks 2 ja 14 4-ga jagamisel jäägiks 2.

Moodulite võrdluste omadused

Kinnisvara 1. Kellelegi a Ja lk Alati

alati ei saa võrrelda

Kus λ on arvude suurim ühisjagaja m Ja lk.

Tõestus. Lase λ arvude suurim ühisjagaja m Ja lk. Siis

Sest m(a-b) jagatuna k, See

Seega

Ja m on üks arvu jagajatest lk, See

Kus h = pqs.

Pange tähele, et saame lubada võrdlusi negatiivsete moodulite alusel, s.t. võrdlus a≡b mod( lk) tähendab antud juhul erinevust a-b jagatuna lk. Negatiivsete moodulite puhul jäävad kehtima kõik võrdluste omadused.

Esimese astme võrdlus ühe tundmatuga on järgmine:

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

Lahendage võrdlus- tähendab kõigi x-i väärtuste leidmist, mis seda rahuldavad. Nimetatakse kaks võrdlust, mis vastavad samadele x väärtustele samaväärne.

Kui võrdlus (1) on rahuldatud mis tahes x = x 1, siis (vastavalt 49-le) kõik numbrid, mis on võrreldavad x 1, moodul m: x x 1 (mod m). Kogu seda arvude klassi peetakse üks lahendus. Sellise kokkuleppega saab teha järgmise järelduse.

66.C joondus (1) on nii palju lahendusi, kui palju kogu süsteemi jääke, mis seda rahuldavad.

Näide. Võrdlus

6x– 4 0 (mod 8)

Arvude 0, 1,2, 3, 4, 5, 6, 7 hulgas on kaks arvu, mis vastavad kogu jääkide süsteemile mooduli 8: X= 2 ja X= 6. Seetõttu on sellel võrdlusel kaks lahendust:

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

Esimese astme võrdluse vaba termini (vastasmärgiga) paremale nihutamise teel saab taandada vormile

kirves b(mod m). (2)

Mõelge võrdlusele, mis vastab tingimusele ( A, m) = 1.

66 kohaselt on meie võrdluses nii palju lahendusi, kui palju on seda rahuldavaid terviksüsteemi jääke. Aga kui x läbib kogu modulojääkide süsteemi T, See Oh läbib kogu mahaarvamiste süsteemi (60-st). Seega ühe ja ainult ühe väärtuse jaoks X, võetud kogu süsteemist, Oh saab olema võrreldav b. Niisiis,

67. Kui (a, m) = 1 võrdlustelg b(mod m)on üks lahendus.

Las nüüd ( a, m) = d> 1. Siis on võrdluseks (2) lahenduste leidmiseks vajalik (55-st), et b jagatuna d, vastasel juhul on võrdlus (2) võimatu ühegi täisarvu x korral . Eeldusel seega b mitmekordsed d, paneme a = a 1 d, b = b 1 d, m = m 1 d. Siis on võrdlus (2) samaväärne sellega (lühendatult d): a 1 x b 1 (mod m), milles juba ( A 1 , m 1) = 1, ja seetõttu on sellel üks lahendusmoodul m 1 . Lase X 1 – selle lahuse väikseim mittenegatiivne jääk moodul m 1 , siis kõik arvud on x , moodustavad selle lahenduse on leitud kujul

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

Modulo m, arvud (3) moodustavad mitte ühe lahendi, vaid rohkem, täpselt nii palju lahendeid, kui on arve (3) reas 0, 1, 2, ..., m – 1 kõige vähem mittenegatiivset modulojääki m. Kuid siia langevad järgmised numbrid (3):

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

need. Kokku d numbrid (3); seetõttu on võrdlus (2) olemas d otsuseid.

Saame teoreemi:

68. Olgu (a, m) = d. Võrdluskirves b ( mod m) on võimatu, kui b ei jagu d-ga. Kui b on d kordne, on võrdlusel d lahendust.

69. Meetod esimese astme võrdluste lahendamiseks, mis põhineb jätkumurdude teoorial:

Seose laiendamine jätkuvaks murdosaks m:a,

ja vaadates kahte viimast sobivat murdu:

jätkuvate fraktsioonide omaduste järgi (vastavalt 30 ) meil on

Nii et võrdlusel on lahendus

leidmiseks, millest piisab arvutamiseks Pn– 1 vastavalt punktis 30 määratletud meetodile.

Näide. Lahendame võrdluse

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

Siin (111, 321) = 3 ja 75 on 3 kordne. Seetõttu on võrdlusel kolm lahendit.

Jagades mõlemad võrdluse pooled ja mooduli 3-ga, saame võrdluse

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

mille peame esmalt lahendama. Meil on

q
P 3

Niisiis, antud juhul n = 4, P n – 1 = 26, b= 25 ja meil on lahendus võrdlusele (5) kujul

x–26 ∙ 25 99 (mod 107).

Seetõttu on võrdluse (4) lahendused esitatud järgmiselt:

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

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

Pöördelemendi arvutamine antud mooduli järgi

70.Kui arvud on täisarvud a Ja n on koaprime, siis on arv a', mis rahuldab võrdlust a ∙ a′ ≡ 1 (mod n). Number a' helistas mooduli n kordav pöördpöörd ja selle jaoks kasutatud tähistus on a- 1 (mod n).

Vastastikuste suuruste arvutamine teatud väärtuse mooduli kohta võib toimuda, lahendades esimese astme võrdluse tundmatuga, milles x number aktsepteeritud a'.

Võrdluslahenduse leidmiseks

a∙x≡ 1 (mod m),

Kus ( olen)= 1,

võite kasutada Eukleidese algoritmi (69) või Fermat-Euleri teoreemi, mis väidab, et kui ( olen) = 1, siis

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

x ≡ a φ( m)–1 (mod m).

Rühmad ja nende omadused

Rühmad on üks taksonoomilisi klasse, mida kasutatakse ühiste iseloomulike omadustega matemaatiliste struktuuride klassifitseerimiseks. Rühmadel on kaks komponenti: trobikond (G) Ja operatsioonid() määratletud selles komplektis.

Hulga, elemendi ja liikmelisuse mõisted on tänapäevase matemaatika määratlemata põhimõisted. Iga hulk on määratletud selles sisalduvate elementide abil (mis omakorda võivad olla ka hulgad). Seega ütleme, et hulk on defineeritud või antud, kui mõne elemendi puhul saame öelda, kas see kuulub sellesse hulka või mitte.

Kahe komplekti jaoks A, B rekordid B A, B A, B∩ A, B A, B \ A, A × B vastavalt tähendavad seda B on hulga alamhulk A(st mis tahes element alates B sisaldub ka A, näiteks naturaalarvude hulk sisaldub reaalarvude hulgas; pealegi alati A A), B on komplekti õige alamhulk A(need. B A Ja B ≠ A), paljude ristmik B Ja A(st kõik sellised elemendid, mis asuvad samaaegselt A, ja sisse B Näiteks täisarvude ja positiivsete reaalarvude ristumiskoht on naturaalarvude hulk), hulkade liit B Ja A(st komplekt, mis koosneb elementidest, mis asuvad kas A, kas sisse B), määra erinevus B Ja A(st elementide kogum, mis asub B, aga ära valeta A), Descartes'i komplektide korrutis A Ja B(st vormi paaride komplekt ( a, b), Kus a A, b B). Via | A| kogumi võimsus on alati tähistatud A, st. elementide arv komplektis A.

Tehe on reegel, mille kohaselt hulga mis tahes kaks elementi G(a Ja b) sobitatakse G kolmanda elemendiga: a b.

Palju elemente G operatsiooniga nimetatakse Grupp, kui järgmised tingimused on täidetud.

Punktis n annavad nad samad jäägid.

Samaväärsed koostised: a ja b mooduli poolest võrreldav n kui nende erinevus a - b jagub n-ga või kui a saab esitada kui a = b + kn , Kus k- mõni täisarv. Näiteks: 32 ja −10 on võrreldavad moodul 7, kuna

Väide “a ja b on võrreldavad mooduli n” on kirjutatud järgmiselt:

Modulo võrdsuse omadused

Mooduli võrdlusrelatsioonil on omadused

Suvalised kaks täisarvu a Ja b võrreldav moodul 1.

Selleks, et numbrid a Ja b olid mooduli poolest võrreldavad n, on vajalik ja piisav, et nende erinevus jagub n.

Kui arvud ja on moodulis paarikaupa võrreldavad n, siis nende summad ja , samuti produktid ja on ka moodulis võrreldavad n.

Kui numbrid a Ja b mooduli poolest võrreldav n, siis nende kraadid a k Ja b k on ka mooduli poolest võrreldavad n mis tahes loomuliku all k.

Kui numbrid a Ja b mooduli poolest võrreldav n, Ja n jagatuna m, See a Ja b mooduli poolest võrreldav m.

Selleks, et numbrid a Ja b olid mooduli poolest võrreldavad n, mis on esitatud selle kanoonilise lagunemise kujul lihtsateks teguriteks lk i

vajalik ja piisav

Võrdlusseos on ekvivalentsuhe ja sellel on palju tavaliste võrdsuste omadusi. Näiteks saab neid liita ja korrutada: kui

Võrdlusi ei saa aga üldiselt jagada üksteise või muude arvudega. Näide: 2 võrra vähendades saame aga eksliku võrdluse: . Võrdluste lühendireeglid on järgmised.

Samuti ei saa te võrdlustega toiminguid teha, kui nende moodulid ei ühti.

Muud omadused:

Seotud määratlused

Mahaarvamise klassid

Kõikide numbrite kogum, mis on võrreldav a modulo n helistas mahaarvamise klass a modulo n ja on tavaliselt tähistatud [ a] n või . Seega on võrdlus samaväärne jäägiklasside võrdsusega [a] n = [b] n .

Alates mooduli võrdlusest n on ekvivalentsusseos täisarvude hulgal, siis jääkklassid modulo n esindavad samaväärsusklasse; nende arv on võrdne n. Kõikide jäägiklasside komplekt modulo n tähistatakse või.

Liitmise ja korrutamise toimingud indutseerivad hulgal vastavaid tehteid:

[a] n + [b] n = [a + b] n

Nende operatsioonide puhul on hulk piiratud ring ja kui n lihtne – lõplik väli.

Mahaarvamise süsteemid

Jääksüsteem võimaldab sooritada aritmeetilisi tehteid piiratud arvude hulgaga, ületamata selle piire. Täielik mahaarvamiste süsteem moodul n on mis tahes hulk n täisarvu, mis on võrreldamatud mooduli n. Tavaliselt võetakse väikseimad mittenegatiivsed jäägid tervikliku jääkide süsteemina mooduli n

0,1,...,n − 1

või absoluutselt väikseimad arvudest koosnevad mahaarvamised

paaritu korral n ja numbrid

paaritu korral n .

Võrdluste lahendamine

Esimese astme võrdlused

Arvuteoorias, krüptograafias ja teistes teadusvaldkondades kerkib sageli vormide esimese astme võrdlustele lahenduste leidmise probleem:

Sellise võrdluse lahendamine algab gcd arvutamisega (a, m)=d. Sel juhul on võimalikud 2 juhtumit:

Kui b mitte mitmik d, siis pole võrdlusel lahendusi.
Kui b mitmekordne d, siis on võrdlusel ainulaadne lahendusmoodul m / d, või mis on sama, d moodullahendused m. Sel juhul esialgse võrdluse vähendamise tulemusena d võrdlus on järgmine:

Kus a 1 = a / d , b 1 = b / d Ja m 1 = m / d on täisarvud ja a 1 ja m 1 on suhteliselt parimad. Seetõttu number a 1 saab modulo ümber pöörata m 1, st leida selline arv c, et (teisisõnu ). Nüüd leitakse lahendus, korrutades saadud võrdluse arvuga c:

Praktiline väärtuse arvutamine c saab realiseerida erineval viisil: kasutades Euleri teoreemi, Eukleidese algoritmi, jätkuvate murdude teooriat (vt algoritm) jne. Eelkõige võimaldab Euleri teoreem väärtuse üles kirjutada c nagu:

Näide

Võrdluseks on meil d= 2, seega moodul 22 on võrdlusel kaks lahendust. Asendame 26 4-ga, mis on võrreldav mooduliga 22, ja seejärel vähendame kõiki 3 arvu 2 võrra:

Kuna 2 on mooduli 11 kaasalgmäär, saame vasakut ja paremat poolt vähendada 2 võrra. Selle tulemusena saame ühe lahendi moodul 11: , mis on võrdne kahe lahendusega moodul 22: .

Teise astme võrdlused

Teise astme võrdluste lahendamine taandub sellele, et välja selgitada, kas antud arv on ruutjääk (kasutades ruutkeskmise vastastikkuse seadust), ja seejärel ruutjuure mooduli arvutamine.

Lugu

Hiina jäägiteoreem, mis on tuntud juba sajandeid, väidab (tänapäevases matemaatilises keeles), et jääkrõngas mooduli mitme koalgarvu korrutis on