Teoria dei numeri. Congruenze. Comportamento rispetto elevamento a potenza

Elevamento a potenza

Abbiamo accennato prima alla strategia per tentativi nel caso di operazioni ripetute. Tuttavia, almeno nel caso delle potenze, esiste un metodo per calcolarne esattamente e velocemente le classi di congruenza.

Cerchiamo di arrivarci partendo dal metodo per tentativi.

ESEMPIO

Trovare la cifra delle unità di 2007²⁰⁰⁷ .

La cifra delle unità significa la sua congruenza modulo 10. Sappiamo già che è possibile ridurre la base: siccome

2007 ≡ 7, allora 2007²⁰⁰⁷ ≡ 7²⁰⁰⁷ (mod 10).

Per ridurre l’esponente, procediamo per tentativi come abbiamo visto, elencando le prime potenze di 7 modulo 10:

7⁰ ≡ 1,  7¹ ≡ 7,  7² = 49 ≡ 9,  7³ = 7²· 7 ≡ 9 · 7 = 63 ≡ 3,  7⁴ ≡ 21 ≡ 1

Siccome l’ultimo risultato è uguale al primo, e il calcolo di ogni valore dipende solo dal precedente, le potenze saranno periodiche da questo punto in poi, ovvero si otterrano gli stessi resti nello stesso ordine. In altre parole,

7¹, 7², 7³, 7⁴, 7⁵, 7⁶, 7⁷, 7⁸, 7⁹,… sono congruenti modulo 10 a 7, 9, 3, 1, 7, 9, 3, 1, 7,… rispettivamente. Quindi nel caso che stiamo trattando l’esponente si ripete ogni 4, ovvero si riduce modulo 4:

preso un numero naturale a, 7^a è congruo modulo 10 a 1, 7, 9, 3 rispettivamente nei casi a ≡ 0, 1, 2, 3 (mod 4), e quindi

7^a ≡ 7^{a mod 4} (mod 10).
2007 è congruente modulo 4 alle sue ultime due cifre, quindi 2007 ≡ 7 ≡ 3 (mod 4).

Segue che
2007²⁰⁰⁷ ≡ 7²⁰⁰⁷ ≡ 7³ ≡ 3 (mod 10). La cifra delle unità di 2007²⁰⁰⁷ quindi è 3.

Tutti i passaggi appena effettuati possono essere considerati come un’applicazione delle proprietà delle potenze:

7²⁰⁰⁷ = 7^4·501+3 = 7^4·501 · 7³ = (7⁴)⁵⁰¹ · 7³ ≡ 1⁵⁰¹ · 3 = 3 (mod 10).

Il calcolo delle potenze si riesce quindi a semplificare, riducendo anche l’esponente, se si riesce a trovare ogni quanto tempo le potenze si ripetono come prima abbiamo fatto per tentativi; e le potenze dovranno per forza ripetersi da un certo punto in poi dato che i valori che possono assumere sono finiti (da 0 a m − 1 se stiamo considerando resti modulo m).
Il periodo con il quale si ripetono le potenze di un numero, 4 nell’ esempio precedente, si chiama ordine moltiplicativo di 7 modulo 10: in generale dato un a con MCD(a,m) = 1, si chiama ordine moltiplicativo di a modulo m, e si scrive ord_a (m), il più piccolo intero positivo tale che

aⁿ ≡ 1(mod m).
Inoltre definiamo ord (m) il massimo degli ordini moltiplicativi ord_a (m) al variare di a. Per fortuna,il valore ord (m) si riesce a calcolare facilmente ed è anche possibile utilizzarlo al posto di ord_a (m).
Infatti vale sempre, per ogni a, che:

ord_a (m) | ord (m)

Il che si traduce nel fatto che:

Quindi l’ordine moltiplicativo è proprio il modulo con il quale ridurre l’esponente.
L’ordine moltiplicativo, nel caso di un modulo m = p^k potenza di un primo, è il massimo che ci si potrebbe aspettare: cioè è pari al numero di elementi non multipli di p fino a p^k(è evidente che un a non multiplo di p non può diventarne multiplo facendo delle potenze). I multipli di p sono uno.

(433)