numeri naturali

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

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.

Il teorema da cui ho preso spunto io e che deriva come corollario da questo è il seguente:

Siano $a$ $b$ interi positivi coprimi tra loro. L'equazione $ax+by=c$ ammette soluzioni intere positive se $c>ab-a-b$. E questo mi sembra possa andare bene nel nostro caso.

[fields]

Si, è chiaro che la proprietà che citi va bene in questo caso. Ma l'esercizio era dimostrare per conto proprio che la proprietà è valida, non dire: Ah si la conosco, l'ha già dimostrata Frobenius, e citare semplicemente il risultato. Così sono capaci tutti...

[Salamandra]

Per favore, potete rischiarare le tenebre della mia ignoranza: che cos'è l'algoritmo di Euclide? L'ho già sentito ma non lo ricordo.

[fields]

L'algoritmo di Euclide serve per trovare il massimo comun divisore fra due numeri. Dall'algoritmo di Euclide deriva che se $d$ è il massimo comun divisore di $a$ e $b$ esistono interi $x$ e $y$ tali che $ax+by=d$.

[giuseppe87x]

fields a questo punto, visto che non posta nessuno niente, puoi far vedere la tua dimostrazione.

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

Soluzione.

Allora. Sia $c=aq+r$, con $0<=r<a$. Poiché $c>=ab$, $q>=b$. Poiché $a$ e $b$ sono primi fra loro, il più piccolo naturale $k>0$ tale che $bk-=0 (mod a)$ è $a$ (questo perché $mcm(a,b)=ab$). Dunque $0,b,2b,3b,...,(a-1)b$ danno resti tutti fra loro diversi quando divisi per $a$. Poiché la quantità di tali numeri è $a$, esistono $y,z>=0$, con $y<a$, tali che $by=az+r$. Dall'uguaglianza ricaviamo che $z<=b$. Poiché $q>=b$, $z<=b$ e dunque $z<=q$. Possiamo dunque scrivere

$c=aq+r=a(z+x)+r$, con $x>=0$. Ma allora

$c-by=az+ax+r-az-r=ax$. Dunque $c=ax+by$, con $y>=0$ e $x>=0$, che è quanto volevamo dimostrare.


Nota: esiste anche una dimostrazione geometrica di questo fatto (e tale dimostrazione era la soluzione del libro che ho consultato).

[giuseppe87x]

Bene!
A proposito, quale libro hai consultato?

[karl]

Noto che deve essere c>ab e non c>=ab,altrimenti non si
possono avere soluzioni totalmente positive ma solo del tipo
(b,0) e (0,a).
Cio' detto veniamo all'interpretazioine geometrica .
L'equazione (1) ax+by=c e' quella di una retta che taglia i semiassi positivi
nei punti $A(c/a,0), B(0,c/b)$ la cui distanza L e':
(2) $L=sqrt((c^2)/(a^2)+(c^2)/(b^2))=c/(ab)sqrt(a^2+b^2)=q*delta+r/(ab)*delta$
avendo posto $c=(ab)*q+r,delta=sqrt(a^2+b^2)$
I punti le cui coordinate sono soluzione intera della (1)
sono detti nodi della retta e se $(alpha,beta)$ e' uno di questi
tutti gli altri sono del tipo:
$(alpha+kb,beta-ka)$ con k intero relativo.La distanza tra due
nodi consecutivi (corrispondenti a due valori consecutivi di k) e',come
e' facile verificare,uguale a $delta$ e quindi la (2) ci dice che
nel segmento AB di misura $bar(AB)=L$ ,tutto contenuto nel 1° quadrante, vi sono almeno
q nodi (e in realta' non piu' di q+1) tra i quali compaiono anche quelli a coordinate totalmente positive.
E poiche' per ipotesi e' $c>ab$ ovvero $q>=1$ ,questo prova la tesi.
karl

[fields]

Bene Karl! Con una dimostrazione puramente aritmetica e una geometrica ora siamo completi!

@ giuseppe87x

Be', io leggo praticamente sempre libri matematici in inglese. Il libro in questione è "Elementary number theory" di Jones & Jones. Un libro bellissimo per chi parte da zero, non solo in teoria dei numeri, ma anche in matematica. Purtroppo contiene però pochissimi esercizi non banali, e forse proprio per il pubblico a cui è rivolto. In ogni caso tratta una fetta notevole di teoria dei numeri.

[fields]

Una dimostrazione ancora più semplice, che fornisce subito le soluzioni.

Vogliamo le soluzioni positive di $ax+by=c$, supponendo che $c>=ab-b$ e $a$ e $b$ primi fra loro.e positivi. Poniamo $y=b^(-1)c (mod a)$ e $x=(c-b[b^(-1)c(mod a)])/a$. Abbiamo che $b^(-1) (mod a)$ esiste ed è maggiore di $0$ poiché $a$ e $b$ sono primi fra loro. $x$ è intero perché $c-b[b^(-1)c (mod a))$ è divisibile per $a$. $x>=0$ poiché $y<=a-1$ e dunque $c-by>=c-b(a-1)>=ab-b-ab+b=0$.