combinazioni lineari positive

[ma_go]

un esercizietto classico per principianti:
fissiamo due interi positivi $a,b$ coprimi. qual è il massimo intero positivo $N$ che non sia della forma $ha+kb$ per qualche $h,k$ interi non-negativi? quanti sono gli interi positivi che non si scrivono in quella forma?

[auron95]

Mmh... ma esiste una formula bella e pulita per ricavare il numero di numeri non ottenibili dalla forma $ha+kb$?

EDIT stavo scherzando, l'ho trovata, adesso devo pensare perchè è vera

[auron95]

Ok provo io (metto il testo nascosto così se qualche altro novizio come me vuole provare non si rovina la sorpresa)

Testo nascosto:

$n$ si può scrivere come $ka+hb$ se e solo se esiste k tale che $kb \equiv n \pmod a$ ,in modo che la differenza sia un multiplo di $a$, e $kb < n$ (altrimenti dovrei togliere un multiplo di $a$ per ottenere $n$, cosa non concessa)
Dato che $a$ e $b$ sono coprimi, allora $0, b,2b,3b,\dots, (a-1)b$ sono tutte le classi di resto modulo $a$ (in gara potrei darlo per noto o dovrei dimostrarlo?), quindi se $n\ge (a-1)b$ sicuramente ho una combinazione lineare per scrivere $n$.

Se invece da quei multipli di $b$ tolgo dei multipli di $a$ ottengo numeri non esprimibili, in quanto il più piccolo multiplo di $b$ congruo ad $n$ è sicuramente maggiore.

Il più alto $n$ che posso ottenere con questo metodo lo ottengo togliendo dal multiplo di b più alto $(a-1)b$ (non posso prendere altri multipli altrimenti ne avrei uno più piccolo congruo mod a) il minimo multiplo di $a$ (cioè proprio $a$).
Quindi l'$n$ cercato è $(a-1)b-a=(a-1)(b-1)-1$ (che viene simmetrico in a e b come dovrebbe, per fortuna)

Per quanto riguarda il numero di numeri non esprimibili, preso un $kb$, $0\le k<a$, allora posso togliere $\displaystyle \left[\frac{kb}{a}\right]$ diversi multipli senza ottenere numeri negativi.
Sia ora $kb = q_ka+r_k$
Il numero cercato lo posso esprimere come $\displaystyle \sum_{k=0}^{a-1} q_k = \sum_{k=0}^{a-1} \frac{q_ka+r_k}{a}-\sum_{k=0}^{a-1}\frac{r_k}{a}=\frac 1a\left(b\sum_{k=0}^{a-1}k -\sum_{k=0}^{a-1}r_k\right)$

Ora la somma degli $r_k$ è la somma di tutti i resti modulo $a$ cioè i numeri da $0$ a $a-1$. Quindi è uguale alla somma dei $k$ (solo ordinata diversamente)
Quindi ottengo $\displaystyle \frac 1a (b-1)\sum_{k=0}^{a-1} k = \frac {(b-1)}a \cdot \frac{a(a-1)}2=\frac{(a-1)(b-1)}2$

Spero che l'hide non dia problemi con il $\LaTeX$ ... altrimenti lo tolgo.

[ma_go]

mi pare che torni, sì. e quella cosa la puoi dare per scontata, in gara: l'importante è che tu metta in evidenza (come hai fatto) il fatto che usi l'ipotesi che $a$ e $b$ siano coprimi.

dovrebbero esserci altre dimostrazioni per la seconda richiesta, e sto ancora cercando di capire se ci sia una soluzione "elegantissima" di una delle due parti del problema. se qualcuno (anche dei più esperti) ha idee, dica pure.