Combinaison linéaire de deux entiers positifs

[invite0ccb3982]

Bonjour
D'après le théorème de Bézout, si deux entiers positifs a et b sont premiers entre eux alors il existe u et v entiers relatifs tels que au + bv = 1 donc, à fortiori, pour tout entier n, il existe u' et v' tel que au'+bv' = n.
Mais dans le cas où l’on considère uniquement u' et v' positifs, tous les nombres n positifs ne peuvent être écrits sous la forme au'+bv'.
En faisant un programme, je me suis aperçu, pour les valeurs de a et b de mon programme, que c’était seulement à partir de (a-1)(b-1) que tous les nombres étaient atteints par combinaison linéaire à coefficients positifs de a et b.
Je cherche une confirmation sachant que je n'ai ni réussi à le démontrer ni réussi à trouver un théorème correspondant sur internet (s’il existe).
Merci
-----

[Médiat]

Bonjour
En faisant un programme, je me suis aperçu, pour les valeurs de a et b de mon programme, que c’était seulement à partir de (a-1)(b-1) que tous les nombres étaient atteints par combinaison linéaire à coefficients positifs de a et b.

Voici la démonstration que j'ai donné dans un autre fil (les notations sont différentes)
http://forums.futura-sciences.com/sc...thmetique.html

La question était de trouver le plus grand que l'on ne peut pas écrire (ce qui revient bien au même).

si m et n ne sont pas premiers entre eux : pas de solution (trivial)
si m et n sont premiers entre eux (désolé, mais je n'ai pas le temps de rédiger proprement):
1) si x >= mn - n alors il existe a et b tels que x = an + bm, en effet
et on peut écrire
2) si x = mn - n - m, il n'existe pas de a et b tels que x = am + bn, dans le cas contraire on aurait :
mn - n - m = an + bm
mn =(a+1)n + (b+1)m
donc
donc



donc soit k soit k' = 0 ce qui est impossible car on aurait a ou b négatif.
3) si x = mn - n - m + k avec 0 < k < m
soit c tel que , il existe d tel que donc


(il faudrait montrer proprement que , mais c'est sans problème)

Le plus grand nombre que l'on ne peut pas écrire sous la forme an + bm est donc (mn - n - m)

[invite0ccb3982]

Merci pour la réponse (même si, je l'avoue, j'ai eu du mal à comprendre toutes les étapes de la démonstration).

[invite2c3ff3cc]

C'est très connu, c'est le problème de Frobenius ou des pièces de monnaie ( http://en.wikipedia.org/wiki/Coin_problem ou http://mathworld.wolfram.com/CoinProblem.html )

[A voir en vidéo sur Futura]