Alice, Bob e Eva — Esercizi

91⁴ + 92⁴ + 93⁴ + 94⁴ + 95⁴ ≡ x mod 5

“Allora, come va con l'esercizio?”.

“Ehm”.

“Niente?”.

“Mah, no, qualcosa ho fatto, ma mi sfugge la visione globale”.

“Questa scusa devo passarla ai miei studenti”.

“Uffa. Come dovrei procedere?”.

“Comincia a calcolare il resto della divisione per 5 di ognuna delle basi”.

“Ok, questo è facile: 91 dà resto 1 nella divisione per 5, 92 invece 2, e così via”.

“Fino a 95”.

“Sì, giusto: 95 dà resto 0”.

“Benissimo. Ora eleva questi resti alla quarta”.

“Ah, capisco: sto applicando la proprietà delle potenze, vero?”.

“Esatto. Prima ti calcoli a ≡ x mod 5, poi calcoli x⁴ ≡ y mod 5. Se a ≡ x, anche a⁴ ≡ x⁴”.

“Quindi, per capire, dato che 91 ≡ 1 allora 91⁴ ≡ 1⁴?”.

“Esatto. Prosegui con gli altri numeri, adesso”.

“Allora, 92 ≡ 2, quindi 92⁴ ≡ 16”.

“Dato che 16 è maggiore di 5, vai avanti e calcola 16 mod 5”.

“Giusto; risulta ancora 1”.

“Esatto. Vai avanti ancora”.

“Vediamo: 93 ≡ 3, quindi 93⁴ ≡ 81 ≡ 1, poi abbiamo 94 ≡ 4, quindi 94⁴ ≡ 256 ≡ 1, e infine 95 ≡ 0 e quindi 95⁴ ≡ 0”.

“Ottimo. Quindi il risultato della nostra espressione è 4”.

“Bello, anche se non è del tutto immediato”.

“In che senso?”.

“Nel senso che i numeri diventano grossi ugualmente. Insomma, anche se non è un numero gigantesco, 256 è pur sempre un numero di tre cifre”.

“Capisco che sei calcolatrice-dipendente, ma non è necessario arrivare fino a 256. Voglio dire, sai già che 94 ≡ 4, no?”.

“Certo, questo è facile”.

“Allora puoi dire che 94⁴ ≡ 4⁴ ≡ 4²·4². Ora i calcoli sono più semplici, no?”.

“In effetti, sì: 4² = 16 ≡ 1, quindi 4⁴ ≡ 1² ≡ 1”.

“Bene. Quindi hai calcolato il resto della divisione per 5 di una espressione senza calcolarne esplicitamente il valore (che, detto per inciso, è un numero abbastanza grande: 374544979)”.

“Niente male”.

“E nota che puoi farlo anche per numeri molto più grandi. Prova questo, per esempio:”.

91¹⁰⁰ + 92¹⁰⁰ + 93¹⁰⁰ + 94¹⁰⁰ + 95¹⁰⁰ ≡ x mod 5

“Alla cento?”.

“Sì”.

“Ehi, mi stai fregando, io so già che i numeri da 91 a 95 nella congruenza modulo 5 valgono tutti 1, tranne l'ultimo che vale 0”.

“E quindi?”.

“E quindi se elevo 1 alla 100 ottengo sempre 1. Il risultato è 4 anche qui”.

“Benissimo! Visto che la calcolatrice non serve? Ora, però, facciamo un calcolo che non è una fregatura:”.

91¹⁰⁰ + 92¹⁰⁰ + 93¹⁰⁰ + 94¹⁰⁰ + 95¹⁰⁰ ≡ x mod 7

“Uh, modulo 7, cosa cambia?”.

“Prova a calcolare 91 mod 7”.

“91 è un multiplo di 7, quindi 91 ≡ 0”.

“Questa era facile. Passa al 92”.

“Bè, se 91 ≡ 0, allora 92 ≡ 1. Facile anche questa”.

“Avanti”.

“Non mi sembra così difficile: 93 ≡ 2, facile”.

“Ah, vedo che hai dimenticato che devi poi elevare alla 100. Fino a che si tratta di 0 e di 1, è facile elevarli. Ora però hai a che fare con 2¹⁰⁰”.

“Posso usare la calcolatrice?”.

“Ti pare una domanda da fare?”.

“Ok, ok. Allora, come faccio?”.

“Una buona cosa, come hai visto, è quando ottieni un resto uguale a 1”.

“Bene, quindi?”.

“Comincia ad analizzare le potenze di 2, modulo 7”.

“Allora, 2¹ ≡ 2, 2² ≡ 4, 2³ ≡ 8 ≡ 1. Ecco, ho trovato un 1”.

“Bene, ora sai che se prendi tre fattori 2 alla volta ottieni sempre un 1. Quindi come puoi fare per calcolare 2¹⁰⁰?”.

“Vediamo, raggruppare a tre alla volta significa dividere per 3, ma 100 non è divisibile per 3, quindi avrò un resto. Cioè, avrò resto 1, giusto?”.

“Sì, in pratica hai calcolato 2¹⁰⁰ = 2⁹⁹·2 = (2³)³³·2 ≡ 1³³·2 ≡ 2”.

“Ok, allora provo con 3. Vediamo, 3² = 9 ≡ 2, 3³ = 27 ≡ 6”.

“Ti potrebbe forse essere d'aiuto notare che 3³ ≡ 6 ≡ -1”.

“Meno uno?”.

“Sì, ricordati dell'orologio: se 7 corrisponde a 0, 8 corrisponde a 1, 6 corrisponde a -1”.

“Sì, è vero, mi avevi detto che questi calcoli funzionano anche con i numeri negativi. Ma perché mi è utile?”.

“Perché se 3³ ≡ -1, allora 3⁶ ≡ (-1)² ≡ 1, ed ecco che hai trovato la tua potenza uguale a 1”.

“Perfetto. Allora 3¹⁰⁰ può essere scritto come 3⁹⁶·3⁴ ≡ 3⁴ ≡ 81 ≡ 4”.

“Rimane 4¹⁰⁰. E ricordati che 4 è una potenza di 2”.

“Giusto, dato che ho scoperto prima che 2³ ≡ 1, posso dire che anche 2⁶ ≡ 1. Però 2⁶ = 4³, quindi ecco che ho trovato la potenza uguale a 1: 4³ ≡ 1”.

“E quindi ora è facile: 4⁹⁹ sarà congruente a 1, e quindi 4¹⁰⁰ ≡ 4”.

“E finalmente posso trovare quello che mi hai chiesto: il risultato è 1+2+4+4 = 11 ≡ 4”.

“Senza dover calcolare il numerone”.

“Mh, però c'è qualcosa che non mi convince”.

“Cosa?”.

“Questi calcoli funzionano se riesco a trovare una potenza congruente a 1. Siamo sicuri che la trovo sempre?”.

“Bella domanda”.

⇐ · ⇒