Lo strano caso dell'MCD

[Enigmatico]

Che significa $gcd(A)$?

[karlosson_sul_tetto]

gcd=greatest common divisor= Massimo Comun Divisore

(e quindi non ha senso dire $gcd(A)$, ma si deve dire $gcd(A,B,\ldots)$ )

[Talete]

Perché il problema è stato eliminato? Che problema era?

(scommetto che concerneva il massimo comun divisore....)

[LucaMac]

Era dimostrare che $gcd(x^a-1,x^b-1)=x^{gcd(a,b)} - 1 $ che è anche un bell'esercizio (e utile) da fare secondo me

[Talete]

Boh, sembra interessante... ci provo...

Testo nascosto:

Suppongo $x\neq1$, $a\neq0$, $b\neq0$.

Wlog $gcd(a,b)=1$ perché altrimenti, detto $d:=gcd(a,b)$, chiamo $y:=x^d$ e mi basta dimostrarlo per $gcd(a,b)=1$.

Quindi la tesi è che $\frac{x^a-1}{x-1}$ e $\frac{x^b-1}{x-1}$ siano coprimi. Sia per assurdo $d$ un loro divisore comune diverso da $1$. Allora, ricordando la nota identità $\frac{x^n-1}{x-1}=\sum_{i=0}^{n-1} x^i$ si deve avere:

\[\sum_{i=0}^{a-1} x^i\equiv \sum_{i=0}^{b-1} x^i \pmod{d}.\]

Ora, sia wlog $a\ge b$. Allora posso riscriverla come:

\[\sum_{i=b}^{a-1} x^i\equiv 0\pmod{d}.\]

Ma quindi posso dividere per $x^b$ perché coprimo con $x^b-1$ quindi anche con $d$. Ottengo:

\[\sum_{i=0}^{a-b-1} x^i\equiv 0\pmod{d}.\]

Ma quindi $d$ divide anche $\frac{x^{a-b}-1}{x-1}$, da cui si fa per induzione (credo).

È giusta?

[Whov]

Per "induzione" non credo sia il termine più corretto, Talete, ma trovo molto azzeccata l'idea delle congruenze: io mi ero incartato con l'algoritmo di Eulero! . Provo a formalizzare l'ultima parte del procedimento.
Sono date due somme $ \displaystyle\sum_{i=0}^{n}x^i $ e $ \displaystyle\sum_{j=0}^{m}x^j $ con, senza perdita di generalità, $ n > m > 0 $ (ps hai usato due volte la lettera d per due diversi MCD ). Ora con il tuo algoritmo si passa da MCD($ \displaystyle\sum_{i=0}^{n}x^i; \displaystyle\sum_{j=0}^{m}x^j $) all'equivalente MCD($ \displaystyle\sum_{i=0}^{n-m-1}x^i; \displaystyle\sum_{j=0}^{m}x^j $). Per cui si ha che il termine di grado massimo (che prima era n) diminuisce ogni volta e diventa n-m-1 o m. Da ciò consegue che l'algoritmo ha fine. Certamente $ m > 0 $ e $ n-m-1 \ge 0 $ , poiché $ n \ge m+1 $ cioé $ n > m $ come da Hp. Ma allora finché $ n-m-1>0 $ l'algoritmo si può reiterare (non all'infinito!) finché una somma non diventa $ x^0=1 $ (cioé n-m-1=0) e l'algoritmo ha fine. Da questo la tesi.
Tuttavia non è chiaro perché n>m (e mai n=m) per ogni iterazione: dimostriamolo!
Inizialmente si ha a-1=n e b-1=m. m'=m e n'=n-m-1. Allora b'=m'+1=m+1=b e a'=n'+1=(a-1-(b-1)-1)+1=a-b. Inizialmente però MCD(a, b)=1 da cui MCD(a-b, b)=1. Dunque a' e b' restano coprimi sempre (in pratica io parto con x^a, x^b, passo alla serie tronca, trasformo, ottengo due nuove serie che vengono da valori degli esponenti coprimi). Per induzione, essendo per Hp a, b iniziali coprimi, allora sarà sempre possibile procedere con l'algoritmo senza mai incappare in n=m.
Che ne dite?

[Talete]

Mi piace hai formalizzato bene la mia idea "buttata lì"

Comunque, mi è venuta in mente un'altra soluzione:

Se $d$ è un numero tale che $x^a-1\equiv x^b-1\equiv0\pmod{d}$, allora $d\mid x-1$ (forse sto usando un po' troppo la lettera $d$... vabbè ci sono affezionato ). Dimostriamo questo claim. Chiaramente $d\nmid x$. Allora si ha che $\operatorname{ord}_d(x)\mid a$, e $\operatorname{ord}_d(x)\mid b$, e quindi $\operatorname{ord}_d(x)\mid \gcd(a,b)$. Nell'altro post avevo supposto $\gcd(a,b)=1$, e quindi $\operatorname{ord}_d(x)=1$. Quindi $x\equiv1\pmod{d}$, e $d\mid x-1$. Et voilà

È corretta o sparo scemenze?

[AlexThirty]

Io guardando in internet ho trovato qualcosa di diverso
possiamo dire che un certo $ x^{a}-1 $ divide $ x^{b}-1 $ se $ a $ divide $ b $. Quindi sicuramente $ a^{MCD (m,n)}-1 $ divide sia $ a^{m}-1 $ che $ a^{n}-1 $. Ora consideriamo un qualsiasi numero $ r $ che divida sia $ a^{m}-1 $ che $ a^{n}-1 $. Allora $ a^{m} $ E $ a^{n} $ Sono congrui a 1 modulo r.
Siccome però $ MCD (m,n) $ È della forma $ sm+tn $ Allora si ha che
$ a^{sm+tn}=(a^{m})^{s}(a^{n})^{t} $ E questo numero è congruo a 1 modulo r. Quindi qualsiasi numero divida entrambi divide anche l'MCD.

come vi sembra?

[Rho33]

Se volete il caso generale:
Proviamo che $ \displaystyle MCD (x^a-y^a, x^b-y^b) = x^{MCD (a,b)} - y^{ MCD (a,b) } $ per ogni coppia $ (x,y) $ di interi positivi coprimi.

Sia $ \displaystyle MCD (x^a-y^a, x^b-y^b) = k $ , allora possiamo dire che $ x^{MCD(a,b)} -y^{MCD(a,b)} | k $

ora per Bezout ci saranno $ \displaystyle c,d $ tali che $ k= ac +bd $

Allora $ \displaystyle x^{MCD(a,b)} -y^{MCD(a,b)} \equiv x^{ac+bd} - y^{MCD(a, b)} \equiv (x^a)^{c} (x^b)^{d} - y^{MCD(a,b)} \equiv (y^a)^{c} (y^b)^{d} - y^{MCD(a,b)} \equiv y^{ac+bd} - y^{MCD(a,b)} \equiv 0 (mod \ k) $

Quindi $ \displaystyle k | x^{MCD(a,b)} -y^{MCD(a,b)} $ e necessariamente $ \displaystyle k= x^{MCD(a,b)} -y^{MCD(a,b)} $

Secondo voi va bene? Anche scritta in un esercizio per il senior?

[Rho33]

La cosa bella da vedere è che dopo aver perso un bel pò a provarlo, scopro casualmente questo

http://www.artofproblemsolving.com/comm ... 15p2110064

[alegh]

Nel caso $ MCD(2^{c}-1,2^{d}-1) $ io ho pensato di fare così: dimostro che l'algoritmo euclideo può essere applicato anche agli esponenti e dopo alcuni passaggi trovo:$ MCD(2^{c}-1,2^{d}-1)=MCD(2^{c-d}-1,2^{d}-1) $. A questo punto posso affermare che quindi dato $ MCD(c,d) $, io avrò $ MCD(2^{c}-1,2^{d}-1)=2^{(c,d)}-1 $.
Come vi sembra?