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 1157 (mod 23).
Nella soluzione dell’ esercizio c'è una cosa che non capisco:
Poichè 57 = 22 · 2 + 13 , per il teorema di Fermat si ha 1157= (1122) 2 ⋅ 1113 = 1113 (mod 23)
e, calcolando modulo 23, si ha : 112 = 121 = 6 , 113 = 6 ·11 = 66 = −3 , 116 = 9 ,1112= 81 = 12 , 1113= 11 · 12 = 132 = 17 .
Non capisco perchè 113 abbia come risultato -3 mentre io avrei detto fosse 20.
1.DOMANDA SULLA CONGRUENZA EIL TEOREMA DI FERMAT :11
57
(MOD 23)
RISPOSTA Sì è esatto dire che 113 = 20 ( usando le classi ), poiché 113 = 23⋅2 +20
(e passando alle classi modulo 23 ), essendo la classe di 23 uguale alla classe nulla , si ottiene appunto (con le classi !) : 113 = 20.
Ma è altrettanto esatto dire che 113 = -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. DOMANDASULLACONGRUENZAE ILTEOREMADIFERMAT:IL RESTO DELLA DIVISIONE TRA783E17
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:
xa+b = xa⋅ xb
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. DOMANDASULLACONGRUENZAE ILTEOREMADIFERMAT:IL RESTO DELLA DIVISIONE TRA566E23
