Feladat: F.3065 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Elek Péter ,  Erdélyi László ,  Farkas Péter ,  Lovász Zoltán ,  Véber Miklós 
Füzet: 1995/december, 534 - 535. oldal  PDF  |  MathML 
Témakör(ök): Euler-Fermat-tételek, Prímszámok, Maradékosztályok, Feladat
Hivatkozás(ok):Feladatok: 1995/április: F.3065

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az egyszerűség kedvéért legyen xn=aaa...ab¯, ahol az ,,a'' jegyek száma n.
Két esetet vizsgálunk attól függően, hogy x1 és a 10 relatív prímek-e.
Ha x1 és 10 nem relatív prímek, akkor van egy közös prímosztójuk (ami csak a 2 vagy az 5 lehet). Ez a prímosztó viszont mindegyik xn-nek osztója, mert

xn=x1+10⋅(10+102+103+...+10n-1)a.

Ha x1 és 10 relatív prímek, akkor bebizonyítjuk, hogy végtelen sok olyan n pozitív egész van, amelyre xn osztható x1-gyel. Ehhez először megmutatjuk, hogy létezik olyan m pozitív egész, amelyre 1+10+102+...+10m-1 osztható x1-gyel.
Válasszunk az y1=1, y2=11, y3=111, ... sorozatból két olyan elemet, amelyik x1-gyel osztva ugyanannyi maradékot ad. (Ilyen tagok léteznek, mert a sorozatnak végtelen sok tagja, maradéka viszont csak véges sok féle van.) Legyen ez a két tag yk és yl, ahol k<l. A választás szerint
yi-yk=10l-1+10l-2+...+10k=10k(1+10+102+...+10l-k-1)
osztható x1-gyel. Mivel x1 és a 10 relatív prímek, x1 relatív prím a kiemelt 10k tényezőhöz, tehát osztója kell legyen (1+10+102+...+10k-l-1)-nek. Mindez azt jelenti, hogy m=l-k megfelelő.
Legyen tehát m olyan pozitív egész, amelyre 1+10+102+...+10m-1 osztható x1-gyel. Ekkor minden k pozitív egészre
xkm+1=x1+(102+103+...+10km+1)a==x1+100a(1+10m+102m+103m+...+10(k-1)m)(1+10+102+...+10m-1)
osztható x1-gyel, tehát összetett.
 
Megjegyzések. 1. A bizonyítás második részét másképpen is el lehet mondani. Ha x1 és 10 relatív prímek, akkor a 9x1 és a 10 is relatív prímek, és az Euler‐Fermat-tétel szerint 10φ(9x1)-1 osztható 9x1-gyel. Ebből viszont következik, hogy
1+10+102+...+10φ(9x1)-1=10φ(9x1)-19
osztható x1-gyel.
2. Ha b>1, akkor x1 helyett számolhattunk volna b-vel is. A b=1 esetet azonban így is meg kellett volna vizsgálnunk.
3. A bizonyítás b-nek sok értékére egyszerű, például ha b páros, b=5 vagy b osztható 3-mal. Még a b=7 eset sem nehéz. A b=1 eset azonban további esetszétválasztást igényel, vagy pedig a látott gondolatmenet alkalmazását.