Numeri naturali
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!
Attenzione, $x$ e $y$ sono richiesti essere positivi!
Risposte
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.
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.
a=3
b=5
c=16
mi pare sia un controesempio
o sbaglio?
b=5
c=16
mi pare sia un controesempio
o sbaglio?
Se non ho abbagli mi pare che 16=3*2+5*2, no?
quando dico che non so fare i conti è vero!
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...
Dipenda da cosa intendi per "parte elementare"...
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?
Ma per curiosità: cosa dice il citato teorema di Frobenius?
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.
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.
"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.
"fields":
[quote="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.[/quote]
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.
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... 
Per favore, potete rischiarare le tenebre della mia ignoranza: che cos'è l'algoritmo di Euclide? L'ho già sentito ma non lo ricordo.
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$.
fields a questo punto, visto che non posta nessuno niente, puoi far vedere la tua dimostrazione.
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=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=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).
Soluzione.
Allora. Sia $c=aq+r$, con $0<=r
$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).
Bene!
A proposito, quale libro hai consultato?
A proposito, quale libro hai consultato?
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
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
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.
@ 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.
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$.
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$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo