Diofantee lineari

Tutto ciò che dovete sapere per arrivare preparati alle competizioni matematiche.

Diofantee lineari

Messaggioda ElPaso98 » 14/11/2016, 23:48

Data un'equazione del tipo [tex]ax+by=c[/tex] con [tex]MCD(x,y)=1[/tex], [tex]c>1[/tex] e [tex]a,b>0[/tex] è possibile stabilire qual è il minimo [tex]c_m[/tex] per cui si ha che l'equazione ha almeno una coppia di soluzioni [tex](x,y)[/tex] positive per [tex]c \ge c_m[/tex]? O quanto meno stringere [tex]c[/tex] all'interno di due valori dipendenti da [tex]a,b[/tex], evidentemente ponendolo maggiore di [tex]a+b[/tex] date le ipotesi, per stringere il cerchio?

Edit: se le ipotesi fossero [tex]MCD(a,b)=1[/tex], [tex]c>1[/tex], [tex]a,b>0[/tex]?
Ultima modifica di ElPaso98 il 16/11/2016, 17:30, modificato 1 volta in totale.
ElPaso98
 
Messaggi: 99
Iscritto il: 26/02/2016, 19:38

Re: Diofantee lineari

Messaggioda Gerald Lambeau » 15/11/2016, 15:56

EDIT: errore mio, quello che chiedi tu è l'opposto
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: Diofantee lineari

Messaggioda ElPaso98 » 16/11/2016, 6:46

Non ho letto il tuo messaggio prima dell'edit quindi non so a cosa eri arrivato, comunque ieri ci ho ragionato e credo si possa dire che se [tex]c >ab[/tex] allora lo si può sempre esprimere con [tex]x,y>0[/tex]. In questo caso si avrebbe che [tex]c_m=ab[/tex], prima di postare la mia dimostrazione vorrei sentire un po' gli altri per capire se si ottiene lo stesso risultato.
EDIT:avevo scritto erroneamente [tex]ab+<c_m \le ab[/tex]
E poi fatto un errroe di battitura nell'edit :lol:
La mia soluzione è riferita alla 'seconda versione' della domanda ,cioè con (a,b)=1
Ultima modifica di ElPaso98 il 16/11/2016, 17:31, modificato 1 volta in totale.
ElPaso98
 
Messaggi: 99
Iscritto il: 26/02/2016, 19:38

Re: Diofantee lineari

Messaggioda Gerald Lambeau » 16/11/2016, 17:19

Io avevo letto $MCD(a, b)=1$, mentre in realtà c'è scritto $MCD(x, y)=1$, che è ben diverso.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: Diofantee lineari

Messaggioda ElPaso98 » 16/11/2016, 17:28

Oddio scusa :? Ho clamorosamente sbagliato le ipotesi iniziali! In effetti intendevo dire proprio MCD (a,b)=1, sarà stata l'ora tarda, mi dispiace averti fatto perdere del tempo, in ogni caso anche quello che ho scritto per sbaglio sembra risultare un caso interessante, magari ci lavorerò su, se hai voglia scrivi quello che avevi sviluppato
ElPaso98
 
Messaggi: 99
Iscritto il: 26/02/2016, 19:38

Re: Diofantee lineari

Messaggioda Gerald Lambeau » 16/11/2016, 18:12

Non erano conclusioni mie, con quelle ipotesi è un teorema vero e proprio (che si può anche usare in gara!): http://artofproblemsolving.com/wiki/index.php?title=Chicken_McNugget_Theorem.
Il problema è che per usare il teorema $x$ e $y$ sono non negativi, mentre tu li chiedi strettamente positivi, ed effettivamente questo potrebbe far alzare il limite; a occhio direi che $ab$ potrebbe essere un buon candidato per queste ipotesi leggermente diverse!
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: Diofantee lineari

Messaggioda ElPaso98 » 16/11/2016, 20:51

Il teorema che hai citato tu è più potente, buono a sapersi! Grazie!
ElPaso98
 
Messaggi: 99
Iscritto il: 26/02/2016, 19:38

Re: Diofantee lineari

Messaggioda Gerald Lambeau » 16/11/2016, 21:54

Prego!
Comunque no, le ipotesi del teorema sono, anche se leggermente, meno restrittive, ma per quanto riguarda la potenza non cambia molto.
In realtà, penso che da quel teorema si possa raggiungere qualche conclusione, se non l'intera soluzione, per quanto riguarda il tuo problema. Ad esempio è banale, partendo dal teorema, dire che si può scrivere qualunque numero da $ab+1$ in su con $x$ e $y$ positivi. Inoltre, se vogliamo $ax+by=ab$, essendo $a$ e $b$ coprimi, abbiamo che $a \mid y$ e $b \mid x$, quindi ci riconduciamo a $abx'+aby'=ab \Rightarrow x'+y'=1$ con $x', y' \ge 1$, assurdo! Dunque si ha proprio che $c_m=ab+1$.
Certo, abbiamo usato il Chicken McNugget Theorem per risolvere il tuo problema, ma la potenza del risultato ottenuto non è da meno!

È interessante adesso provare invece con $MCD(x, y)=1$.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: Diofantee lineari

Messaggioda ElPaso98 » 17/11/2016, 16:44

Sono d'accordo, però prima vorrei proporre la mia dimostrazione riguardo il caso con [tex](a,b)=1[/tex], sulla quale ho un dubbio

Data l'equzione [tex]ax+by=c[/tex] voglio che questa abbia soluzioni strettamente positive con [tex]c>0[/tex].
Siano [tex]x_0, y_0[/tex] le soluzioni di [tex]ax_0+by_0=1[/tex], allora sappiamo tutti che [tex]x=cx_0+kb[/tex], mentre [tex]y=cy_0-ka[/tex]. Metto a sistema queste due relazioni e le pongo entrambe maggiori di 0. Otterrò, esplicitando rispetto a [tex]k[/tex], la seguente relazione: [tex]-c\frac{x_0}{b}<k<c\frac{y_0}{a}[/tex]. Ora voglio che il mio [tex]k[/tex], in quell'intervallo becchi almeno un valore intero, quindi mi basta porre [tex]c\frac{y_0}{a}-(-c\frac{x_0}{b})>1[/tex] che con qualche passaggio porta dritto a [tex]c>ab[/tex]. Ho appena dimostrato che se [tex]c>ab[/tex], allora posso esprimere [tex]c[/tex] usando [tex]x,y>0[/tex], tuttavia ciò non implica che [tex]ab[/tex] sia il minimo valore che posso esprimere in tal modo, del resto potrebbe anche capitare, ad esempio una cosa del tipo [tex]31,9<k<32,2[/tex], in cui l'intervallo ha una "distanza" di 0,3 che comunque garantirebbe l'esistenza di un valore intero di [tex]k[/tex] a me congeniale. Quindi (e qui iniziano i miei dubbi) ho concluso così:
supponiamo [tex]c=ab[/tex], allora necessariamente alcune coppie di soluzioni sono [tex](b,0);(0,a)[/tex] che evidentemente non soddisfano le mie ipotesi iniziali, così come tutte le altre infinite soluzioni (c'è sempre almeno una variabile negativa al più nulla tra le due), e questo caso ce lo siamo tolti, ora
supponiamo [tex]c<ab[/tex] e consideriamo [tex]ax+by=c[/tex]. Poichè [tex]a,b[/tex] sono fissati, quando [tex]RHS[/tex] diminuisce, lo fanno anche [tex]x,y[/tex] e siccome abbiamo appena dimostrato che se [tex]c=ab[/tex] c'è sempre una soluzione non positiva, lo stesso deve accadere in questo caso.
Che mi dite?
ElPaso98
 
Messaggi: 99
Iscritto il: 26/02/2016, 19:38

Re: Diofantee lineari

Messaggioda Gerald Lambeau » 17/11/2016, 16:55

Non ho capito bene a cosa vuoi arrivare. Se tu vuoi trovare il minimo $c_m$ tale che puoi farlo per ogni $c \ge c_m$, qualunque numero più piccolo, eccettuato $c_m-1$, lo devi ignorare. Il fatto è che alcuni di questi numeri potrebbero essere esprimibili e altri no, e mettersi a guardarli è quasi uno spreco di tempo per quello che chiedi.
Potresti quindi gentilmente dirmi a che ti serve sapere se puoi o no scrivere numeri minori di $ab$? Perché potrei aver perso un pezzo :lol:
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Prossimo

Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite