Lo strano caso dell'MCD

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: Lo strano caso dell'MCD

Messaggio da Enigmatico »

Che significa $gcd(A)$?
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Lo strano caso dell'MCD

Messaggio da 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)$ )
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Lo strano caso dell'MCD

Messaggio da Talete »

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

(scommetto che concerneva il massimo comun divisore....)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
LucaMac
Messaggi: 180
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: Lo strano caso dell'MCD

Messaggio da 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 :D
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Lo strano caso dell'MCD

Messaggio da 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?
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Whov
Messaggi: 23
Iscritto il: 20 ago 2014, 12:40

Re: Lo strano caso dell'MCD

Messaggio da 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! :evil: . 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 :wink: ). 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
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Lo strano caso dell'MCD

Messaggio da Talete »

Mi piace ;) hai formalizzato bene la mia idea "buttata lì" :D

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?
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: Lo strano caso dell'MCD

Messaggio da 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?
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
Rho33
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Re: Lo strano caso dell'MCD

Messaggio da 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
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Re: Lo strano caso dell'MCD

Messaggio da Rho33 »

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

http://www.artofproblemsolving.com/comm ... 15p2110064 :cry:
alegh
Messaggi: 143
Iscritto il: 10 giu 2015, 21:38

Re: Lo strano caso dell'MCD

Messaggio da 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?
Rispondi