Modulaararitmeetika kell

Vali moodul n ja tehe. Vaata tulemust mooduljäägi kellal ning uuri liitmis-/korrutamistabeleid.

Näidisarvutus — Modulaararitmeetika kell

Avaldis	7 x 5 (mod 12)
Tulemus	11

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Algarvuline moodul lubab jälle jagada 🖖

Modulaararitmmeetika tegeleb täisarvudega tsüklilise mooduli n all, kirjutatakse a ≡ b (mod n). See algebraline süsteem moodustab kommutatiivse ringi Z/nZ. Kui moodul p on algarv, muutub ring korpuseks, mis tähendab, et igal nullist erineval elemendil on olemas multiplikatiivne pöördelement.

Miks seda kellaaritmeetikaks nimetatakse 🖖

12-tunnisel kellal on 4 tundi pärast kella 11 hoopis 3, mitte 15 — arvud pöörduvad algusesse tagasi, kui nad ületavad 12. Just see ongi modulaararitmeetika: a ≡ b (mod n) tähendab, et a ja b annavad n-ga jagamisel sama jäägi. Seega 15 ≡ 3 (mod 12). Põhimõte on lihtne: modulaararitmeetika hoiab alles vaid jagamise jäägi, ja selle tööriista kell näitab, kuidas arvud ringi käivad.

Üheksaga jaguvuse reegel on peidetud modulaararitmeetika 🖖

Vana reegel „arv jagub 9-ga, kui tema numbrite summa jagub 9-ga“ on puhas modulaararitmeetika. Kuna 10 ≡ 1 (mod 9), on ka iga kümne aste ≡ 1, nii et arv on kongruentne oma numbrite summaga (mod 9). Sama tõsiasi on aluseks üheksaga kontrollimise võttele — sajanditevanusele viisile arvutusi käsitsi üle kontrollida.

MODULAARARITMEETIKA — MILLAL TOHIB JAGADA JA MILLAL MITTE?

Millise modulaararitmeetika juhtumiga on tegemist?

Mooduli n järgi arvutamine tähendab ainult jäägi alleshoidmist ning liitmine, lahutamine ja korrutamine peavad sellele vastu. Jagamine mitte. Kas mingi arvuga tohib jagada — kas tal on pöördarv — sõltub ainult sellest, kas tal on n-iga ühine tegur. Just seepärast käitub algarvuline moodul nii teisiti kui kordarvuline. Kumma juhtumiga on tegu, sõltub tehtest ja sellest, mis arv n on.

Liitmine — alati korralik, ükskõik milline n on 13 + 5 ≡ 6 (mod 12)

Algarvuline moodul — jagada tohib iga nullist erineva elemendiga φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Kordarvuline moodul — enamiku elementidega ei tohi jagada 2 × 3 ≡ 0, φ(6) = 2

Korduvad astmed — need käivad ringi ja Fermat ütleb, kus a^p−1 ≡ 1 (mod p)

Liitmine — alati korralik, ükskõik milline n on

Mida te teate: Ükskõik milline moodul. Liitmine, lahutamine ja korrutamine mooduli n järgi on alati määratud ja igal elemendil on liitmise vastand.

Mida kontrollida: 13 + 5 ≡ 6 (mod 12)

Näidisarvutus: 12-tunnine kell: 13 + 5 = 18 ja 18 mod 12 = 6. Viis tundi pärast kella ühte on kell kuus.

Ava see juhtum: kell mod 12

Liitmine — alati korralik, ükskõik milline n on. Liitmistabel mooduli 12 järgi: iga rida on eelmine ühe võrra nihutatuna ja iga väärtus esineb täpselt üks kord. Ükskõik milline moodul. Liitmine, lahutamine ja korrutamine mooduli n järgi on alati määratud ja igal elemendil on liitmise vastand. — Liitmistabel mooduli 12 järgi: iga rida on eelmine ühe võrra nihutatuna ja iga väärtus esineb täpselt üks kord.

Algarvuline moodul — jagada tohib iga nullist erineva elemendiga

Mida te teate: n on algarv. Siis ei jaga ükski nullist erinev element n-iga tegurit, seega on igaühel korrutamise pöördarv.

Mida kontrollida: φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Näidisarvutus: Mooduli 7 järgi: 3 × 4 = 12 ≡ 5. Kõik kuus nullist erinevat väärtust 1…6 on pööratavad, nii et korrutustabelis ei ole väljaspool esimest rida ühtki nulli.

Ava see juhtum: algarv mod 7

Algarvuline moodul — jagada tohib iga nullist erineva elemendiga. Korrutustabel mooduli 7 järgi: esimesest reast allpool ühtki nulli ja iga rida on 1 kuni 6 permutatsioon. n on algarv. Siis ei jaga ükski nullist erinev element n-iga tegurit, seega on igaühel korrutamise pöördarv. — Korrutustabel mooduli 7 järgi: esimesest reast allpool ühtki nulli ja iga rida on 1 kuni 6 permutatsioon.

Kordarvuline moodul — enamiku elementidega ei tohi jagada

Mida te teate: n on kordarv. Pöördarv on ainult n-iga ühistegurita väärtustel; ülejäänud on nullitegurid ja nendega jagamine on mõttetu.

Mida kontrollida: 2 × 3 ≡ 0, φ(6) = 2

Näidisarvutus: Mooduli 6 järgi: 2 × 4 = 8 ≡ 2. Ei 2 ega 4 ole pööratav, sest SÜT(2,6) = 2 ja SÜT(4,6) = 2. Ühikud on ainult 1 ja 5 — kaks kuuest.

Ava see juhtum: kordarv mod 6

Kordarvuline moodul — enamiku elementidega ei tohi jagada. Korrutustabel mooduli 6 järgi, nullidega üle pikitud, ja ainult kaks rida on permutatsioonid. n on kordarv. Pöördarv on ainult n-iga ühistegurita väärtustel; ülejäänud on nullitegurid ja nendega jagamine on mõttetu. — Korrutustabel mooduli 6 järgi, nullidega üle pikitud, ja ainult kaks rida on permutatsioonid.

Korduvad astmed — need käivad ringi ja Fermat ütleb, kus

Mida te teate: Astendamine mooduli n järgi. Algarvu p ja p-ga mittejaguva a puhul korduvad astendajad perioodiga, mis jagab p − 1.

Mida kontrollida: a^p−1 ≡ 1 (mod p)

Näidisarvutus: Mooduli 13 järgi: 7¹² ≡ 1. Fermat’ väike teoreem tagab selle iga alusega 1 kuni 12, ilma ühtki suurt astet välja arvutamata.

Ava see juhtum: Fermat' mod 13

Korduvad astmed — need käivad ringi ja Fermat ütleb, kus. Iga aluse astmed mooduli 13 järgi; astendaja 12 veerg naaseb iga ühiku puhul ühe juurde. Astendamine mooduli n järgi. Algarvu p ja p-ga mittejaguva a puhul korduvad astendajad perioodiga, mis jagab p − 1. — Iga aluse astmed mooduli 13 järgi; astendaja 12 veerg naaseb iga ühiku puhul ühe juurde.

Ülesanne täielikult lahendatud

7 12 mod 13 arvutamine täisruudustikul 5 sammu
Arvuta 7¹² mod 13 ilma arvu 7¹² kordagi välja kirjutamata. See on tehe a^k parameetritega n = 13, a = 7 ja k = 12 ning võrgustik on avaldise a^k mod 13 täielik tabel.
1. 7¹² on 13 841 287 201 — üksteist numbrit vastuse jaoks, mis peab tulema vahemikus 0 kuni 12. Taandamine säilib korrutamisel: korrutise jääk sõltub üksnes selle tegurite jääkidest, seega võid taandada pärast iga sammu, mitte alles lõpus.
  
  $7^{12} = 13841287201, x y mod n = ((x mod n) (y mod n)) mod n$
2. Fermati väike teoreem määrab vastuse enne igasugust arvutamist. Algarvu p ja sellise arvu a korral, mida p ei jaota, kehtib a^p−1 ≡ 1; siin on p = 13 ja k on täpselt p − 1, mistõttu tulemus on 1 ning kõik alljärgnev on teoreemi kontrollimine, mitte vastuse otsimine.
  
  $p = 13 prime, 13 ∤ 7 ⟹ 7^{12} = 7^{p - 1} \equiv 1 (mod 13)$
3. Ruutu võtmine kahekordistab astendajat, seega kolm ruutu võtmist viivad arvuni 7⁸. Igal real tehakse taandamine enne järgmise algust, mispärast ükski arv kogu arvutuses ei ületa arvu 100.
  
  $7^{2} = 49 \equiv 10, 7^{4} \equiv 1 0^{2} = 100 \equiv 9, 7^{8} \equiv 9^{2} = 81 \equiv 3 (mod 13)$
4. 12 on 8 + 4 ning mõlemad need astmed arvutati teel ülespoole, seega viib veel üks korrutamine arvutuse lõpule. Kokku neli korrutamist, võrreldes üheteistkümnega, mida vajaks kaheteistkümne seitsme korrutamine vasakult paremale — ning kokkuhoid kasvab koos astendajaga, mitte mooduliga.
  
  $12 = 110 0_{2} = 8 + 4 ⟹ 7^{12} \equiv 7^{8} \cdot 7^{4} \equiv 3 \times 9 = 27 \equiv 1 (mod 13)$
5. Arvu 7 järk ehk vähim k, mille korral 7^k ≡ 1, peab jagama arvu 12, seega on see üks arvudest 1, 2, 3, 4, 6 ja 12. Viie pärisjagaja kontrollimine välistab neist igaühe, seega on järk täpselt 12.
  
  $7^{1} \equiv 7, 7^{2} \equiv 10, 7^{3} \equiv 5, 7^{4} \equiv 9, 7^{6} \equiv 12 ⟹ ord_{13} (7) = 12$
Vastus

Kolm ruutu võtmist ja lõpetav korrutamine taastavad veatult tööriista rea väärtusele a = 7: 10 kohal k = 2, 9 kohal k = 4, 3 kohal k = 8 ja 1 kohal k = 12, kus Fermat' kohaselt see pidi olema. Kuna järk on 12, mitte selle pärisjagaja — järgu test nõudis tulemust 12 kohal k = 6, mis ei ole 1 —, on see rida arvude 1 kuni 12 permutatsioon, läbides iga mittenullise jäägi täpselt ühe korra, mis teeb arvust 7 algjuure mooduli 13 järgi. Nüüd loe rida teises suunas: kui on antud 11, leia k. Selleks ei ole ruutimis-korrutamisalgoritmi, vaid üksnes otsing, ning see asümmeetria kerge edasisuuna ja raske tagasisuuna vahel on kogu Diffie–Hellmani võtmevahetuse alus. Algoritm skaleerub viisil, mida tabel ei suuda: 2048-bitine astendaja nõuab maksimaalselt umbes 4 000 mooduliga korrutamist, samal ajal kui selle nimetatud astme väljakirjutamine nõuaks umbes 2,7 × 10⁶¹⁶ numbrit.

$ord_{13} (7) = 12 ⟹ {7^{k} mod 13}_{k = 1}^{12} = {1, 2, \dots, 12}$

Õpitee

Kui kaks asja jõuavad sama väärtuseni

Viib edasi Sünnipäevaparadoks

Allikad (1)

The congruence sign this tool prints, and the book that introduced it: C. F. Gauss, Disquisitiones arithmeticae. Leipzig, 1801 — Section I defines a ≡ b (mod n); Section II is where a prime modulus starts behaving like a field. Digitised by the Smithsonian Libraries.

42Mathi meeskond · Uuendatud 2026-08-17

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Matemaatika õppetunnid →

Näiteülesanded

kell mod 12 - Kellaaritmeetika: 13 ≡ 1 (mod 12), seega 13+5 taandub väärtuseks 6.
algarv mod 7 - Algarvuline moodul: nullist erinevad korrutamisread käituvad permutatsioonidena.
kordarv mod 6 - Liitarvuline moodul näitab korduvaid ridu, kus gcd(rida,n) > 1.
Fermat' mod 13 - Fermat' tüüpi muster: a^(p-1) ≡ 1 mod p, kui p on algarv ja gcd(a,p)=1.