numeri naturali

[fields]

Siano $a$,$b$,$c$ interi positivi tali che $a$ e $b$ sono primi fra loro e $c>=ab$. Provare che $c$ è somma di un multiplo positivo di $a$ e di un multiplo positivo di $b$, ovvero che esistono interi positivi $x$ e $y$ tali che $ax+by=c$.

Attenzione, $x$ e $y$ sono richiesti essere positivi!

[giuseppe87x]

E' noto che l'equazione diofantea $ax+by=c$, per l'algoritmo euclideo, ammette soluzioni intere sse $c$ è multiplo del massimo comune divisore tra $a$ e $b$.
Poichè $MCD(a, b)=1$ allora sicuramente l'equazione ammette soluzioni $x$ e $y$ intere.
Per un corollario del teorema di Frobenius sappiamo che la suddetta equazione ammette soluzioni positive per $c>ab-a-b$. Nel nostro caso, poichè $c>=ab$ si vede facilmente che $x$ e $y$ sono positivi.

[Fioravante Patrone]

a=3
b=5
c=16

mi pare sia un controesempio

o sbaglio?

[Luca.Lussardi]

Se non ho abbagli mi pare che 16=3*2+5*2, no?

[Fioravante Patrone]

quando dico che non so fare i conti è vero!

[fields]

Non conosco il teorema di Frobenius in questione. Comunque l'idea è di dare una prova diretta, nel libro di teoria dei numeri in cui l'esercizio è proposto nemmeno viene citato il teorema di Frobenius! Mi sembra più divertente quindi dare una prova diretta, basata solo sulla parte elementare di teoria dei numeri. Se qualcuno vuole provarci...

[Luca.Lussardi]

Dipenda da cosa intendi per "parte elementare"...

[fields]

Intendo solo la parte "elementarissima": massimo comun divisore, minimo comune multiplo, scomposizione in fattori primi, algoritmo di Euclide.

Ma per curiosità: cosa dice il citato teorema di Frobenius?

[giuseppe87x]

Se $a$ e $b$ sono interi positivi aventi massimo comune divisore $1$ il numero di interi positivi $m$ che non possono essere scritti nella forma $ar+bs=m$ per interi positivi $r$ e $s$ è dato da $((a-1)(b-1))/2$.
Da qui deriva quel corollario.

Va bè leggendolo mi è subito venuto in mente di sfruttare questo risultato; quando ho tempo provo a farlo senza utilizzare questo teorema.

[fields]

Se $a$ e $b$ sono interi positivi aventi massimo comune divisore $1$ il numero di interi positivi $m$ che non possono essere scritti nella forma $ar+bs=m$ per interi positivi $r$ e $s$ è dato da $((a-1)(b-1))/2$.
Da qui deriva quel corollario.

Va bè leggendolo mi è subito venuto in mente di sfruttare questo risultato; quando ho tempo provo a farlo senza utilizzare questo teorema.

Capisco, grazie. Comunque il risultato di Frobenius, preso da solo in quanto enunciato, non mi sembra utile per dimostrare quanto chiesto. Infatti esso considera i numeri che NON sono della forma $ax+by$, con $x$ e $y$ positivi, dunque alla fine ci si trova comunque a dover dimostrare da capo che per $c>=ab$ sono tutti della forma in questione.