esempi d’uso del teorema di Eulero e di Fermat

Esempi

Trovare l’ultima cifra di 7^143

Chiedere l’ultima cifra di un numero sottende la scelta di un sistema numerico. Ovviamente non essendo specificato si assume per convenzione sia quello decimale. Vogliamo quindi calcolare la congruenza modulo 10 del numero in questione. (Per trovare le ultime due cifre dovremmo usare la congruenza mod 100)

Calcoliamo dunque $\phi (10)=4$ e notiamo inoltre che $7$ è primo con 10, dunque $7^4\equiv 1(\mathrm{mod}10)$ per il teorema di Eulero.

Sfruttando la divisione euclidea per 4 otteniamo: $143=35\cdot 4+3$ e per le usuali proprietà delle potenze abbiamo che:

$$7^{143}=(7^4{)}^{35}\cdot 7^3.$$

Sappiamo che $(7^4{)}^{35}\equiv 1(\mathrm{mod}10)$ e quindi $7^{143}\equiv 1\cdot 7^3(\mathrm{mod}10)$. Il problema si è ora ridotto al calcolo dell’ultima cifra di $7^3$. Lo si può fare con la forza bruta o in alternativa utilizzando le congruenze:

• $7^3=7^2\cdot 7$
• $7^2=49\equiv 9(\mathrm{mod}10)$
• $9\cdot 7=63\equiv 3(\mathrm{mod}10)$

Risultato: L’ultima cifra di $7^{143}$ è $3$.

Divisibilità per 7

Provare che $3n^7+4n^{19}+2n+5n^{31}$ è divisibile per 7 per ogni numero $n$.

Vogliamo considerare la congruenza mod 7. Osserviamo anzitutto che 7 è primo e dunque ci sono i presupposti per l’utilizzo del teorema di Fermat.

Dall’Osservazione 65 possiamo dire che:

• I termine: $3n^7\equiv 3n(\mathrm{mod}7)$

• II termine: Utilizzando la divisione euclidea per 7 otteniamo $19=2\cdot 7+5$ e per le proprietà delle potenze $4n^{19}=4\cdot (n^7{)}^2\cdot n^5$ che per l’Osservazione 65

  $$\equiv 4n^2\cdot n^5(\mathrm{mod}7)\equiv 4n^7(\mathrm{mod}7)\equiv 4n(\mathrm{mod}7)$$

• III termine: $2n\equiv 2n(\mathrm{mod}7)$

• IV termine: Analogamente a quanto sopra $5n^{31}=5\cdot (n^7{)}^4\cdot n^3\equiv 5n^4\cdot n^3(\mathrm{mod}7)\equiv 5n^7(\mathrm{mod}7)\equiv 5n(\mathrm{mod}7)$

Ci riconduciamo dunque alla divisibilità per 7 di:

$$3n+4n+2n+5n=14n$$

che è banalmente vero poiché $14n\equiv 0(\mathrm{mod}7)$ per ogni $n\in \mathbb{Z}$.

Provare che 511 non è un numero primo

Supponiamo che esso sia primo e dunque $\phi (511)=510$ (Osservazione 62.ii), consideriamo $2^{\phi (511)}=2^{510}$ (ovvero $2^{p-1}$), dovremmo avere per Fermat che:

$$2^{510}\equiv 1(\mathrm{mod}511).$$

Osserviamo che $511=512-1=2^9-1$, quindi $2^9-1\equiv 0(\mathrm{mod}511)$, ovvero:

$$2^9\equiv 1(\mathrm{mod}511).$$

D’altra parte, usando la divisione euclidea per 9, abbiamo $510=9\cdot 56+6$ e quindi:

$$2^{510}=(2^9{)}^{56}\cdot 2^6\equiv 2^6(\mathrm{mod}511)$$

Il che è assurdo perché comporterebbe $1=2^6$.

Conclusione: L’assurdo dimostra che 511 non può essere primo.

Risorse