Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.
Okey, la oss gjøre dette aritmetisk først, og så benytte oss av modulær aritmetikk:
Alle tall kan skrives som
a + b*10 + c*10^2 + ... + n*10^n
=a + b*(3^3+1) + c*(3^3+1)^2 + ... + n*(3^3+1)^n
Som vi vet så vil (9+1)^n være lik
nC0*9^n + nC1 * 9^(n-1) + ... + nCn *1
-> 9=3^3 er faktor i alt untatt siste ledd som er 1
Dermed blir a*(9+1)^n = a(3P + 1) = 3Pa + a
og a + b*10 + c*10^2 + ... + n*10^n
= a + (3Pb + b) + (3Qc + c) + .... + (3Rn + n)
= 3(Pb + Qc + ... + Rn) + (a + b + c + ... +n)
Som jo er delelig med 3 hvis a + b + c + ... +n) er delelig med 3.
QED
Samme bevis kan brukes for deling med 9, og deling med (n-1) i base n
Ved modulær aritmetikk:
10 [symbol:identisk] 1 (mod 3)
a [symbol:identisk] b (mod n)
-> a^n [symbol:identisk] b^n (mod n)
Dermed:
a + b*10 + c*10^2 + ... + n*10^n [symbol:identisk] a + b + c + ... + n (mod 3)