Divisjonsregler for 3 og 9

[Markus]

I en av oppgavene plutarco la ut som øving til Abelkonkurransen, skulle man finne ut om $1234567891011\dots 9899100$ var delelig på 3. Hintet sa at hvis dette skulle være sant måtte tverrsummen være delelig på $3$. Jeg begynte å tenke over hvorfor det må være sånn, og tenkte på om følgende er bevis på hintet.

La oss si at vi har et fem-sifret tall $n$:

$n=a\cdot {10}^4+b\cdot {10}^3+c\cdot {10}^2+d\cdot {10}^1+e$

$n=a(9999+1)+b(999+1)+c(99+1)+d(9+1)+e$

$n=9999a+999b+99c+9d+a+b+c+d+e$.

Siden alle tall som skrives på formen $999$, $9999999$ osv har $3$ som faktor må alle slike tall være delelig på $3$ (de kan skrives som $3^2({10}^n+{10}^{n-1}+\cdots +{10}^0)$). I dette tilfellet får vi:

$n=3(3333a+333b+33c+3d)+a+b+c+d+e$

Hvis $n$ skal være delelig på $3$ må altså $a+b+c+d+e$ være delelig på $3$, slik at $3$ er en felles faktor for alle leddene i $n$.

Siden $a+b+c+d+e$ er tverrsummen betyr det altså at tverrsummen må være delelig på $3$. Dette stemmer for alle tall med $k$ siffer, da hver tierplass, hundrerplass, tusenplass, titusenplass osv. kan skrives på formen ${10}^m-1+1$.

Fungerer argumentasjonen, og kan man med samme argumentasjon også vise at hvis et tall er delelig på $9$, må også tverrsummen være delelig på $9$?

[Gustav]

Det er helt riktig.

Påstandene er også bevist her https://artofproblemsolving.com/wiki/in ... nd_9_proof

[Gustav]

Oppfølger: Vis følgende:

Et positivt heltall $N$ er delelig med $2^n$ hvis og bare hvis de $n$ siste sifrene er delelig med $2^n$. (F.eks er $27104$ delelig med $2^3=8$ siden $104=8\cdot 13$ er delelig med $8$.)

[Markus]

Hm, jeg har tenkt på denne en stund nå plutarco. Kunne du kommet med noen hint?

[Gustav]

Hint: Skriv tallet på samme form som i ditt forrige bevis. Og så kan man bruke at $2^n$ deler ${10}^m$ for alle $m\ge n$

[Markus]

Okei - jeg tror jeg har noe som kan ligne på et bevis nå.

Jeg bruker lemmaen (muligens ikke helt rett ordbruk?) din om at $2^n\mid {10}^m,\mathrm{\forall }m\ge n$

La oss si at $N$ er et $6$-sifret tall, da har vi at:
$N=a\cdot {10}^5+b\cdot {10}^4+c\cdot {10}^3+d\cdot {10}^2+e\cdot 10+f$

Hvis for eksempel $2\mid f$, følger det også at $2\mid 10,{10}^2,\dots ,{10}^5$ av lemmaen.
Da vil alle følgende leddene i $N$ være delelig på $2$, da ${10}^m$ er en faktor i alle, og $m\ge 1$.

Hvis for eksempel $2^3\mid d\cdot {10}^2+e\cdot 10+f$, følger det også at $2^3\mid {10}^3,{10}^4,{10}^5$, og siden ${10}^3,{10}^4,{10}^5$ er faktorer i de neste kommende leddene i $N$ betyr det at $2^3|a\cdot {10}^5+b\cdot {10}^4+c\cdot {10}^3$.

Kan dette ligne på noe? Jeg sliter dog med å generalisere og å vise hvis og bare hvis-delen.

[Gustav]

Helt rett det du skriver ja. Vi kan generalisere på følgende måte:

Skriv $N=\sum _{i=0}^m{a}_i{10}^i$.

$\Rightarrow$: Anta at $2^n$ deler $N$ der $0<n\le m$ (tilfellene $n=0$ og $n=m+1$ er trivielle). Siden $2^n$ deler ${10}^i$ for alle $i\ge n$, så vil $2^n$ dele $\sum _{i=n}^m{a}_i{10}^i$ og dermed også $N-\sum _{i=n}^m{a}_i{10}^i=\sum _{i=0}^{n-1}{a}_i{10}^i$.

$\Leftarrow$: Anta at $2^n$ deler de $n$ siste sifrene, $\sum _{i=0}^{n-1}{a}_i{10}^i$. Da vil $2^n$ dele $\sum _{i=n}^m{a}_i{10}^i+\sum _{i=0}^{n-1}{a}_i{10}^i=N$.

PS: Det samme vil jo funke med $5^n$ istedet for $2^n$

[Markus]

Takker for generaliseringen!

Det vil også funke med $5^n$ fordi ${10}^n=5^n\cdot 2^n$?

Og til hvis og bare hvis-delen: Hvis $2^n$ ikke deler de $n$ siste siffene, impliserer det nødvendigvis til at $N$ ikke er delelig med $2^n$? Beklager hvis jeg spør dumt, men er ikke så veldig god på bevis.

[Gustav]

- Det stemmer!

- Tenk Venn-diagram i slike tilfeller. A,B er to sirkler som representerer to utsagn. Implikasjonen $A\Rightarrow B$ betyr at sirkel A ligger inni sirkel B. $B\Rightarrow A$ betyr at sirkel B ligger inni A. $A\iff B$, som er det samme som hvis og bare hvis, betyr at sirkel A og B overlapper perfekt.

[Markus]

- Det stemmer!

- Tenk Venn-diagram i slike tilfeller. A,B er to sirkler som representerer to utsagn. Implikasjonen $A\Rightarrow B$ betyr at sirkel A ligger inni sirkel B. $B\Rightarrow A$ betyr at sirkel B ligger inni A. $A\iff B$, som er det samme som hvis og bare hvis, betyr at sirkel A og B overlapper perfekt.

Det var en veldig fin måte å fremstille det på. Det oppklarte det, tusen takk!