Problema sul massimo comun divisore

[minima.distanza]

Innanzitutto buonasera a tutti...

Stavo guardando alcuni video del training olimpico di Massimo Gobbino quando, sentendomi finalmente pronto, mi son deciso ad iniziare a guardare i video delle lezioni di uno stage basic senior (2007).

Stavo guardando il video di Federico Poloni sulle congruenze, quando mi sono accorto che stavo perdendo i pezzi. L'autore, infatti, mettendosi a cercare tutti i possibili massimi comuni divisori tra $ x-y $ e $ x^2 +xy +y^2 $, da un certo punto in poi mi manda in confusione .

Fino a quando riconduce il problema a trovare $ (x-y,3xy) $ capisco tutto ( o almeno mi sembra, applica semplicemente una "proprietà" del massimo comune divisore....), ma poi ? Da dove tira fuori quei casi ? Qualcuno mi spiegherebbe il problema perfavore, mostrandomi magari "al rallentatore" come si "risolvono" tali tipi di problemi, che non lo capisco molto bene da come lo spiega lui...

[Tibor Gallai]

Stavo guardando il video di Federico Poloni sulle congruenze, quando mi sono accorto che stavo perdendo i pezzi.

E' un modo gentile per dire che ti sono cascate le palle?
No no, ok.

Comunque, al solito, un link al video come minimo non guasterebbe.
Nessuno ha voglia di andare a scartabellare tra i vari video, e cercare il punto giusto nel video.

[fph]

Uhm, tranquillo, molto probabile che sia l'autore ad aver fatto casino.
Mi sembra di ricordare che avevo scelto quell'esercizio qualche minuto prima della lezione per illustrare un paio di tecniche (il passaggio x^2+xy+x^2 -> 3xy, e come poi scartare i fattori di quelli che tra poche righe chiamerò a e b), ma poi mi sono reso conto "in diretta" che non veniva immediatamente utilizzando solo quelle. Per far tornare tutto ammodino avrei probabilmente dovuto aggiungere l'ipotesi mcd(x,y)=1. Così l'esercizio si fa, ma è più complicato di quanto avevo pianificato. In ogni caso spero di avere spiegato decentemente le due tecniche, che erano la cosa importante...

Provo a svolgerlo per bene ora --- sperando di non rifare casino...
-nota che se d=mcd(x,y), allora d divide il tuo mcd. Possiamo quindi "semplificare una d" ponendo x=da, y=db, con stavolta mcd(a,b)=1. Il problema diventa quindi trovare d*mcd(a-b,3dab) (occhio alla d che rimane).
-ci serve quindi trovare i fattori "non banali" che può avere g:=mcd(a-b,3dab). Dove vanno cercati? O tra i divisori di a, o tra quelli di b, o tra quelli di 3d.
-se p|a e p|g, allora dev'essere anche p|b (perché?), e questo va contro l'ipotesi che a e b fossero primi tra loro
-restano i primi che dividono 3d. C'è ancora qualcosa che possiamo scartare, o può in generale succedere che tutti i divisori di 3d siano anche fattori di g? Risposta: in generale puoi beccarli tutti -- è possibile trovare esempi in cui quel divisore è un qualunque fattore di 3d (come? possiamo scegliere indipendentemente d, a e b, con l'unico vincolo che a e b siano primi tra loro. Quindi, fissati d e g, basta scegliere b=un primo enorme, e a in modo che b-a=g)
-quindi in generale quell'mcd può essere un qualunque numero w tale che $ d \mid w \mid 3d^2 $.

Ditemi se ora torna...

[Tibor Gallai]

[EDIT: oops, tardi! ]

Ok, con immane sforzo ho trovato video e problema incriminato.

Mi sa che la confusione nasce perché ad un certo punto si incarta e cambia le ipotesi. Credo che ripulendolo e riordinandolo, si possa riassumere così:

risolvere $ $x^3-y^3 = 2^{27}\cdot 3^{15} $, dove $ $x $ e $ $y $ sono interi coprimi.

Quindi $ $(x-y)\left(x^2+xy+y^2\right)=2^{27}\cdot 3^{15} $. I $ $2 $ e i $ $3 $ si possono distribuire a piacimento tra i due fattori a sinistra? A priori no, perché sono legati da $ $x $ e $ $y $. Calcoliamo il MCD dei due fattori.

$ $\left(x-y,\ x^2+xy+y^2\right) = (x-y,\ 3xy)\ |\ (x-y,\ 3)\cdot (x-y,\ x)\cdot (x-y,\ y) = (x-y,\ 3)\ |\ 3 $.

Nel passaggio centrale ho usato il fatto generale che $ $(a,bc)\ |\ (a,b)\cdot (a,c) $, che puoi facilmente dimostrare.

Quindi il MCD dei due fattori deve dividere $ $3 $, ovvero può essere solo $ $1 $ o $ $3 $. Vale a dire che uno dei due fattori non avrà alcun $ $2 $, ed uno dei due fattori avrà al più un $ $3 $.

Per concludere il problema basta allora esaminare tutti i casi, che sono solo 8 (i fattori negativi non vanno considerati perché $ $x-y>0 $).

[minima.distanza]

Perfetto ! Mi sembra di aver capito...

@fph: Bel video !

se p|a e p|g, allora dev'essere anche p|b

Questo succede per lo stesso motivo per cui si possoo "abbassare" i numeri in $ 2x^2 +3y^2 = 1998 $ o mi cnfondo ? è la stessa cosa applicata ai massimi comuni divisori...

@tibor gallai:
Scusa, me ne ero dimenticato del link...
Capisco tutto ( o almeno, credo di capire ) fino all'ultimo passaggio... da dove tiro fuori tutti gli otto casi ? cioè... col tuo metodo io tiro fuori delle condizioni entro cui devono stare quei fattori, ma come faccio poi ? Non capisco... ( io, se non l'avessi visto risolvere in questo modo, avrei impstato il sistema notando che $ x-y = 2*3^{n} $( con n che varia tra 0 e 15) e $ x^2 +xy +y^2 = 3^{15-n} $... Mi rendo conto che ciò è contosissimo, ma avrei fatto male ? sembra di sì... Tibor parla di 8 casi, io me ne devo fare 15 qualcuno mi spiega eprchè non va bene ?)

[Tibor Gallai]

il MCD dei due fattori deve dividere $ $3 $, ovvero può essere solo $ $1 $ o $ $3 $.

i fattori negativi non vanno considerati perché $ $x-y>0 $

$ $\begin{array}{ll} \left\{ \begin{array}{l} x-y=1\\ x^2+xy+y^2=2^{27}\cdot 3^{15} \end{array} \right. & \left\{ \begin{array}{l} x-y=3\\ x^2+xy+y^2=2^{27}\cdot 3^{14} \end{array} \right. \\ \noalign{\bigskip} \left\{ \begin{array}{l} x-y=2^{27}\\ x^2+xy+y^2=3^{15} \end{array} \right. & \left\{ \begin{array}{l} x-y=2^{27}\cdot 3\\ x^2+xy+y^2=3^{14} \end{array} \right. \end{array} $

$ $\begin{array}{ll}\left\{ \begin{array}{l} x-y=3^{14}\\ x^2+xy+y^2=2^{27}\cdot 3 \end{array} \right. & \ \ \,\left\{ \begin{array}{l} x-y=3^{15}\\ x^2+xy+y^2=2^{27} \end{array} \right. \\ \noalign{\bigskip} \left\{ \begin{array}{l} x-y=2^{27}\cdot 3^{14}\\ x^2+xy+y^2=3 \end{array} \right. & \ \ \,\left\{ \begin{array}{l} x-y=2^{27}\cdot 3^{15}\\ x^2+xy+y^2=1 \end{array} \right. \end{array} $

[minima.distanza]

ah non me ne ero accorto....
è fantastico insomma ! il procedimento di prima serve solo per escludere a priori dei casi quindi...

è fantastico !

Bellissimo, grazie mille, posso andare avanti a guardare il video di fph ora...

[Tibor Gallai]

Bellissimo, grazie mille, posso andare avanti a guardare il video di fph ora...

Sì, però prima ripulisci la tastiera da tutta quella bava...

[fph]

@fph: Bel video !

Nah, mica tanto, come hai fatto notare tu mi incasino e non ci si capisce una mazza. Non ti sentire in dovere di complimentarti.

se p|a e p|g, allora dev'essere anche p|b

Questo succede per lo stesso motivo per cui si possoo "abbassare" i numeri in $ 2x^2 +3y^2 = 1998 $ o mi cnfondo ? è la stessa cosa applicata ai massimi comuni divisori...

Sì, la ragione è la stessa. Hai g|a-b, quindi p|a-b per transitività. Poiché hai anche p|a, sottraendo i due membri di destra trovi p|b.

[minima.distanza]

I: Non ti ho fatto notare io che ti incasini ( anche se in parte è vero)
II: il fatto che ti incasini e che un è uno stimolo per non soribre passivamente il video come una macchinetta...

[Tibor Gallai]

Sì, vogliamo poi aggiungere che la scelta del $ $2^{27}\cdot 3^{15} $ è particolarmente infelice, perché si tratta di un cubo? (vedi Ultimo Teorema di Fermat...)

Ma se si tralasciano tutte le cose tipo $ $n=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n} $, la lezione sembra molto ben fatta!

[EvaristeG]

Basta notare la differenza tra $ n $ e $ \phantom{}_n $, che mi sembra evidente ...

[Tibor Gallai]

Ah, quindi basta porre $ $n \neq \phantom{}_n = \phantom{}^{\phantom{}_n} $. Tutto chiaro.

[danielf]

$ (x-y,\ 3xy)\ |\ (x-y,\ 3)\cdot (x-y,\ x)\cdot (x-y,\ y) = (x-y,\ 3)\ |\ 3 $.

.

perchè è uguale al MCD tra (x-y,3) e perchè divide 3?

[Veluca]

Per ipotesi sai che (x,y)=1, quindi puoi dire che (x-y,y)=(x,y)=1, (x-y,x)=(-y,x)=1 e da questo segue che (x-y,3)(x-y,y)(x-y,x)=(x-y,3). Ma se d è il massimo comun divisore tra x-y e 3, per definizione d|x-y e d|3