Liigu sisu juurde

Kuidas modulo töötab, ka negatiivsete arvudega?

Jäägid igas märgireeglis, astmed ja pöördarvud mooduli järgi, elaval numbrilaual.

Tehe

−31 mod 12

5

−31 = −3 × 12 + 5: jääk on see, mis jääb alles pärast arvu 12 täisarvuliste kordsete ära võtmist.

Põhiväärtused tabelina
Märgireegelqr
Mitte kunagi negatiivne (matemaatika)−35
Arvu n märk (Python, Excel)−35
Arvu a märk (JavaScript, C, Java)−2−7
Jagatis q
−3
Kongruents
−31 ≡ 5 (mod 12)
Mitte kunagi negatiivne (matemaatika)
5
Arvu n märk (Python, Excel)
5
Arvu a märk (JavaScript, C, Java)
−7

Jäägid igas märgireeglis, astmed ja pöördarvud mooduli järgi, elaval numbrilaual.

Kuidas kasutada

  1. Vali a mod n, aste mooduli järgi aᵇ mod n või pöördarv mooduli järgi a⁻¹ mod n.
  2. Sisesta täisarvud või lohista punkti ümber numbrilaua, et arvu a muuta.
  3. Negatiivse arvu puhul vali sobiv märgireegel; matemaatika, Pythoni ja JavaScripti vastused on loetletud kõrvuti.

Kuidas see töötab

a mod n on jääk r pärast arvu n täisarvuliste kordsete ära võtmist: a = q × n + r. Mõtle numbrilauale n arvuga, 0 üleval: alusta nullist ja astu a sammu (negatiivse a puhul tagasi); r on koht, kuhu jõuad. 31 tundi enne südaööd näitab 12-tunnine kell 5, sest −31 = −3 × 12 + 5.

Negatiivsete arvude puhul erinevad reeglid selles, millise nime nad sellele kohale annavad. Matemaatika kasutab eukleidilist jääki, mis ei ole kunagi negatiivne (0 ≤ r < |n|). Python ja Excel ümardavad q allapoole, seega on r-il arvu n märk. JavaScripti %, C ja Java ümardavad q nulli poole, seega on r-il arvu a märk: −31 % 12 on seal −7. Vastused erinevad n võrra ja on kongruentsed: −7 ≡ 5 (mod 12).

Astmeid mooduli järgi leitakse korduva ruutu võtmisega: 4¹³ mod 497 = 445, ilma et 4¹³ tuleks kunagi täielikult välja kirjutada. Arvu a pöördarv on x, mille puhul a × x ≡ 1 (mod n), leitud laiendatud Eukleidese algoritmiga: 3 × 4 = 12 ≡ 1 (mod 11), seega 3⁻¹ mod 11 = 4. See on olemas ainult siis, kui arvudel a ja n pole ühist tegurit. Allikad: Khan Academy, modulaararitmeetika; OpenStax Contemporary Mathematics, jaotis 3.7.

Arvutusnäide

Mis on −31 mod 12?

  1. Kirjuta −31 = q × 12 + r. Matemaatikas q = −3, seega r = −31 − (−3 × 12) = 5.
  2. JavaScript ja C ümardavad jagatise hoopis nulli poole: q = −2, seega jääk on −7.

5 matemaatikas ja Pythonis, −7 JavaScriptis; need erinevad arvu 12 võrra.

Korduma kippuvad küsimused

Miks annab −7 % 3 JavaScriptis −1, aga Pythonis 2?

JavaScript ümardab jagatise nulli poole (−2), seega on jääk −7 − (−6) = −1. Python ümardab allapoole (−3), seega on see −7 − (−9) = 2. Mõlemad on oma reegli järgi õiged.

Kuidas saada koodis alati mittenegatiivne jääk?

Kasuta positiivse n puhul avaldist ((a % n) + n) % n. See muudab JavaScripti või C kärbitud jäägi eukleidiliseks.

Kus kasutatakse modulaararitmeetikat?

Kellades ja kalendrites, kontrollnumbrites nagu IBAN ja ISBN, räsitabelites ning avaliku võtmega krüptograafias nagu RSA, mis tugineb astmetele ja pöördarvudele mooduli järgi.

Miks arvul 4 mod 6 pöördarvu pole?

Arvudel 4 ja 6 on ühine tegur 2, seega on iga arvu 4 kordne mooduli 6 järgi paaris ega saa kunagi olla 1.

Mis vahe on jäägil mod ja jäägil remainder?

Positiivsete arvude puhul vahet pole. Negatiivsete puhul annab „mod“ tavaliselt tulemuse vahemikus 0 kuni n − 1 (või n märgiga), „jääk“ aga, nagu JavaScripti %, võtab arvu a märgi.

Saada tagasisidet