Esercizi sul Teorema di Fermat

Esercizi sul Teorema di Fermat

+Esercizi sul Teorema di Fermat

Versione italiana

Esercizi sul Teorema di Fermat

Il Teorema di Fermat, noto anche come Teorema di Fermat sui numeri primi, afferma che:

Se p$p$ è un numero primo e a$a$ è un intero non divisibile per p$p$, allora:

a^{p-1} \equiv 1 \mod p $a^{p-1} \equiv 1 \mod p$

Concetti Chiave

1. Numeri Primi: Un numero primo è un numero maggiore di 1 che ha solo due divisori: 1 e se stesso.
2. Congruenza: L'espressione a \equiv b \mod m$a \equiv b \mod m$ significa che a$a$ e b$b$ hanno lo stesso resto quando divisi per m$m$.
3. Potenza Modulare: Rappresenta il risultato di elevare un numero a una potenza e poi prendere il resto rispetto a un altro numero.

Esercizi

Esercizio 1

Verifica il Teorema di Fermat per a = 2$a = 2$ e p = 5$p = 5$.

Soluzione:

Calcoliamo 2^{5-1} \mod 5$2^{5-1} \mod 5$:

2^4 = 16 $2^4 = 16$

Ora calcoliamo 16 \mod 5$16 \mod 5$:

16 \div 5 = 3 \quad \text{(resto 1)} $16 \div 5 = 3 \quad \text{(resto 1)}$

Quindi:

2^4 \equiv 1 \mod 5 $2^4 \equiv 1 \mod 5$

Esercizio 2

Verifica il Teorema di Fermat per a = 3$a = 3$ e p = 7$p = 7$.

Soluzione:

Calcoliamo 3^{7-1} \mod 7$3^{7-1} \mod 7$:

3^6 = 729 $3^6 = 729$

Ora calcoliamo 729 \mod 7$729 \mod 7$:

729 \div 7 = 104 \quad \text{(resto 1)} $729 \div 7 = 104 \quad \text{(resto 1)}$

Quindi:

3^6 \equiv 1 \mod 7 $3^6 \equiv 1 \mod 7$

Esercizio 3

Dimostra che se p = 11$p = 11$ e a = 4$a = 4$, allora 4^{10} \equiv 1 \mod 11$4^{10} \equiv 1 \mod 11$.

Soluzione:

Calcoliamo 4^{10} \mod 11$4^{10} \mod 11$:

4^{10} = 1048576 $4^{10} = 1048576$

Ora calcoliamo 1048576 \mod 11$1048576 \mod 11$:

1048576 \div 11 = 95324 \quad \text{(resto 2)} $1048576 \div 11 = 95324 \quad \text{(resto 2)}$

Quindi:

4^{10} \equiv 2 \mod 11 $4^{10} \equiv 2 \mod 11$

In questo caso, il Teorema di Fermat non è soddisfatto, poiché 4$4$ è divisibile per 11$11$.

English version

Fermat's Theorem Exercises

Fermat's Theorem, also known as Fermat's Prime Number Theorem, states that:

If p$p$ is a prime number and a$a$ is an integer that is not divisible by p$p$, then:

a^{p-1} \equiv 1 \mod p $a^{p-1} \equiv 1 \mod p$

Key Concepts

1. Prime Numbers: A prime number is a number greater than 1 that has only two divisors: 1 and itself.
2. Congruence: The expression a \equiv b \mod m$a \equiv b \mod m$ means that a$a$ and b$b$ have the same remainder when divided by m$m$.
3. Modular Power: Represents the result of raising a number to a power and then taking the remainder with respect to another number.

Exercises

Exercise 1

Verify Fermat's Theorem for a = 2$a = 2$ and p = 5$p = 5$.

Solution:

Let's calculate 2^{5-1} \mod 5$2^{5-1} \mod 5$:

2^4 = 16 $2^4 = 16$

Now let's calculate 16 \mod 5$16 \mod 5$:

16 \div 5 = 3 \quad \text{(remainder 1)} $16 \div 5 = 3 \quad \text{(remainder 1)}$

So:

2^4 \equiv 1 \mod 5 $2^4 \equiv 1 \mod 5$

Exercise 2

Verify Fermat's Theorem for a = 3$a = 3$ and p = 7$p = 7$.

Solution:

Let's calculate 3^{7-1} \mod 7$3^{7-1} \mod 7$:

3^6 = 729 $3^6 = 729$

Now let's calculate 729 \mod 7$729 \mod 7$:

729 \div 7 = 104 \quad \text{(remainder 1)} $729 \div 7 = 104 \quad \text{(remainder 1)}$

So:

3^6 \equiv 1 \mod 7 $3^6 \equiv 1 \mod 7$

Exercise 3

Prove that if p = 11$p = 11$ and a = 4$a = 4$, then 4^{10} \equiv 1 \mod 11$4^{10} \equiv 1 \mod 11$.

Solution:

Let's calculate 4^{10} \mod 11$4^{10} \mod 11$:

4^{10} = 1048576 $4^{10} = 1048576$

Now let's calculate 1048576 \mod 11$1048576 \mod 11$:

1048576 \div 11 = 95324 \quad \text{(remainder 2)} $1048576 \div 11 = 95324 \quad \text{(remainder 2)}$

So:

4^{10} \equiv 2 \mod 11 $4^{10} \equiv 2 \mod 11$

In this case, Fermat's Theorem is not satisfied, since 4$4$ is divisible by 11$11$.