Két egész szám hányadosaként előálló tizedes tört tizedesjegyei maximum hány tizedes jegy után fognak ismétlődni periodikusan az osztó és az osztandó méretének függvényében?
A periódus hosszát nem csak prím esetén lehet kiszámolni brute force nélkül:
Az egész abból jön, hogy a kis Fermat tételnek van általánosítása, az Euler-Fermat tétel: Ha a és m relatív prímek, akkor
a^φ(m) ≡ 1 (mod m)
ahol φ(m) az Euler-féle φ függvény. (Prímek esetén φ(p) = p-1, ebből jön ki speciális esetként a kis Fermat tétel.)
Ráadásul van még a λ(m) Carmichael-függvény is, amihez a Carmichael tétel kimondja, hogy
a^λ(m) ≡ 1 (mod m)
A tétel szerint λ(m) a legkisebb szám, amire ez a hatvány-kongruencia teljesül tetszőleges a és m relatív prímek esetén.
Sok számra λ(m) = φ(m), de néha kisebb (valahányad-része). És ha kisebb, az azt jelenti, hogy kevesebb esetet kell megnézni, hogy melyik 10^x-1 szám a nevező többszöröse. Ugyanis bár a Carmichael tétel szerint λ(m) a legkisebb kitevő, de ez csak azt jelenti, hogy tetszőleges a-ra nézve nem találunk kisebbet. Adott esetben a=10-re lehet, hogy már kisebb számra is teljesül a 10^x ≡ 1 (mod m) egyenlőség, és ez az x ekkor λ(m) valamelyik osztója lesz.
Nem részletezem, nézz utána ezeknek a tételeknek, ha ki akarod viszonylag gyorsan számolni a periódus hosszát is.
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!