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} + \dots + 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\geq 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, \forall m \geq 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 \geq 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\leq m$ (tilfellene $n=0$ og $n=m+1$ er trivielle). Siden $2^n$ deler $10^i$ for alle $i\geq n$, så vil $2^n$ dele $\sum_{i=n}^ma_i 10^i$ og dermed også $N-\sum_{i=n}^ma_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}^ma_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 \Leftrightarrow 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 \Leftrightarrow 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!