In questo caso non si puo’ applicare il piccolo Teorema di Fermat poichè 26 non è primo => posso applicare uina sua generalizzazione e cioè il Teorema di Eulero:

1

Avvertenza: Le domande e a volte le risposte, sono tratte dal corpo del messaggio delle mails in cui non si ha a dispo- sizione un editor matematico e quindi presentano una simbologia non corretta, ma comprensibile per questo scopo.

[…]è corretto risolvere l'esercizio 6.111 sulle dispense di Niesi con la formula di Eulero?

Verificare che classe(3)^12 = classe(1) in Z(26) Soluzione (mia):

In questo caso non si puo’ applicare il piccolo Teorema di Fermat poichè 26 non è primo => posso applicare uina sua generalizzazione e cioè il Teorema di Eulero:

Prima verifico che MCD(a, n) = 1 => OK, posso applicare il Teorema di Eulero MCD(3, 26) = 1

3 = 26 * 0 + 3

26 = 3 * 8 + 2 3 = 2 * 1 + 1 2 = 1 * 2

Per applicare il Teorema di Eulero devo prima calcolare:

fi (n) = fi (26) = fi (13 * 2) = fi (13) * fi (2) Siccome:

13 è primo => fi (13) = 12 2 è primo => fi (2) = 1

===> fi (26) = 12

Applico ora il Teorema di Eulero secondo cui:

classe(a)^fi (n) = classe(1) in Z(n) quindi

classe(3)^fi (26) = classe(3)^12 = classe(1) Tesi dimostrata

E' Giusta una risoluzione di questo genere o Vi aspettavate qualcosa di diverso?

1. D

S

T

D

E

R

Sì è corretta ed elegante la sua soluzione con il teorema di Eulero !

Altrimenti si può fare come ho indicato nell'esercizio 2.a) dell'esercitazione N.7, con il calcolo diretto.

http://www.dima.unige.it/~baratter/2007.11.20.pdf

Il primo passaggio dell’algoritmo euclideo, che ho evidenziato

in rosso, è inutile, si inizia dividendo il numero maggiore per il

minore.

2

[…]nell'esercizio in cui Lei ha usato il Teorema di Eulero (esercizio 1.b) dell’esercitazione n.8 : http://www.dima.unige.it/~baratter/2007.11.26.pdf ),

alla fine dopo aver calcolato fi (n) lo utilizza per dividere l'esponente del numero da calcolare e di cui farne l'inverso in Z(45).

Utilizza questo metodo, invece che calcolare la classe di quel numero elevato all'esponente che era 313 (molto maggiore di 45) e poi ridurre la classe calcolata dividendo per 45, perchè appunto l'esponente è molto maggiore rispetto all’n di Z(n) giusto?

R

RASSICURANTE

Sì ! anche perchè 7 ^ 313 la calcolatrice tascabile (la mia) non lo fa :-)

2. T

E

‘

’