Sì è corretto ! il resto è 1 !

(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.

[…] Ho un problema con un esercizio preso sugli appunti del prof. Niesi.

L'esercizio è il seguente: calcolare 11⁵⁷ (mod 23).

Nella soluzione dell’ esercizio c'è una cosa che non capisco:

Poichè 57 = 22 · 2 + 13 , per il teorema di Fermat si ha 11⁵⁷= (11²²) ²⋅ 11¹³ = 11¹³ (mod 23)

e, calcolando modulo 23, si ha : 11² = 121 = 6 , 11³ = 6 ·11 = 66 = −3 , 11⁶ = 9 ,11¹²= 81 = 12 , 11¹³= 11 · 12 = 132 = 17 .

Non capisco perchè 11³ abbia come risultato -3 mentre io avrei detto fosse 20.

1.DOMANDA SULLA CONGRUENZA EIL TEOREMA DI FERMAT :11⁵⁷(MOD 23)

RISPOSTA Sì è esatto dire che 11³ = 20 ( usando le classi ), poiché 11³ = 23⋅2 +20

(e passando alle classi modulo 23 ), essendo la classe di 23 uguale alla classe nulla , si ottiene appunto (con le classi !) : 11³ = 20.

Ma è altrettanto esatto dire che 11³ = -3 ( usando le classi ) . E questo perchè 20 e -3 sono equivalenti modulo 23, infatti 20-(-3) = 23 che è un multiplo di 23 !

Così ad esempio la classe di 45 modulo 23 è 22, ma è anche -1 poichè 45 = 23 ⋅ 2 -1 .

Spesso può essere utile lavorare con i rappresentanti negativi, se sono molto più piccoli in valore assoluto dei rappresentanti positivi.

Basta tener conto sempre della relazione di equivalenza che in Z23 dice : due interi sono equivalenti modulo 23 <=> la loro differenza è un multiplo di 23.

(2)

[…] un esercizio sul teorema di fermat propone la divisione tra 5^66 e 23.

il problema è che scrivendolo con fermat ottengo in Z23 che 5^22 = 1.

quindi svolgendo ottengo: 5^66 = (5^22)^3 = 1.

Io credo che il resto debba venire 2.. come si dovrebbe procedere?

[…] volevo sapere se è questo il metodo esatto per la risoluzione di esercizi del tipo

"Utilizzando teorema fermat calcolare resto della divisione tra 7^83 e 17"

soluzione:

7^83=17*q+r 0<=r<=16

83=16*5+3 7^83=(7^16)^5 + 7^3 = 7^3 = -10^3(modulo 17) è corretto ?

RISPOSTA RASSICURANTE

3.DOMANDA SULLA CONGRUENZA EIL TEOREMA DI FERMAT : IL RESTO DELLA DIVISIONE TRA 7⁸³ E 17

RISPOSTA Fin dove ha scritto è corretto, ad eccezione di questa ′svista′ :

• 83=16*5+3 => 7^83=(7^16)^5 + 7^3

Il segno esatto non è il + ma il segno di prodotto per la proprietà delle potenze:

x^a+b = x^a⋅ x^b

E il suo numero finale è 7^3 ( o se preferisce -10^3 ) modulo 17, ma non è il resto cercato ! Deve ancora ridurre modulo 17 il numero in questione 7^3 , finchè trova appunto un numero compreso tra 0 e 16 (estremi inclusi), ok ?

Sì è corretto ! il resto è 1 !

2.DOMANDA SULLA CONGRUENZA EIL TEOREMA DI FERMAT : IL RESTO DELLA DIVISIONE TRA 5⁶⁶ E 23

(3)

[…]avrei una domanda circa l'ultimo esame, nell’ esercizio dove bisognava calcolare il resto della divisione tra 4^68 e 23 utilizzando il teorema piccolo di Fermat:

4^22 = 1 (Mod 23) quindi 4^68 = (4^22)^3 + 4^2 => (1)^3 + 4^2 MA 4^2 è uguale a 16 ke è minore di 23 allora come faccio a calcolare il resto?

[…] in un equazione del tipo classe di 14 * x =classe di 5 in Z103 dove M.C.D tra (14,103)=1 non riesco a procedere :(

4.DOMANDA SULLA CONGRUENZA EIL TEOREMA DI FERMAT : IL RESTO DELLA DIVISIONE TRA 4⁶⁸ E 23

RISPOSTA Attenzione ! 4^68 = (4^22)^3 + 4^2 non è esatto, non si tratta di una somma ma bensì di un prodotto !

Allora calcolando tutto modulo 23:

4^68

= (4^22)^3 * (4^2) ( per il piccolo terorema di Fermat)

= (1)^3 * (4^2)

= 4^2

= 16

Ora poichè abbiamo trovato che in Z23 4^68=16

con 16, intero minore di 23 e maggiore o uguale a zero, NON dobbiamo procedere ancora a ridurre modulo 23 ! Siamo arrivati ! il resto della divisione di 4^22 per 23 è esattamente 16 !!

Era ... più facile del previsto.

5.UN ESERCIZIO SULLE EQUAZIONI LINEARI IN ZN

RISPOSTA A pag 103 (Es. 6.100) delle dispense di Niesi c'è la soluzione, l'ha vista vero? Mi dica quali sono i passaggi che non capisce.

Ha guardato l'esercizio 3b) della mia esercitazione N. 9 http://www.dima.unige.it/~baratter/md08-09/2008.11.25.pdf dove si chiede di trovare l'inverso di un elemento in un Zn ? Se capisce come si fa a trovare l'inverso allora l'esercizio è quasi fatto.

(4)

[…] perchè la classe di -15 è uguale alla classe di 24 in Z39 ? 6.CLASSI UGUALI IN ZN

RISPOSTA La risposta è:

perchè -15 è congruente a 24. ( due classi di equivalenza

coincidono quando i loro rappresentanti sono equivalenti, in questo caso la rel. di equiv. è la congruenza).

Infatti secondo la def. di congruenza di Gauss:

Due numeri interi a, b ∈ Z si dicono congruenti modulo n ( n>1), in simboli a≡b (mod n) se n divide la differenza a-b,ossia se vale a-b=kn con k∈Z.

Se lei chiama a=-15 , b=24, n=39 ha che n divide b-a, ossia 39 divide 24-(-15)=24+15=39.

Lei dirà che questo torna, ma è il risultato di quale ragionamento?

in pratica come faccio a trovare 24 ?

Il modo mentale più spontaneo quando si ha a che fare con numeri negativi o con numeri maggiori di 39 (n) è questo:

aggiungere al numero in questione 39 o i multipli di 39 che sono necessari, per portarsi ad avere come rappresentante della classe un numero maggiore o uguale a zero e minore strettamente di 39.

Quindi lavorando con le classi in Z39 ( ometto qua il simbolo di classe, la barra sopra i numeri) si ha :

-15 = -15 +39 = 24

Quando invece non si fa il calcolo a mente perché il numero in questione è ′grande′, un modo per arrivare al risultato è quello che ho indicato nell’esercizio 2.a) dell’esercitazione n. 8 ( pag.8)

http://www.dima.unige.it/~baratter/md08-09/2008.11.18.pdf

(5)

[…] Ho svolto questi esercizi ma non ho il risultato, vorrei sapere se sono giusti e se vanno bene come svolgimento per l’ esame.

¾ Calcolare 35 ⁵⁷ mod (23) Svolgimento :

35

⁵⁷

mod (23) p-1 = 22 57/22 = 2 resto = 13

(35

²²

)

²

⋅ 35

¹³

=1 ⋅ 35

¹³

35

²

= 1225 ≡ 6

35

⁴

= 36 ≡ 13 35

⁸

= 169 ≡ 8

35

¹²

= 12 ⋅ 8 = 104 ≡ 12

35

¹³

= 35

¹²

⋅ 35 = 12 ⋅ 35 = 420 ≡ 6

¾ Calcolare 11⁶⁸ mod 13 !

Svolgimento :

(11⁶⁰) (11⁸) = (11¹²)⁵ ⋅ 11⁸ 11² = 121 ≡ 4

11⁴= 16 ≡ 6 11⁸= 36 ≡ 10

11¹² = 10 ⋅ 6 = 60 ≡ 8

11¹³ = 11¹²⋅ 11 = 8 ⋅ 11 = 88 ≡19

7.CALCOLO DI POTENZE IN ZN:35 ⁵⁷ mod (23) , 11⁶⁸ mod 13

13 al posto di 12 : 35

¹²

= 35

⁴

⋅ 35

⁸

La tecnica nei vari passaggi è corretta, ma attenta alla partenza, poiché si deve calcolare 35⁵⁷ modulo 23, è molto meglio ridurre la base 35 modulo 23 e così la domanda diventa

′calcolare 12⁵⁷ modulo 23’ , che offre il vantaggio di lavorare con numeri un po’ più piccoli.

Le ho segnato in rosso un errore-svista.

RISPOSTA

3 e non 6 , siamo modulo 13 !

RISPOSTA La tecnica è corretta, ma sarebbe stato meglio farlo come l’esercizio precedente, e utilizzare il piccolo teorema di Fermat, che semplifica subito il calcolo, essendo 11¹² ≡ 1 in Z13.

Le ho segnato in rosso un errore.

(6)

[…] è 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?

8.DOMANDA SUL TEOREMA DI EULERO

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

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

http://www.dima.unige.it/~baratter/md08-09/2008.11.18.pdf

Il primo passaggio dell’algoritmo euclideo, che ho evidenziato in rosso, è inutile, si inizia dividendo il numero maggiore per il minore.

(7)

[…]nell'esercizio in cui Lei ha usato il Teorema di Eulero (esercizio 3.b) dell’esercitazione n.9 : http://www.dima.unige.it/~baratter/md08-09/2008.11.18.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?

RISPOSTA

RASSICURANTE

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

9. TEOREMA DIEULERO ED ESPONENTI‘GRANDI’