Annuler
connectez vous
- Arithmétique : divisibilité, PGCD et PPCM, Nombres premiers
- Des mathématiciens célèbres : Fermat et Gauss
- Fonction exponentielle - Fiche de Cours terminale
- Le raisonnement par récurrence : principe et exemples rédigés
- Fiche sur les nombres complexes - terminale
- Limites de fonctions - Cours sur les limites
- Cours sur les suites en Terminale S
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale ArithmétiqueTopics traitant de Arithmétique [tout]Lister tous les topics de mathématiques
Niveau terminale
exo de spé arithmétique
Posté par domager (invité)
Salut a tous voila j'ai le problème suivant :
a et b désignent deux entiers naturels premiers entre eux
On dispose d'un nombre non limité de pièces de a euros et d'un nombre non limité de pièces de b euros. Quelle est la plus grande somme que l'on ne peut pas payer avec ces pièces?
je n'arrive pas à trouver un raisonnement pouvez vous m'aidez?
Merci
Posté par domager (invité)re : exo de spé arithmétique
Re j'ai beau avoir la formule je ne comprend pas quelequ'un peu m'expliquer?
As-tu vérifé la formule? Car elle est fausse (c'est une combinaison linéaire à coefficients positifs de a et de b). La bonne formule est en fait ab-a-b=(a-1)(b-1)-1.
Si ça peut d'aider.
Bonjour
Si a et b sont premiers entre eux, pour tout n il existe u et v tels que au+bv=n (Bézout). l'ennui est que souvent u et v ne sont pas tous les deux positifs. Alors si on accepte de payer avec des pièces de a et de se rendre la monnaie avec des pièces de b, je ne vois pas où est le problème!
Salut Camelia,
je pense qu'on considere sans rendue de monnaie sinon l'exo n'a pas trop d'interet c'est à dire avec les coefficients positifs dans l'equation de Bezout.
Bon deja a et b sont premiers entre eux il existe donc u et v tels que au+bv=c.
Donc par suite en faisant la division euclidienne de u par b on a:
u=bq+r avec 0<=r<b donc :
a(bq+r)+bv=c d'ou ar+b(v+aq)=c.
r est positif demandons nous quand v+aq l'est.
v+aq=(c-au)/b+qa=(c-au+qab)/b donc:
v+aq>=0 ssi c-au+qab>=0 ssi c>=au-qab ssi c>=a(u-qb)>=ar donc si c>=a(b-1) le resultat est bon car r<=(b-1).
De meme en divisant v par a on obtient:
v=aq'+r' avec 0<=r'<=(a-1)
On obtient au+b(aq'+r')=br'+a(bq'+u)=c.
Donc bq'+u>=0 ssi (c-bv)/a+bq'>=0 ssi c-bv+bq'a>=0 ssi c>=bv-bq'a=b(v-q'a)=br' donc si c>=b(a-1) on a aussi le resultat.
Donc si c>=min(b(a-1),a(b-1) alors la somme est possible.
Est ce qu'on peut faire mieux?
Exemple:
si on prend a=2,b=3 on ne peut obtenir min(b(a-1),a(b-1))=min(3,4)=3 et on peut faire deux donc ca doit etre ameliorable un petit peu à suivre.
je cherche... Cauchy,dans ta démarche, tu suppose que u et v existent et sont positifs...
ne faut-il pas chercher à quelle(s) condition(s) u et v ne peuvent pas pas être positifs en même temps?
.... mais franchement, je suis "à l'ouest"! 
Non au depart u et v sont entiers verifiant l'equation de Bezout ils ne sont pas necessairement positifs je montre comment on peut se ramener à des coefficients positifs par division euclidienne sous certaines conditions pour c.
j'ai une piste, j'ai trouvé de l'aide sur un autre forum... je vous retrouve d'ici quelques heures...
voici les indices :
il existe u et v entiers relatifs tels que au+bv=c
si (u,v) est solution alors (u+kb;v-ka) est auusi solution
il existe une solution entière la plus petite possible, c'est le reste de la division euclidienne de u par b, u0=r avec 0
rb-1
de cet encadrement, on doit pouvoir trouver une solution "astucieuse" pour v0 et que cette solution astucieuse conduise à c
ab-a-b-1
il faudra alors montrer que ab-a-b n'est pas "payable"
l'espoir renait malgré un "non-aboutissement"...
oui mais qu'est qui prouve que v est entier?
ensuite si on arrive à montrer que u et v entiers relatifs existent pour c(a-1)(b-1)
il faudra encore prouver que le plus petit entier inférieur à ce nombre n'est pas "payable" à savoir qu'il n'existe pas u et v entiers naturels tels que (a-1)(b-1)-1=au+bv
raisonnons par l'absurde en supposant qu'il existe deux entiers naturels u et v tels que :
au+bv=(a-1)(b-1)-1
choisissons l'entier u compris entre 0 et b-1 (le reste de la division par b de u)
au+bv=ab-a-a+1-1
a(u+1)+b(v+1)=ab
b divise ab et b divise b(v+1) donc b divise a(u+1)
or b est premier avec a donc avec le th de Gauss, b divise u+1
or u+1 est un entier naturel compris entre 1 et b, la seule possibillité pour que b divise u+1 est u+1=b
on a alors ab+b(v+1)=ab donc b(v+1)0
or v+1>0 et b>0 , c'est impossible donc l'hypothèse de départ est fausse, avec des pièces de a euros et des pièces de b euros, le nombre (a-1)(b-1)-1=ab-a-b n'est pas "payable"
je reviens pour la première partie...
ok, je reprends ta démarche Cauchy :
Donc par suite en faisant la division euclidienne de u par b on a:
u=bq+r avec 0<=r<b donc :
a(bq+r)+bv=c d'ou ar+b(v+aq)=c.
r est positif demandons nous quand v+aq l'est.
v+aq=(c-au)/b+qa=(c-au+qab)/b donc:
v+aq>=0
puisque v+aq est un entier v+aq>=0 ssi v+aq>-1
ssi (c-au+qab)/b>-1 ssi c-au+qab>-b ssi c>a(u-qb)-b donc ssi c>ar-b
si c>a(b-1)-b le resultat est bon car r<=(b-1)
on a donc si c>=a(b-1)-b+1 alors le résultat est bon.
soit si c>=ab-b-a+1 alors la somme c est "payable"
reste à prouver que l'entier immédiatement inférieur n'est pas payable et c'est fini...
qu'en pensez-vous?
pour la deuxième partie de la démonstration, il y a encore plus élégant :
on a montré que l'on peut payer toute somme supérieure ou égale à ab-a-b+1 avec des pièces de a euros et des pièces de b euros, montrons la somme maximale non "payable" est l'entier précédent ce nombre, à savoir ab-a-b
montrons par l'absurde que le nombre ab-a-b n'est pas "payable" avec des pièces de a euros et des pièces de b euros.
supposons qu'il existe deux entiers naturels u et v tels que :
au+bv=ab-a-b
a(u+1)+b(v+1)=ab
b divise ab et b divise b(v+1) donc b divise a(u+1)
or b est premier avec a donc avec le th de Gauss, b divise u+1
de même a divise v+1
comme u et v sont des entiers naturels, u+1 et v+1 sont strictement positifs donc
u+1b et v+1a
on a donc a(u+1)ab et b(v+1)ab
ce qui entraine a(u+1)+b(v+1)2ab
or on a supposé que ab=a(u+1)+b(v+1), on aurait donc ab2ab
c'est absurde, le nombre ab-a-b n'est donc pas "payable", tous ceux qui lui sont supérieurs le sont donc le plus grand nombre non payable est ab-a-b
Bonjour,
Je suis actuellement sur ce même problème mais je ne comprends pas le raisonnement qui a abouti à sa résolution. Quelqu'un pourrait-il tenter de le formuler autrement ?
Merci d'avance pour votre aide.
Bonjour,
La démonstration du dernier message me semble compréhensible et indépendante du reste.
Elle démontre que ab-b-a n'est pas payable avec des pièces de a Euros et de b Euros.
Je vais tenter une formulation un peu différente pour démontrer ceci :
Si c ab - a- b +1 alors il existe des entiers naturels x et y tels que xa + yb = c.
Mais je n'aurai peut-être pas le temps ce matin.
Ces remarques en attendant :
Si a = 1 ou b =1, alors toute somme est payable avec ces pièces.
Il faut donc supposer a 2 et b 2.
Avec cette hypothèse, on a bien ab - a -b 0.
On a même ab - a -b 1 car le couple (2,2) ne vérifie pas a et b premiers entre eux.
Ci-dessous, une démonstration pour :
Si c
ab - a - b +1 alors
il existe des entiers naturels x et y tels que xa + yb = c .
Soit c un entier tel que c
ab - a - b +1 .
Il existe u et v entiers relatifs tels que au + bv = c .
On utilise la division euclidienne de u par b :
u = bq + r avec
0
r < b .
Soit s = v + aq .
On a alors ar + bs = c .
Il reste à démontrer que l'entier relatif s est un entier naturel.
c ab -a -b +1 . D'où ar + bs
ab -a -b +1 .
Puis b(s+1)
a(b-r-1) + 1 .
Or r < b
; donc
b-r
1 .
D'où b(s+1)
1 . Qui donne s+1
1/b > 0.
L'entier s+1
est strictement positif ;
donc s+1
1 . D'où s
0 .
J'y ai trouvé cette démonstration qui me semble plus simple pour démontrer
Si c
ab - a - b +1 alors
il existe des entiers naturels x et y tels que
xa + yb = c .
En passant par la contraposée :
S'il n'existe pas des entiers naturels x et y tels que xa + yb = c
alors
c
ab - a - b .
Soit c un entier naturel.
Il existe u et v entiers relatifs tels que au + bv = c .
On utilise la division euclidienne de u par b :
u = bq + r avec
0
r < b .
Soit s = v + aq .
On a alors ar + bs = c
où
r
est un entier naturel et vérifie
r
b-1 .
S'il n'existe pas des entiers naturels x et y tels que xa + yb = c
alors
l'entier relatif s
n'est pas un entier naturels ; donc
s
-1 .
On en déduit facilement c
ab - a - b .