problème de Frobenius

ARITHMETIQUE

Le problème de Frobenius , ou problème des pièces de monnaie est la recherche du plus grand nombre qui ne peut pas être atteint en utilisant seulement des pièces de montants déterminés.

En termes mathématiques, étant donnés n entiers strictement positifs a1, a<inf<2,.,an, tels que pgcd(a1, a2,.,an ) = 1, il s’agit de trouver le plus grand nombre qui ne peut pas s’écrire sous forme d’une combinaison linéaire k1a1 + k2a2+. + knan, où les ki sont des entiers positifs. Ce nombre est appelé nombre de Frobenius.
Le cas n=1 est trivial puisqu’alors a1 = 1. Il n’y a pas de nombre de Frobenius.
Le cas n=2 a été démontré par Sylvester (1884). Le nombre de Frobenius est a1a2-a1-a2.
Pour les valeurs de n supérieures, il n’y a pas de formule mais il existe des algorithmes qui permettent de le déterminer.