$MCD(a^{m}-1,a^{n}-1)$

Messaggioda ficus2002 » 05/04/2006, 15:38

Se a>1 allora $(a^{m}-1,a^{n}-1)=a^{(m,n)}-1$, con $m,n$ interi positivi e $(*,*)$ massimo comun divisore.
ficus2002
Average Member
Average Member
 
Messaggio: 94 di 640
Iscritto il: 09/02/2006, 17:35

Re: $MCD(a^{m}-1,a^{n}-1)$

Messaggioda carlo23 » 05/04/2006, 19:48

ficus2002 ha scritto:Se a>1 allora $(a^{m}-1,a^{n}-1)=a^{(m,n)}-1$, con $m,n$ interi positivi e $(*,*)$ massimo comun divisore.


Abbiamo che se $d|n$ allora $a^d-1|a^n-1$, quindi

$a^(n,m)-1|a^n-1$

$a^(n,m)-1|a^m-1$

ora sia $k>1$ il più grande intero tale che

$k(a^(n,m)-1)|a^n-1$

$k(a^(n,m)-1)|a^m-1$

abbiamo per qualche $s>=1$

$k^s|a^n-1$ quindi $a^n -= 1 mod k^s$

$k^s|a^m-1$ quindi $a^m -= 1 mod k^s$

segue che l'ordine di $a$ modulo $k^s$ divide $(n,m)$ quindi $k^s|a^(n,m)-1$ ma ciò è impossibile per le ipotesi, da cui la tesi.

Ciao Ciao :D perdonate eventuali errori...
Ultima modifica di carlo23 il 06/04/2006, 11:41, modificato 1 volta in totale.
carlo23
Senior Member
Senior Member
 
Messaggio: 952 di 1683
Iscritto il: 01/11/2005, 19:38

Messaggioda ficus2002 » 06/04/2006, 08:08

ciao, grazie della tua soluzione!
Nella seconda parte, è più veloce ragionare così: se $k$ è un divisore comune di $a^m-1$ e $a^n-1$ allora $k|(a^{(m,n)}-1)$, quindi $a^{(m,n)}-1$ è $MCD(a^{m}-1,a^{n}-1)$ .
ficus2002
Average Member
Average Member
 
Messaggio: 95 di 640
Iscritto il: 09/02/2006, 17:35

Messaggioda carlo23 » 06/04/2006, 11:42

ficus2002 ha scritto:ciao, grazie della tua soluzione!
Nella seconda parte, è più veloce ragionare così: se $k$ è un divisore comune di $a^m-1$ e $a^n-1$ allora $k|(a^{(m,n)}-1)$, quindi $a^{(m,n)}-1$ è $MCD(a^{m}-1,a^{n}-1)$ .


Ho fatto solo una piccola correzione, adesso è più chiara anche se come dici è più veloce come hai appena proposto.

Ciao Ciao :D
carlo23
Senior Member
Senior Member
 
Messaggio: 954 di 1683
Iscritto il: 01/11/2005, 19:38


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite