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

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

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 perdonate eventuali errori...

Ultima modifica di carlo23 il 06/04/2006, 11:41, modificato 1 volta in totale.

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)$ .

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