matematikk.net

Vis at det for ethvert positivt heltall n eksisterer et annet positivt heltall som er delelig på n og bare består av sifrene 7 og 0.

Hvis vi kan vise dette hvor vi bytter ut 7 med 1, følger påstanden og dette er vel også litt sterkere. Jeg prøver.

La først n være et tall som ikke har 2, 3 eller 5 som faktor. Da er gcd(n,10)=1 og Eulers teorem gir at n går opp i [tex]10^{\phi(n)}-1[/tex]. ([tex]\phi(n)[/tex] er Eulers phi-funksjon; antall positive heltall mindre enn n som er koprime til n.) Vi får nå at

[tex]\frac{10^{\phi(n)}-1}9 = \overbrace{111\dots111}^{\phi(n)\, \rm{1-ere}}[/tex]

Siden gcd(n,9)=1, vil n gå opp i venstresida og følgelig høyresida. Kall nå tallet med mange 1-ere over for x.

Hvis nå n hadde 3 som en faktor, si med multiplisitet a, gjør prosessen som over med tallet n delt på 3^a.

Betrakt så talla [tex]\sum_{i=0}^j 10^{\phi(n)\cdot i}x[/tex] for [tex]j=0,1,\dots,3^a[/tex]. Disse 3^a+1 talla vil alle bestå utelukkende av 1-ere. Men ved php vil minst 2 av disse være like modulo 3^a, så vi kan ta differansen mellom 2 slike. Denne består nå utelukkende av 1-ere 0-er og har altså 3^a som en faktor, så n vil også være en faktor i dette tallet.

Om tallet nå skulle ha 2 og/eller 5 som faktorer, slenger vi bare på et passelig antall 0-er på slutten.

Noen sluttkommentarer: Beviset over er bare et eksistensbevis hvis 3 er en faktor i n. Det beskriver en måte å finne det ønskede multippel på, men hvis 3 forekommer mange ganger i primtallsfaktoriseringa til n, blir det fort vanskelig å finne et konkret tall. Jeg ville tro det finnes andre beviser enn mitt som konstruerer et tall med den ønskede egenskap.

Hvis vi jenker litt på krava, kan vi gjøre dette resultatet litt sterkere. For eksempel vil alle det for primtall p finnes et tall på formen 111...111 hvor p er en faktor.

Æsj, nå innså jeg akkurat at jeg kunne fått medalje i VM i omstendelige bevis.

Vi ser bare på talla 7, 77, 777,..., 7 n+1 ganger. Minst to av disse vil være kongruente modulo n ved duehullprinsippet (noen må seriøst finne et bedre navn på dette), så differansen vil være delelig med n og vi har konstruert et tall på formen 77...7700..0 hvor n er en faktor.

Jeg likte det siste beviset best, ja

Mitt gikk ut på å ta for seg [tex]\{7 \cdot 10^i \} _{i \geq 0} [/tex] i [tex]\mathbb{Z}_n[/tex]. Fra et visst ledd må følgen ha en endelig periode. La oss si perioden er p. (Hvis n er koprim med 7 kan vi bruke phi-funksjonen for å finne en periode.) Sum over (et multiplum av) n ledd som alle ligger p ledd fra hverandre innenfor den periodiske delen av følgen. Resultatet må være delelig med n.