Diofantee lineari

[ElPaso98]

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]?

[Gerald Lambeau]

EDIT: errore mio, quello che chiedi tu è l'opposto

[ElPaso98]

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
La mia soluzione è riferita alla 'seconda versione' della domanda ,cioè con (a,b)=1

[Gerald Lambeau]

Io avevo letto $MCD(a, b)=1$, mentre in realtà c'è scritto $MCD(x, y)=1$, che è ben diverso.

[ElPaso98]

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

[Gerald Lambeau]

Non erano conclusioni mie, con quelle ipotesi è un teorema vero e proprio (che si può anche usare in gara!): http://artofproblemsolving.com/wiki/ind ... et_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!

[ElPaso98]

Il teorema che hai citato tu è più potente, buono a sapersi! Grazie!

[Gerald Lambeau]

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$.

[ElPaso98]

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?

[Gerald Lambeau]

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