OliForum Matematico

dopo la vacanza che mi sono fatto a Lisbona mi sento molto arrugginito e questo non va bene. non riesco bene a risolvere alcune diofantee facili.
allora mi sono detto continua con la teoria e, avendo fatto così, mi sono imbattuto nella definizione di un numero che il mio testo denomina con G. non so come si chiami.
mi sembra che sia il più piccolo numero che si possa scrivere come combinazione lineare: ax + by=c

e che deve essere minore o uguale a c.
lo G di due numeri a e b si trova facendo (a-1)*(b-1)
mi sapreste dire che cavolo è? e se serve nelle soluzioni?


altro problema:
una diofantea di primo grado può avere più di una soluzione intera. com'è possibile?

scusate per la scrittura e la fretta ma non sono sul mio computer

matteo16 ha scritto: altro problema:
una diofantea di primo grado può avere più di una soluzione intera. com'è possibile?

non ho ancora capito la prima

Se ho capito bene che cosa stai chiedendo...

Un 'equazione diofantea di due variabili di primo grado è della seguente forma $ \displaystyle ax+by=c $

Si chiama omogenea quando c=0
Un'equazione diofantea omogenea ammette sempre infinite soluzioni.
Sia$ \displaystyle (x_k,~y_k) $ una soluzione allora sono soluzioni anche $ \displaystyle (x_k \cdot z,~y_k \cdot z) $ con z intero

Un'equazione diofantea non omogenea ammette infinite soluzioni se e solo se $ \displaystyle (a,b)|c $
In pratica trovi le infinite soluzioni della omogenea $ \displaystyle ax+by=0 $ che chiamiamo $ \displaystyle (x_1,~y_1)...(x_n,~y_n) $,
poi trovi una soluzione della non omogenea che chiamiamo $ \displaystyle (x_m, ~y_m) $ allora le infinite soluzioni sono $ \displaystyle (x_m+x_1,~ y_m+y_1)...(x_m+x_n,~y_m+y_n) $



ps. va in glossario.

ti sei dimenticato di specificare che a,b,x,y sono interi /positivi/ credo.
G non ha un nome per quel che ne so; quello che citi è un lemmetto che può tornare utile ogni tanto ma decisamente non lo definirei una delle pietre miliari della teoria dei numeri .

(a proposito, già che abbiamo sollevato la questione, qualcuno ha voglia di dimostrarlo per esercizio?
Dati a,b interi positivi, dimostrare che G=(a-1)(b-1) è il più grande intero che non si può scrivere come ax+by, con x,y interi positivi.
)

Prima cosa, a e b devono essere coprimi, affinché valgano i discorsi che state facendo.
Seconda cosa, quello che chiede di dimostrare fph è falso, ed in realtà è G-1 il massimo intero non esprimibile come ax+by.
Terza cosa, aggiungo che fra gli interi tra 0 e G-1, esattamente la metà sono esprimibili come ax+by, sempre con x e y non negativi. Dimostrate anche questo, già che ci siete.

fph ha scritto:ti sei dimenticato di specificare che a,b,x,y sono interi /positivi/ credo.

Spero di non fare questi errori stupidi in gara.

Dati a,b interi positivi, dimostrare che G-1, con G=(a-1)(b-1), è il più grande intero che non si può scrivere come ax+by, con x,y interi non negativi.

Ci provo

Dimostriamo che
1. $ \displaystyle ax+by $ non può essere uguale a $ \displaystyle G-1 $
2. $ \displaystyle ax+by=G-1+z $ ha sempre soluzioni con z intero positivo

1. Supponiamo per assurdo che $ \displaystyle ax+by=(a-1)(b-1)-1 \Longrightarrow ax+by=ab-a-b $$ \displaystyle \Longrightarrow (x+1)a+(y+1)b=ab $
RHS è un multiplo do a, $ \displaystyle (x+1)a $ è un multiplo di a, di conseguenza, anche $ \displaystyle (y+1)b $ è un multiplo di a. Per ipotesi avevamo che (a,b)=1 e quindi $ \displaystyle a|y+1 $. Con lo stesso procedimento si dimostra che $ \displaystyle b|x+1 $.
$ \displaystyle (x+1) $ e $ \displaystyle (y+1) $ sono sempre positivi e quindi LHS è maggiore stretto di RHS, assurdo. Quindi abbiamo dimostrato che $ \displaystyle ax+by \neq G-1 $

2. $ \displaystyle a(x+1)+b(y+1)=ab+z $.

Siccome il caso è simmetrico, supponiamo che $ \displaystyle a>b $.
Abbiamo quindi per un certo k:
$ \displaystyle a \equiv k \pmod b $
$ \displaystyle 2a \equiv 2k \pmod b $
$ \displaystyle 3a \equiv 3k \pmod b $
$ \displaystyle 4a \equiv 4k \pmod b $
...
$ \displaystyle ba \equiv 0 \pmod b $
con $ \displaystyle (k,b)=1 $

Dimostriamo ora che $ \displaystyle k, ~2k,~ 3k,~ ...,~ bk $ coprono tutti i residui modulo $ \displaystyle b $.
Infatti, se non li coprissero allora per Pigeonhole avremo $ \displaystyle mk-nk \equiv 0 \pmod b \Longrightarrow m-n \equiv 0 \pmod b $ (con $ \displaystyle m\neq n~e~ m,~n~ \leq ~b) $ che è assurdo.

Da questo punto si conclude facilmente che qualunque numero maggiore di $ \displaystyle ab $ può essere scritto come $ \displaystyle ax+by $, infatti se abbiamo un numero $ \displaystyle r $ (maggiore di $ \displaystyle ab $) tale che $ \displaystyle r \equiv s \pmod b $ allora possiamo sempre prendere un certo $ \displaystyle ta $ (con $ \displaystyle t \leq b $) tale che $ \displaystyle ta \equiv s \pmod b $ e aggiungere un multiplo di $ \displaystyle b $ in modo che la somma faccia $ \displaystyle r $.

Giusto

Se è giusto questo allora penso che

Terza cosa, aggiungo che fra gli interi tra 0 e G-1, esattamente la metà sono esprimibili come ax+by, sempre con x e y non negativi. Dimostrate anche questo, già che ci siete

sia abbastanza immediato...

Tibor Gallai ha scritto:Seconda cosa, quello che chiede di dimostrare fph è falso, ed in realtà è G-1 il massimo intero non esprimibile come ax+by.

oops... In effetti temevo un off-by-one ma ero troppo pigro per verificarlo.

Trovato! Si chiama numero di Frobenius
http://it.wikipedia.org/wiki/Problema_delle_monete

Una dimostrazione (non tanto elementare) si trova a
http://www.mat.uniroma3.it/users/fontan ... n1_1.2.pdf

In gara devo dimostrare questo lemma ogni volta che lo uso?

mod_2 ha scritto: Se è giusto questo allora penso che

Terza cosa, aggiungo che fra gli interi tra 0 e G-1, esattamente la metà sono esprimibili come ax+by, sempre con x e y non negativi. Dimostrate anche questo, già che ci siete

sia abbastanza immediato...

Come mi ha fatto notare Carlein, questo lemma non è poi così immediato...


Vi propongo la dimostrazione che (ho) fatto con tantissimi aiutini di Carlein (in realtà ha fatto quasi tutto lui)

Allora supponiamo $ \displaystyle b>a $ e $ \displaystyle b=ka+s $ con $ \displaystyle s<a $.

Il problema equivale a trovare il numero delle soluzioni della disuguaglianza $ \displaystyle ax+by<ab-a-b $ con a,b interi positivi e x, y interi non negativi.

Giocando un pò con le disuguaglianze troviamo che

1) $ \displaystyle x<b-1- \dfrac{b+by}{a} $
2) $ \displaystyle by<ab-a-b \Longrightarrow y<a- \dfrac{a}{b} -1 $$ \displaystyle \Longrightarrow y \leq a-2 $

Allora abbiamo che
$ \displaystyle y=a-2~~~~~~~~~~x<-1+\dfrac{b}{a} $
$ \displaystyle y=a-3~~~~~~~~~~x<-1+\dfrac{2b}{a} $
...
$ \displaystyle y=a-a~~~~~~~~~~x<-1+\dfrac{(a-1)b}{a} $

Dobbiamo quindi fare la somma del numero delle soluzioni x in ciascuna di queste disuguaglianze (ricordiamo che anche x=0 è soluzione e quindi ognuno va sommato a 1).

Sia ora $ \displaystyle \left[ z \right] $ la parte intera di z, la nostra somma diventa

$ \displaystyle \left[ -1+\dfrac{b}{a}+1 \right]+\left[ -1+\dfrac{2b}{a}+1 \right]+...+\left[ -1+\dfrac{(a-1)b}{a}+1 \right] $$ \displaystyle =\left[ \dfrac{b}{a} \right]+\left[ \dfrac{2b}{a} \right]+...+\left[ \dfrac{(a-1)b}{a} \right] $

Ricordando ora b=ka+s

la somma è uguale a
$ \displaystyle k+2k+...+(a-1)k+\left[ \dfrac{s}{a} \right] $$ \displaystyle +\left[ \dfrac{2s}{a} \right]+...+\left[ \dfrac{(a-1)s}{a} \right] $

Siccome s e a sono primi fra di loro e s<a allora $ s,~2s,~...~(a-1)s $ coprono tutti i residui modulo a tranne 0.

E quindi se scriviamo la somma senza tenere il conto che devo prendere la parte intera, devo sottrarre tutti i residui modulo a (tranne 0)

$ \displaystyle \left[ \dfrac{b}{a} \right]+\left[ \dfrac{2b}{a} \right]+...+\left[ \dfrac{(a-1)b}{a} \right] $$ \displaystyle =\dfrac{b}{a} + \dfrac{2b}{a} +...+ \dfrac{(a-1)b}{a} - \dfrac{a(a-1)}{2a} $$ \displaystyle = \dfrac{b(a-1)}{2}-\dfrac{a-1}{2}=\dfrac{ab-b-a+1}{2} $
da cui la tesi

ho unito i vari 3d per non creare confusione