GCD
GCD
Dimostrare che $ GCD\left(a^m-1,a^n-1\right)=a^{GCD(m,n)}-1 $ per tutti gli interi positivi $ a>1 $, $ m $ e $ n $.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
Dimostriamo che se un numero b divide contemporaneamente $ \displaystyle~a^m-1 $ e $ \displaystyle~a^n-1 $, allora b divide $ \displaystyle~a^{GCD(m,n)}-1 $, da cui segue che $ \displaystyle~a^{GCD(m,n)}-1 $ è effettivamente il GCD, per la nota proprietà $ \displaystyle~s\mid t\Rightarrow a^s-1\mid a^t-1 $ (prima con $ \displaystyle~s=GCD(m,n) $ e $ \displaystyle~t=m $, poi con $ \displaystyle~s=GCD(m,n) $ e $ \displaystyle~t=n $)
Poniamo senza perdita di generalità $ \displaystyle~m\ge n $
La nuova ipotesi diventa
$ \displaystyle~\begin{cases}a^m\equiv1\pmod b\\a^n\equiv1\pmod b\end{cases} $
a è quindi primo con b
Possiamo porre $ \displaystyle~r_0=m $ e $ \displaystyle~r_1=n $. Per $ \displaystyle~m\ge n $ abbiamo che esiste un $ \displaystyle~q_1 $ positivo tale che $ \displaystyle~q_1n\le m\wedge (q_1+1)n>m $ (in pratica esiste un $ \displaystyle~q_1 $ tale che $ \displaystyle~q_1n $ è il massimo multiplo di n minore o uguale a m).
Quindi $ \displaystyle~q_1=\left\lfloor\frac{m}{n}\right\rfloor $, cioè $ \displaystyle~q_1=\left\lfloor\frac{r_0}{r_1}\right\rfloor $
Dato che $ \displaystyle~a^n\equiv1\pmod b $ abbiamo che $ \displaystyle~a^{q_1n}\equiv1\pmod b $, cioè $ \displaystyle~a^{q_1r_1}\equiv1\pmod b $
Confrontando questa con $ \displaystyle~a^m\equiv1\pmod b $ otteniamo
$ \displaystyle~a^{r_0}\equiv a^{q_1r_1}\pmod b $
Dato che a è primo con b possiamo dividere per $ \displaystyle~a^{q_1r_1} $ (minore di $ \displaystyle~a^m $):
$ \displaystyle~a^{r_0-q_1r_1}\equiv 1\pmod b $
Possiamo porre $ \displaystyle~r_2=r_0-q_1r_1 $ e imporre il nuovo sistema
$ \displaystyle~\begin{cases}a^{r_1}\equiv1\pmod b\\a^{r_2}\equiv1\pmod b\end{cases} $
Si può proseguire il procedimento ottenendo ogni volta un sistema del tipo
$ \displaystyle~\begin{cases}a^{r_i}\equiv1\pmod b\\a^{r_{i+1}}\equiv1\pmod b\end{cases} $ con $ \displaystyle~\begin{cases}q_i=\left\lfloor\frac{r_{i-1}}{r_i}\right\rfloor\\r_{i+1}=r_{i-1}-q_ir_1\end{cases} $
fino a quando la seconda equazione del sistema non sarà l'identità $ \displaystyle~1\equiv1\pmod b $
La doppia sequenza $ \displaystyle~{q_k},{r_k} $ è quella dell'algoritmo di Euclide, che garantisce che $ \displaystyle~\exists K:r_K=0 $, che dà $ \displaystyle~1\equiv1\pmod b $, e che $ \displaystyle~r_{K-1}=GCD(r_0,r_1)=GCD(m,n) $. Dato che deve verificarsi anche $ \displaystyle~a^{r_{K-1}}\equiv1\pmod b $, otteniamo $ \displaystyle~b\mid a^{GCD(m,n)}-1 $.
Quindi $ \displaystyle~b\mid a^m-1\wedge b\mid a^n-1\Rightarrow b\mid a^{GCD(m,n)}-1 $, che è la tesi.
Poniamo senza perdita di generalità $ \displaystyle~m\ge n $
La nuova ipotesi diventa
$ \displaystyle~\begin{cases}a^m\equiv1\pmod b\\a^n\equiv1\pmod b\end{cases} $
a è quindi primo con b
Possiamo porre $ \displaystyle~r_0=m $ e $ \displaystyle~r_1=n $. Per $ \displaystyle~m\ge n $ abbiamo che esiste un $ \displaystyle~q_1 $ positivo tale che $ \displaystyle~q_1n\le m\wedge (q_1+1)n>m $ (in pratica esiste un $ \displaystyle~q_1 $ tale che $ \displaystyle~q_1n $ è il massimo multiplo di n minore o uguale a m).
Quindi $ \displaystyle~q_1=\left\lfloor\frac{m}{n}\right\rfloor $, cioè $ \displaystyle~q_1=\left\lfloor\frac{r_0}{r_1}\right\rfloor $
Dato che $ \displaystyle~a^n\equiv1\pmod b $ abbiamo che $ \displaystyle~a^{q_1n}\equiv1\pmod b $, cioè $ \displaystyle~a^{q_1r_1}\equiv1\pmod b $
Confrontando questa con $ \displaystyle~a^m\equiv1\pmod b $ otteniamo
$ \displaystyle~a^{r_0}\equiv a^{q_1r_1}\pmod b $
Dato che a è primo con b possiamo dividere per $ \displaystyle~a^{q_1r_1} $ (minore di $ \displaystyle~a^m $):
$ \displaystyle~a^{r_0-q_1r_1}\equiv 1\pmod b $
Possiamo porre $ \displaystyle~r_2=r_0-q_1r_1 $ e imporre il nuovo sistema
$ \displaystyle~\begin{cases}a^{r_1}\equiv1\pmod b\\a^{r_2}\equiv1\pmod b\end{cases} $
Si può proseguire il procedimento ottenendo ogni volta un sistema del tipo
$ \displaystyle~\begin{cases}a^{r_i}\equiv1\pmod b\\a^{r_{i+1}}\equiv1\pmod b\end{cases} $ con $ \displaystyle~\begin{cases}q_i=\left\lfloor\frac{r_{i-1}}{r_i}\right\rfloor\\r_{i+1}=r_{i-1}-q_ir_1\end{cases} $
fino a quando la seconda equazione del sistema non sarà l'identità $ \displaystyle~1\equiv1\pmod b $
La doppia sequenza $ \displaystyle~{q_k},{r_k} $ è quella dell'algoritmo di Euclide, che garantisce che $ \displaystyle~\exists K:r_K=0 $, che dà $ \displaystyle~1\equiv1\pmod b $, e che $ \displaystyle~r_{K-1}=GCD(r_0,r_1)=GCD(m,n) $. Dato che deve verificarsi anche $ \displaystyle~a^{r_{K-1}}\equiv1\pmod b $, otteniamo $ \displaystyle~b\mid a^{GCD(m,n)}-1 $.
Quindi $ \displaystyle~b\mid a^m-1\wedge b\mid a^n-1\Rightarrow b\mid a^{GCD(m,n)}-1 $, che è la tesi.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)