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?

Az eredeti kérdésedhez:

Kezdjük a fordított irányból. Csináljunk olyan törtet, aminél a tizedesvessző után van n darab számjegy és utána kezdődik az ismétlődő szakasz, ami m hosszú.

Tehát pl. 0,12345123123123123123..., itt n=5, m=3

(Te nem azt mondanád, hogy van 5 számjegy a tizedes után, hanem azt, hogy a 6-odiktól kezdve kezdődik az ismétlés, de persze ez a kettő ugyanaz.)

Definiáljuk még jobban: olyan törtet csináljunk, ahol a tizedes után van egy n jegyű szám, aminek az értéke k (k < 10^n), utána m-jegyű számok ismétlődnek, amiknek az értéke j (j < 10^m)

Tehát pl. 0,12345123123123123123... esetén k=12345, n=5, j=123, m=3

Ezt a számot így tudjuk felírni:

x = k/10^n + j/10^(n+m) + j/10^(n+2m) + ...

Ennek a 10^m-szerese:

x·10^m = k·10^m/10^n + j/10^n + j/10^(n+m) + j/10^(n+2m) + ...

A másodikból kivonva az elsőt:

x·10^m - x = k·10^m/10^n + (j-k)/10^n

(minden más kiesett)

Fejezzük ki ebből x-et:

x = (k·10^m + j-k)/((10^m-1)·10^n)

Szóval az eddig példának felhozott 0,12345123123... ez lesz:

x₁ = (12345000+123-12345)/99900000

Most a számláló és nevező nem relatív prímek (6 a legnagyobb közös osztó), ez az egyszerűsített alak:

x₁ = 2055463/16650000

Nézd meg, tényleg 0,12345123123123...

Tudunk egyszerűbb olyan számot is csinálni, ahol n=5 és m=3. Legyen mondjuk k=0 és j=1:

x₂ = (0·10³+1-0)/99900000 = 1/9990000

Látszólag tehát a számláló bármilyen kicsi vagy nagy lehet, csak a nevező legyen 99900000.

Ez azért nem teljesen igaz. Ha relatív prímek, akkor semmi gond, az mind n=5, m=3 alakú lesz. Ha viszont van közös osztójuk, akkor már nagyon más alakú is lehet a tizedestört: pl. ha 11100000 a számláló, akkor az egyszerűsített tört 1/9, ami 0,11111..., 1 hosszú a periódus és rögtön a tizedes után kezdődik. (Annál k=11111, n=5, j=111, m=3, ez is eltorzult 5+3 alakú így...)

Szóval a számláló "mérete" nem igazán számít. A nevezőhöz nézzünk egyszerűbb esetet: m=1 (vagyis 1-szeres ismétlődés). Ez is teljesen érdekes példa, hisz téged leginkább az ismétlődés előtti szakasz hossza érdekel. Ekkor az általános képlet ezzé válik:

x = (9k + j)/(9·10^n)

A nevező prímtényezői 3^2·5^n·2^n

Mindaddig, amíg a számláló és nevező közös osztói között nincs 10, addig n számjegy lesz a tizedes után az ismétlődők előtt. 5 illetve 2 lehet a közös osztók között, de 5·2 nem.

Nézzünk néhány példát:

1/900000 = 0,00000111111...

3·5⁵/900000 = 9375/900000 = 1/96 = 0.01041666666...

...de ha már 2 is megjelenne a számlálóban, akkor csak 4 számjegy lenne az ismétlődők előtt. Tehát nem az számít, hogy relatív prímek-e, csak az, hogy ne legyen a közös osztóban 10.

Érdekesség:

Az előbb az első példában (1/900000) k=0 és j=1 volt, ezért 5 darab nullás után jött a végtelen sok 1. Ha mondjuk k=12345 és j=8, akkor (12345·9+8)/900000 = 0,12345888888... És mi van akkor, ha j=9? Akkor ugye a 9-esek ismétlődnek végtelenszer:

(12345·9+9)/900000 = 0,12345999999...

=(12345+1)·9/900000 = 0,12346

Vagyis az ugyanaz, mint amikor a 0-ák ismétlődnek végtelen sokszor...

Szóval a nevező nem is 9·10^n kell legyen, elég az is, ha 10^n, de akkor 0-ák ismétlődnek.

Ha pedig a nevező ℓ·10^n, ahol ℓ nem osztható se 2-vel se 5-tel, akkor is n darab számjegy van a tizedes után és az ismétlődés előtt. Pontosabban ha a nevező ℓ·2^n·5^m, akkor max(n,m) darab számjegy után kezd ismétlődni. Csak a nevezőtől függ tehát (persze ha a 2 illetve az 5 nem közös osztója a számlálónak és a nevezőnek).

Megjegyzés: Ez még nem bizonyítás, csak egy erős sejtés. Most éjszaka nincs energiám többre, pedig valószínű kevés hiányzik csak :)

Hú, én ezt nem bírtam követni.

Addig okés, hogy egy

x = (k·10^m + j-k)/((10^m-1)·10^n)

alakú számnál „a tizedes után van egy n jegyű szám, aminek az értéke k (k < 10^n), utána m-jegyű számok ismétlődnek, amiknek az értéke j (j < 10^m).”

De a maradékból már az állítást sem tudom kihámozni, nem hogy mi történik.

Mi lesz ebből megoldás (az ismétlődés előtti rész hossza) mondjuk p/q, (p,q)=1 alakú törtekre?

Az x = (k·10^m + j-k)/((10^m-1)·10^n) összefüggés csak bizonyos p/q relatív prím törtekre mond valamit, nem mindegyikre. A legegyszerűbb felállásban annyit mond, hogy ha q=(10^m-1)·10^n, akkor pontosan n darab tizedesjegy után kezdődnek az ismétlődő szakaszok, amik m hosszúak. p értéke mindegy mi, csak relatív prím legyen.

A hasamra ütök: ha pl. q=999900000 (n=5 darab 0 van benne és 9999=10^4-1), p pedig valami tetszőleges ezzel relatív prím, mondjuk 1234567, akkor 5 darab számjegy után kezdődnek az m=4 hosszú ismétlődések.

1234567/999900000 = 0.00123 4690 4690 4690 ...

(Az, hogy mik az értékei az ismétlődő szakaszoknak és mi az értéke a tizedes utáni n számjegynek, az a számlálótól függött, de a hosszuk nem.)

De nem csak az ilyen relatív prímekre mond valamit: az x képletében nincs ugyanis kikötve, hogy relatív prímeknek kell lenniük a számláló és nevezőnek, ezért ha a p/q relatív prímek kibővíthetőek úgy, hogy a nevező (10^m-1)·10^n legyen, akkor szintén n darab tizedes után kezdődnek az m hosszú ismétlődések. (Persze a 10-zel való bővítés nem ér, de mással lehet.)

Pl. legyen a tört p/q = 123/16160 = 3·41/(101·5·2⁵). Bővítsük ki 99·5⁴=61875-tel:

p/q = 99·5^4·3·41/(99·5^4·101·5·2^5) = 7610625/999900000 = 0.00761 1386 1386 ...

Vagyis a nevezőt ki tudtuk bővíteni úgy, hogy (10^m-1)·10^n legyen (ahol most n=5, m=4), ezért az eredeti p/q törtben is 5 számjegy után kezdődnek a 4 hosszú ismétlődések.

Ez az x képlet mást nem mond. Ami többet mondtam az általános esetről, azok a sejtések, amiknek a bizonyításán azóta se gondolkodtam :)

Az általános esethez menő első lépésként nézzük ezt:

A nevező törzstényezői között ha van 2 illetve ha van 5 valamilyen hatványon, akkor a törtet ki lehet bővíteni valamilyen 2^a·5^b számmal, hogy a nevező 10^n-nel osztható legyen, aztán valahogy még 9999..-t is bele kellene varázsolni a nevezőbe és akkor visszavezettük volna arra a képletre, amiből leolvasható a szakaszok hossza. Egyelőre ezeket az eseteket most ne is nézzük, csak azokat, ahol 2 és 5 nincs a nevező prímtényezői között.

Azokból is a legegyszerűbbeket nézzük: az olyan 1/p törteket, ahol p prím és p≠2 és p≠5. Tudunk-e találni olyan s számot, amivel ezt kibővítve (vagyis az s/(s·p) törtet nézve) a nevező 9999... alakú, vagyis s·p = 10^m-1 lesz?

A kis Fermat tétel szerint

a^(p-1) - 1 ≡ 0 (mod p)

ha p és a relatív prímek. Mivel p nem 2 és és nem 5, az alap lehet 10:

10^(p-1) - 1 ≡ 0 (mod p)

vagyis minden p prímnek többszöröse a 10^(p-1) - 1 szám!

Tehát minden prímhez találunk olyan s = (10^(p-1) - 1)/p számot, amivel kibővítve a tört a keresett alakú lesz, vagyis n=0, m=p-1 hosszakkal jellemezhető az 1/p tört.

Az m=p-1 azért nem annyira tuti, valójában p-1 valamelyik osztója is lehet a periódus hossza, nem csak p-1. Pl. p=13 esetén

1/13 = 0.0769230 076923 076923 ....

6 hosszú a periódus, ami persze felfogható 12 hosszú periódusnak is. (A Fermat tétel nem mond olyat, hogy kisebb 10^r-1 ne lehetne p többszöröse...)

Viszont n tuti nulla ilyenkor, és a kérdésed az n-re vonatkozik.

Rájöttem, hogy jóval egyszerűbben lehet kiszámolni az általános esetet, nem kell hozzá Fermat tétel sem. Igaz, hogy nem jön ki az ismétlődő szakasz hossza (vagy annak néhányszorosa), de az nem is volt kérdés...

Szóval a kulcs továbbra is az, hogy az x/((10^m-1)·10^n) alakú törteknél a tizedes után van n darab számjegy, ami után jönnek az m hosszú ismétlődő szakaszok. A számláló nem igazán fontos. A számlálótól függ persze, hogy milyen értékei lesznek ezeknek a szakaszoknak, de a hosszukat a nevező határozza meg.

Na most mi a helyzet egy p/q törttel, ahol (p,q)=1 vagyis relatív prímek?

q prímtényezőiből válasszuk külön a 2 és 5 prímeket:

q = r · 2^u·5^v

Vagyis r már sem 2-vel, sem 5-tel nem osztható.

Nevezzük u és v-ből a nagyobbikat n-nek: n=max(u,v)

Bővítsük a törtet s=2^(n-u)·5^(n-v)-nel (amiből legalább az egyik hatványkitevő persze 0), ez lesz a tört:

p/q = p·s/(r·10^n)

Be fogom bizonyítani, hogy létezik olyan t egész szám, amivel a törtet tovább bővítve ezt kapjuk:

p/q = p·s·t/(r·t·10^n) = p·s·t/((10^m-1)·10^n)

Vagyis hogy minden r-hez létezik t, hogy r·t = (10^m-1). Máshogy fogalmazva: van olyan m egész szám, aminél 10^m-1 osztható r-rel.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

A bizonyítás így megy: Vegyük a következő r elemű halmazt:

T = {9, 99, 999, ..., 10^r-1}

Két lehetőség van, ha a halmaz elemeinek r-rel vett maradékát nézzük:

a) a halmaz egyik elemének maradéka r-rel osztva 0

b) a halmaz egyik elemének sem 0 a maradéka r-rel osztva.

Utóbbi (b) esetben lássuk be, hogy a halmaz legalább 2 eleménél ugyanaz a maradék kell kijöjjön mod r:

- Összesen r-féle maradék lehetséges (0-tól r-1-ig)

- A halmaznak r eleme van, de egyiknek sem 0 a maradéka

- Ezért a skatulyaelv szerint lesz 2 egyforma maradék.

Legyenek mondjuk a T(a) és T(b) elemek azok, amiknek azonos a maradéka. Ezek különbsége természetesen már 0 maradékot ad mod r. Mondjuk ha b>a:

(10^b-1)-(10^a-1) = 10^b-10^a = 10^a·(10^(b-a)-1) ≡ 0 (mod r)

Ez viszont ellentmondás, hisz mivel r sem 2-vel sem 5-tel nem osztható, nem lehet osztója 10^a-nak, vagyis 10^(b-a)-1 ≡ 0 (mod r) kell legyen, viszont 10^(b-a)-1 eleme a halmaznak: ez éppen a T(b-a) elem.

Vagyis b) eset nincs, van a halmaznak olyan eleme, ami r többszöröse.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Ezzel bebizonyítottuk, hogy létezik olyan m, hogy 10^m-1 osztható r-rel, tehát a p/q tört kibővíthető p·s·t/((10^m-1)·10^n) alakra. Az ilyen törtekről pedig tudjuk, hogy a tizedesvessző és az első ismétlődő szakasz között n számjegy van.

Magyarul: A p/q = p/(r·2^u·5^v) törtnél a tizedesvessző után n=max(u,v) számjeggyel kezdődnek a periodikusan ismétlődő szakaszok.

(A periódus hossza m; azt csak brute force módszerrel (illetve prím nevező esetén a Fermat tétellel) lehet megtalálni, de az nem is volt kérdés.)

Ha a/b általános törtről van szó, akkor először a/b=p/q relatív prímek törtje alakra kell egyszerűsíteni, majd q-nak kell a 2-es valamint 5-ös prímtényezőit összeszámolni, amikből a nagyobbik adja a keresett értéket.

Ezzel nem is csak egy felső becslés jött ki, hogy maximum hány számjegy után kezdődik a periodikus rész, pontos értéket adunk rá.

Csak annyit értettem rajta, hogy

1/13 = 0.076923076923 076923076923 076923076923 ....

ilyen 12 hosszú periódusokat is fel lehet írni, bár van feleekkora hosszú is.