Classi di resto
Ciao, ho una domanda credo semplice...
su degli appunti trovo scritto che:
$([9]^(40))^5=[1]^5$ in $ZZ_(100)$ perche?
io ho fatto $9^40/(100)$ e mi viene resto 0, mentre $1/(100)=0$ resto 1.
Come devo fare?dove sbaglio?
grazie!ciao!
su degli appunti trovo scritto che:
$([9]^(40))^5=[1]^5$ in $ZZ_(100)$ perche?
io ho fatto $9^40/(100)$ e mi viene resto 0, mentre $1/(100)=0$ resto 1.
Come devo fare?dove sbaglio?
grazie!ciao!
Risposte
basta notare che $Phi(100)=40$ e usare il teorema di Eulero
grazie Luca, pero nn so applicare il teorema di Eulero, potresti spiegarmelo per favore?
si ha che
$a^(phi(n))-=1(modn)$, con $a,n$ coprimi.
In questo caso hai $a=9$, $n=100$, $phi(100)=40$:
$9^40-=1(mod100)$.
Ok?
$a^(phi(n))-=1(modn)$, con $a,n$ coprimi.
In questo caso hai $a=9$, $n=100$, $phi(100)=40$:
$9^40-=1(mod100)$.
Ok?
da dove vedo l uguaglianza delle classi?dalle congruenza?
pero dividendo per 100 $9^40$ e 1 nn dovrei avere lo stesso resto?
pero dividendo per 100 $9^40$ e 1 nn dovrei avere lo stesso resto?
"richard84":
da dove vedo l uguaglianza delle classi?dalle congruenza?
praticamente sì
pero dividendo per 100 $9^40$ e 1 nn dovrei avere lo stesso resto?
sì, e così è
grazie mille...come faccio a vedere che le divisioni mi danno lo stesso resto?
scusami luca ma nn capisco molto l inglese....c e solo quel modo per vedere che la divsione da lostesso resto?
se vuoi farlo a mano senza spendere una vita sì, altrimenti puoi usare una calcolatrice o dare in pasto a matlab o mathematica.
L'algoritmo che ti ho proposto è molto semplice, funziona così: trasformi l'esponente in binario ($40_(10)=101000_2$), quindi devi calcolare $9^(101000_2)(mod100)$. Consideri l'esponente a partire dalla cifra più significativa: parti con il numero 1, se il bit all'esponente è 0 allora elevi al quadrato, altrimenti calcoli il quadrato e moltiplichi per la base (9). Poi riduci modulo 100. Ti porto tutti i conti.
bit6: $1$. Calcolo: $1^2*9-=9$
bit5: $0$. Calcolo: $9^2-=81$
bit4: $1$. Calcolo: $81^2*9-=49$
bit3: $0$. Calcolo: $49^2-=1$
bit2: $0$. Calcolo: $1^2-=1$
bit1: $0$. Calcolo: $1^2-=1$
Quindi $9^40-=1 (mod100)$
L'algoritmo che ti ho proposto è molto semplice, funziona così: trasformi l'esponente in binario ($40_(10)=101000_2$), quindi devi calcolare $9^(101000_2)(mod100)$. Consideri l'esponente a partire dalla cifra più significativa: parti con il numero 1, se il bit all'esponente è 0 allora elevi al quadrato, altrimenti calcoli il quadrato e moltiplichi per la base (9). Poi riduci modulo 100. Ti porto tutti i conti.
bit6: $1$. Calcolo: $1^2*9-=9$
bit5: $0$. Calcolo: $9^2-=81$
bit4: $1$. Calcolo: $81^2*9-=49$
bit3: $0$. Calcolo: $49^2-=1$
bit2: $0$. Calcolo: $1^2-=1$
bit1: $0$. Calcolo: $1^2-=1$
Quindi $9^40-=1 (mod100)$
"luca.barletta":
bit4: $1$. Calcolo: $81^2*9-=49$
questo passo nn l ho capito e poi ancora, quando arrivo al fondo come leggo tot resto 1?
"richard84":
[quote="luca.barletta"]bit4: $1$. Calcolo: $81^2*9-=49$
questo passo nn l ho capito e poi ancora, quando arrivo al fondo come leggo tot resto 1?[/quote]
poichè il bit dell'esponente che stai considerando è 1 devi quadrare il risultato parziale e moltiplicare per la base.
Il resto finale è l'ultimo risultato che trovi
Scusami Luca nn ho ancora capito quel passaggio...$81^2*9=49$ come lo ottieni?
bit1: $0$. Calcolo: $1^2-=1$ e il risultato?
bit1: $0$. Calcolo: $1^2-=1$ e il risultato?
"richard84":
Scusami Luca nn ho ancora capito quel passaggio...$81^2*9=49$ come lo ottieni?
bit1: $0$. Calcolo: $1^2-=1$ e il risultato?
$81^2*9-=6561*9-=61*9-=549-=49 (mod100)$
il risultato è l'1 finale che ottieni dall'ultimo calcolo.
"luca.barletta":[/quote]
[quote="richard84"]quote]
$81^2*9-=6561*9-=61*9-=549-=49 (mod100)$
Mi sento stupido $6561*9-=61*9-=549-=49(mod100)$ cioe la classe $6561*9$ e uguale alla classe $61*9$? se si come si fa?
ho ridotto 6561 modulo 100: $6561-=61 (mod100)$
ok ho capito grazie!ma esiste solo questo modo?perche sul mio quad sembra scontato che $[9]^(40)-=[1]$ in $ZZ_(100$.
Posso chiederti ancora di aiutarmi sul post "Teorema di Eulero" sul forum universita?
grazie ancora
Posso chiederti ancora di aiutarmi sul post "Teorema di Eulero" sul forum universita?
grazie ancora
è scontato per il th di Euler, quello che ti ho proposto io è una verifica, ma naturalmente se l'esponente è maggiore di $phi(n)$ prima si riduce l'esponente modulo $phi(n)$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo