Combinaison linéaire de deux entiers positifs
Répondre à la discussion
Affichage des résultats 1 à 4 sur 4

Combinaison linéaire de deux entiers positifs



  1. #1
    invite0ccb3982

    Combinaison linéaire de deux entiers positifs


    ------

    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

    -----

  2. #2
    Médiat

    Re : Combinaison linéaire de deux entiers positifs

    Citation Envoyé par kemlicz Voir le message
    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)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    invite0ccb3982

    Re : Combinaison linéaire de deux entiers positifs

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

  4. #4
    invite2c3ff3cc

    Re : Combinaison linéaire de deux entiers positifs

    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 )

  5. A voir en vidéo sur Futura

Discussions similaires

  1. Ion positifs et négatifs
    Par sabulle dans le forum Chimie
    Réponses: 18
    Dernier message: 03/07/2007, 21h34
  2. Systeme d'équation Linéaire à deux inconnues ??!
    Par invitef5dc7e34 dans le forum Mathématiques du collège et du lycée
    Réponses: 11
    Dernier message: 08/05/2007, 11h43
  3. Combinaison linéaire de matrices
    Par invitef5fbbe00 dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 12/04/2007, 02h31
  4. Pgcd de deux nombres entiers
    Par inviteea59665a dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 27/12/2006, 20h07
  5. Combinaison Linéaire
    Par invite1a8a4f0b dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 21/03/2006, 05h39