Nombres premiers (seconde)

[Anonyme]

J'ai un souci dans un pb :

on me donne deux nombres premiers entre eux (pgcd=1).
C'est une histoire de timbres, mais cela revient à trouver le plus
grand nombre qui ne peut pas etre combinaison linéaire des deux
nombres premiers entre uex.

Pour cela on prend l'exemple de 3 et 10. Le plus grand nombre qui ne
peut pas etre "fabriqué" par des 3 et 10 est 17.
Pour le trouver j'ai cree un tableau excel de 10x10. Chaque ligne part
d'un multiple de 10 auquel j'ajoute 3 systematiquement. Et j'ai noirci
à partir de 30 et en dessous jusqu'a ce que je ne puisse plus trouver
de nombre dans mon tableau. Ca donne ici 17.

On prend l'exemple de 13 et 17.
Mon tableau fait 17lignes par 17 colonnes.
Chaque ligne demarre par un multiple de 17 et va de 13 en 13.
J'ai commence a noircir mon tableau a partir de 221 (17*13)en
decroissant.
Le plus grand nombre introuve est donc 191.

Maintenant ma question est comment trouver le plus grand nombre qui ne
sera pas une combinaison lineaire de x et y si pgcd(x;y)=1 et
pourquoi.

Supposons que x soit plus grand que y et que x et y premiers entre
eux. Comment trouver n tel que n+1 = ax + by avec a et b appartenant a
N et n impossible a faire de cette maniere.
Je seche .....

Merci de m'aider.
Arthur

[Anonyme]

Je ne comprends pas ce que tu veux faire.
Moi j'arrive à atteindre 17 avec 3 et 10
17=3x(-51)+10x17.
Plus généralement le résultat est basé sur le théorème de Bezout :
Si a et b sont premiers entre eux il existe x0 et y0 entiers tel que
ax0+by0=1
si tu veux atteindre n anx0+bny0=n



"Arthur" a écrit dans le message de news:
4159c3af.2912227@news.calixo.net...
> J'ai un souci dans un pb :
>
> on me donne deux nombres premiers entre eux (pgcd=1).
> C'est une histoire de timbres, mais cela revient à trouver le plus
> grand nombre qui ne peut pas etre combinaison linéaire des deux
> nombres premiers entre uex.
>
> Pour cela on prend l'exemple de 3 et 10. Le plus grand nombre qui ne
> peut pas etre "fabriqué" par des 3 et 10 est 17.
> Pour le trouver j'ai cree un tableau excel de 10x10. Chaque ligne part
> d'un multiple de 10 auquel j'ajoute 3 systematiquement. Et j'ai noirci
> à partir de 30 et en dessous jusqu'a ce que je ne puisse plus trouver
> de nombre dans mon tableau. Ca donne ici 17.
>
> On prend l'exemple de 13 et 17.
> Mon tableau fait 17lignes par 17 colonnes.
> Chaque ligne demarre par un multiple de 17 et va de 13 en 13.
> J'ai commence a noircir mon tableau a partir de 221 (17*13)en
> decroissant.
> Le plus grand nombre introuve est donc 191.
>
> Maintenant ma question est comment trouver le plus grand nombre qui ne
> sera pas une combinaison lineaire de x et y si pgcd(x;y)=1 et
> pourquoi.
>
> Supposons que x soit plus grand que y et que x et y premiers entre
> eux. Comment trouver n tel que n+1 = ax + by avec a et b appartenant a
> N et n impossible a faire de cette maniere.
> Je seche .....
>
> Merci de m'aider.
> Arthur

[Anonyme]

Tout ceci est-il au programme de seconde ??

[Anonyme]

Le 28/09/2004 22:45, Mic a écrit :
> Je ne comprends pas ce que tu veux faire.
> Moi j'arrive à atteindre 17 avec 3 et 10
> 17=3x(-51)+10x17.

La référence à l'histoire de timbres sous-entend que les multiplicateurs
sont positifs. Un énoncé plus complet serait : comment affranchir une
enveloppe avec 17 brouzoufs quand tu ne disposes que de timbres à 3
brouzoufs et de timbres à 10 brouzoufs.

Tu ne peux pas attendre le facteur pour qu'il te rende la monnaie :
pour reprendre ton exemple, tu ne vas donc pas mettre 17 timbres à 10
brouzoufs, en espérant que l'on te rende 51 timbres à 3 brouzoufs.

Par ailleurs, merci de ne pas citer l'intégralité de l'article auquel tu
réponds (accessoirement, on répond plutôt après une question qu'avant).
Plus de détails ici : .

[Anonyme]

On me dit de prendre des entiers positifs et non relatifs.
Il faut donc trouver n appartenant a N tel que il existe a et b
entiers naturels et ax + by = n+1 mais que ce soit impossible avec n.
Voila le probleme dans sa base.
Et la, je coince vraiment.

On Tue, 28 Sep 2004 22:45:44 +0200, "Mic" wrote:

>Je ne comprends pas ce que tu veux faire.
>Moi j'arrive à atteindre 17 avec 3 et 10
>17=3x(-51)+10x17.
>Plus généralement le résultat est basé sur le théorème de Bezout :
>Si a et b sont premiers entre eux il existe x0 et y0 entiers tel que
>ax0+by0=1
>si tu veux atteindre n anx0+bny0=n
>
>
>
>"Arthur" a écrit dans le message de news:
>4159c3af.2912227@news.calixo.net...[color=green]
>> J'ai un souci dans un pb :
>>
>> on me donne deux nombres premiers entre eux (pgcd=1).
>> C'est une histoire de timbres, mais cela revient à trouver le plus
>> grand nombre qui ne peut pas etre combinaison linéaire des deux
>> nombres premiers entre uex.
>>
>> Pour cela on prend l'exemple de 3 et 10. Le plus grand nombre qui ne
>> peut pas etre "fabriqué" par des 3 et 10 est 17.
>> Pour le trouver j'ai cree un tableau excel de 10x10. Chaque ligne part
>> d'un multiple de 10 auquel j'ajoute 3 systematiquement. Et j'ai noirci
>> à partir de 30 et en dessous jusqu'a ce que je ne puisse plus trouver
>> de nombre dans mon tableau. Ca donne ici 17.
>>
>> On prend l'exemple de 13 et 17.
>> Mon tableau fait 17lignes par 17 colonnes.
>> Chaque ligne demarre par un multiple de 17 et va de 13 en 13.
>> J'ai commence a noircir mon tableau a partir de 221 (17*13)en
>> decroissant.
>> Le plus grand nombre introuve est donc 191.
>>
>> Maintenant ma question est comment trouver le plus grand nombre qui ne
>> sera pas une combinaison lineaire de x et y si pgcd(x;y)=1 et
>> pourquoi.
>>
>> Supposons que x soit plus grand que y et que x et y premiers entre
>> eux. Comment trouver n tel que n+1 = ax + by avec a et b appartenant a
>> N et n impossible a faire de cette maniere.
>> Je seche .....
>>
>> Merci de m'aider.
>> Arthur
>
>[/color]

[Anonyme]

en tout cas c'est ce qu'on me demande....
Arthur

[Anonyme]

Fab a écrit:
> Tout ceci est-il au programme de seconde ??
>

Absolument pas. Programme de TS (et encore, je suis pas sûr que ca ne
soit pas seulement en spé maths).

--
albert

[Anonyme]

On Tue, 28 Sep 2004 23:12:31 +0200, albert junior
wrote:

>
>Absolument pas. Programme de TS (et encore, je suis pas sûr que ca ne
>soit pas seulement en spé maths).

Tout à fait, ceci ne se fait que pour l'option maths en TS.

Je suis un mauvais prof de maths, je n'ai pas été aussi loin avec mes
secondes ...

[Anonyme]

Si a et b sont des entiers positifs et premiers entre eux, le nombre
relatif d peut s'écrire ax+by (avec x et y positifs ou nuls) si et
seulement si le nombre ab-a-b-d ne peut pas s'écrire ainsi.

En particulier, tout ab-a-b est le plus grand nombre qui ne peut pas
s'écrire sous cette forme, puisqu'évidemment 0 est le plus petit qui
peut s'écrire ainsi.

[Anonyme]

On Tue, 28 Sep 2004 20:19:24 GMT, .@. (Arthur) wrote:

>J'ai un souci dans un pb :
>
>on me donne deux nombres premiers entre eux (pgcd=1).
>C'est une histoire de timbres, mais cela revient à trouver le plus
>grand nombre qui ne peut pas etre combinaison linéaire des deux
>nombres premiers entre uex.
>
>Pour cela on prend l'exemple de 3 et 10. Le plus grand nombre qui ne
>peut pas etre "fabriqué" par des 3 et 10 est 17.
>Pour le trouver j'ai cree un tableau excel de 10x10. Chaque ligne part
>d'un multiple de 10 auquel j'ajoute 3 systematiquement. Et j'ai noirci
>à partir de 30 et en dessous jusqu'a ce que je ne puisse plus trouver
>de nombre dans mon tableau. Ca donne ici 17.
>
>On prend l'exemple de 13 et 17.
>Mon tableau fait 17lignes par 17 colonnes.
>Chaque ligne demarre par un multiple de 17 et va de 13 en 13.
>J'ai commence a noircir mon tableau a partir de 221 (17*13)en
>decroissant.
>Le plus grand nombre introuve est donc 191.
>
>Maintenant ma question est comment trouver le plus grand nombre qui ne
>sera pas une combinaison lineaire de x et y si pgcd(x;y)=1 et
>pourquoi.
>
>Supposons que x soit plus grand que y et que x et y premiers entre
>eux. Comment trouver n tel que n+1 = ax + by avec a et b appartenant a
>N et n impossible a faire de cette maniere.
>Je seche .....
on te demande vraiment une formule et une preuve pour a et b qq (1er
entre eux) ?

s'il s'agit que d'un exemple numérique
par ex a=3 b=10 on peut justifier (sans excel )que c'est n=17
17 ne marche pas est facile à vérifier
car 3x+10y=17
exige soit y=0 qui conduit à x=17/3 donc..
soit y=1 qui conduit à x=7/3 donc...
mais 18=3*6+10*0
19=3*3+10*1
20=0*3+10*2

et on remarque que si on a
3x+10y=k avec x et y entiers >=0
alors 3(x+1)+10y=k+3 et x+1>=0
donc si ca marche pour k ca marche pour k+3
donc ca va marcher pour
18+3=21 19+3=22 20+3=23
"etc" ( osé en seconde !!!)
donc ca marhce pour tout nb >=18
donc 17 est bien le plus grand pour lequel ce n'est pas possible
comme l'a dit Xavier Caruso ce 17=ab-a-b=3*10-3-10

Rem :
il est assez "facile" de justifier que ab-a-b ne marche jamais
(pour a>=2 b>=2 cependant : si a=1 ou b=1 tous les n ,dans N,
marchent)
mais que tout nb >=ab-a-b+1=(a-1)(b-1) marche , est plus difficile
( peut se faire à partir de la sol générale de ax+by=c)
mais c'est d'un niveau vraiment supérieur à seconde
et même on connaît le nb de n pour lesquels ca ne marche pas :
il y en a (a-1)(b-1)/2 ( Th de Sylvester je crois)

*****************

Pichereau Alain

adresse mail antispam
http://perso.wanadoo.fr/alain.pichereau/
( olympiades mathématiques 1ère S )

*****************