[Risolto] resto della divisione di 2^n per 7

n = 0    2^0 mod 7 = 1

n = 1    2^1 mod 7 = 2

n = 2    2^2 mod 7 = 4

n = 3    2^3 mod 7 = 1

n = 4    2^4 mod 7 = 2

n = 5    2^5 mod 7 = 4

... e così via

2^n mod 7 = 2^(n mod 3)

Questa é la spiegazione intuitiva

Ora per dimostrarlo usiamo l'induzione matematica

per n = 0 é vero : 2^0 mod 7 = 1   e 2^(0 mod 3) = 2^0 = 1

Sia vero per il generico n

2^(n+1) mod 7 = ( 2*2^n mod 7 ) = (2^n mod 7 + 2^n mod 7) mod 7 =

= (2^(n mod 3) + 2^(n mod 3) ) mod 7

Se n mod 3 <= 1 si può eliminare il mod7 finale

2^0 + 2^0 = 2 e 2 mod 7 = 2

2^1 + 2^1 = 4 e 4 mod 7 = 4

ottenendo  2*2^(n mod 3) = 2^(n mod 3 + 1) = 2*[(n+1) mod 3]

perché gli ultimi due esponenti sono uguali se n mod 3 non é 2

se n mod 3 = 2 invece si può scrivere

(2^2 + 2^2) mod 7 = 8 mod 7 = 1 = 2^0 = 2^[(n+1) mod 3]

e siamo arrivati ugualmente.

"Dire qual è ..." al singolare è IMPOSSIBILE: i resti possibili sono tre e si ripetono ciclicamente.
"il resto della divisione di 2^n per 7" si chiama "2^n mod 7" o "2^n % 7".
I tre valori possibili di "2^n mod 7" dipendono, come segue, dalla forma di n in funzione di un parametro k non negativo.
* per n = 3*k + 0, 2^n mod 7 = 1 = 2^0
* per n = 3*k + 1, 2^n mod 7 = 2 = 2^1
* per n = 3*k + 2, 2^n mod 7 = 4 = 2^2
cioè
* per n = 3*k + q, 2^n mod 7 = 2^q
dove
* (k >= 0) & (q in {0, 1, 2})
"essendo n>3" vuol dire iniziare la successione ciclica da quattro e non da zero.