Forum de mathématiques - Bibm@th.net

marioss

Membre

Inscription : 17-02-2014

Messages : 69

problème à résoudre

salut tout le monde ,

j'ai un problème dans cette exercice . j'ai essayé à mettre x à la puissance " a " mais a appartient à Z. voilà l'exercice :

sachant que :  13a-16b=1 tel que a et b appartenant à Z  et
on a : [tex] x^{13}\equiv 1\;[17][/tex] montrer que : [tex]x\equiv 1\;[17][/tex]

Dernière modification par marioss (28-05-2014 14:56:14)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : problème à résoudre

Salut,

es-tu sûr de l'énoncé de ton sujet ?

marioss

Membre

Inscription : 17-02-2014

Messages : 69

Re : problème à résoudre

salut,

1) montrer que l'équation 13x-16y=1 accepte au moins une solution (a,b) dans Z.

2) on a : [tex] x^{13}\equiv 1\;[17][/tex]  et pgcd(17;x)=1 .

montrer que : [tex]x\equiv 1\;[17][/tex]

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : problème à résoudre

Bonjour,

Ah, marioss, que de manque de rigueur,

salut tout le monde ,
j'ai un problème dans cette exercice . j'ai essayé à mettre x à la puissance " a " mais a appartient à Z. voilà l'exercice :

sachant que :  13a-16b=1 tel que a et b appartenant à Z  et
on a : [tex] x^{13}\equiv 1\;[17][/tex] montrer que : [tex]x\equiv 1\;[17][/tex]

salut,
1) montrer que l'équation 13x-16y=1 accepte au moins une solution (a,b) dans Z.
2) on a : [tex] x^{13}\equiv 1\;[17][/tex]  et pgcd(17;x)=1 .
montrer que : [tex]x\equiv 1\;[17][/tex]

Si tu veux être aidé, il faut que tu dises au moins quelle partie de tes cours, quels théorèmes, peuvent bien convenir pour traiter les 2 questions…(qui apparaissent bien indépendantes...)
Alors seulement on pourra te corriger et t'orienter éventuellement !!!

A+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : problème à résoudre

Salut,

Je ne crois pas qu'il y ait de rapport entre les deux questions...
J'ai pensé au petit théorème de Fermat [tex]x^n\equiv x\;[n][/tex] ici donc [tex]x^{17}\equiv x \; [17][/tex]
et à son corollaire puisque PGCD(x;17)=1 : [tex]x^{16}\equiv 1\;[17][/tex]
Et donc en écrivant [tex]x^{16}=x^{13}\times x^3[/tex] :
on obtient :
[tex]x^{13}\times x^3 \equiv 1\;[17][/tex]
Or, on sait que :
[tex]x^{13}\equiv 1\;[17][/tex]
Donc [tex]x^3 \equiv 1\;[17][/tex]

Je suis arrivé là, mais je n'ai plus le temps de poursuivre pour voir où cela me mène... proprement.

@+

[EDIT]
Tiens, totomm pense aussi que 1 et 2. sont indépendantes...

Dernière modification par yoshi (28-05-2014 16:05:28)

marioss

Membre

Inscription : 17-02-2014

Messages : 69

Re : problème à résoudre

merci yoshi,

je pense que je peux completer maintenant:

Or : x¹³=(x³)⁴.x         implique     x¹³=x.(x³)⁴(mod17)

D'où : x=1(mod17)

Dernière modification par marioss (28-05-2014 16:46:10)

marioss

Membre

Inscription : 17-02-2014

Messages : 69

Re : problème à résoudre

le problème c'est l'exercice semble qu'il faut utiliser l'équation.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : problème à résoudre

RE,

J'avais trouvé dans ma voiture...
Tu as trouvé seul, c'est bien !

le problème c'est l'exercice semble qu'il faut utiliser l'équation.

Alors, c'est que, une fois encore, ton énoncé n'est pas complet ! Dans ce cas, veux-tu bien le recopier intégralement, et à la virgule près ? Merci !
Mais cela m'étonne : s'il y a bien 13, on y trouve 16 (et non 17). Et moi, je n'ai pensé à 16 qu'avec le corollaire du Petit théorème de Fermat...
Or, si on utilise ce corollaire, la question 1 ne sert à rien.
La question 1, c'est Bezout...

Cela ferait deux fois dans cet exercice que l'énoncé est incomplet : 1 fois par exercice, c'est déjà beaucoup, mais là, tu exagérerais vraiment !

Il manquait d'abord PGCD(x,17) = 1.
C'est cette info qui m'a donné la marche à suivre...
J'étais parti avant cela sur :
[tex]x^{13} \equiv 1\; [17] \Rightarrow \left(x^{13}\right)^{17} \equiv 1\; [17]\Leftrightarrow \left(x^{17}\right)^{13} \equiv 1\; [17] [/tex]
Mais je n'ai pas réussi à aboutir...

@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : problème à résoudre

RE,

Une solution de la question 1 - que je n'avais pas cherchée jusqu'à maintenant - est :
(x;y)=(21;17)
13*21 - 16*17 = 273 - 272 = 1
Et je ne vois toujours pas le rapport entre les deux questions.

@+

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : problème à résoudre

Salut,

  Pour la question 1, si on te demande de dire : il existe a et b, je me contenterai de la réponse : "13 et 16 sont premiers entre eux donc par le théorème de Bezout, il existe a et b tels que ....".

Qu'il n'y ait pas de lien entre la question 1 et la question 2. ne me choque pas forcément. Après tout, ce n'est pas écrit "En déduire...".

Fred.

marioss

Membre

Inscription : 17-02-2014

Messages : 69

Re : problème à résoudre

je vois.

merci à tous

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : problème à résoudre

Bonjour,

S'il faut trouver explicitement x et y tel que 13x-16y = 1, on peut "deviner" le couple (5,4) à défaut d'exécuter "à la main" l'algorithme d'Euclide étendu dont il est douteux qu'il soit au programme du bac…

Pour montrer que : [tex]x\equiv 1\;[17][/tex] quand on a [tex] x^{13}\equiv 1\;[17][/tex]
Je mettrais [tex]x[/tex] sous la forme [tex]x=(17k+r)\  avec\  0\leq r<17[/tex]
Alors, en développant [tex](17k+r)^n[/tex] on montre que  [tex](x^n)[17] = r^n[17][/tex]
Et pour n=13, il n'y a que r=1 qui permette [tex]r^{13}\equiv 1[17][/tex] (ce n'est pas la cas pour n=12 ou n=14 par exemple)
Là encore je doute que ce soit demandé au bac...

A+ éventuellement

Un_ignorant

Invité

Re : problème à résoudre

Hum, si x^13 congru à 1 modulo 17,
n'a-t-on pas forcément x et 17 premiers entre eux?

Puisque 17 premier et pgcd(x,17)|17, ce pgcd vaut soit 1 soit 17 or s'il vaut 17, 17 divise x donc divise x^13 congru à 1 modulo 17 absurde!

L'énoncé est donc tout à fait complet.

Quand au lien avec la question a), je vois avec 17, si 13u+17v=1, en passant dans Z/17Z (soit s'autorisant à diviser dans les congruences, car corps), en mettant à la puissance u, on obtient bien le résultat, mais ça n'est pas en effet au programme du bac.

@Totomm: mais "si a congru à b, c congru à d, alors ac congru à bd" est au programme du bac, et "si n entier, si x congru à y, alors x^n congu à y^n" l'est aussi, donc ta démo est au programme,
même si la fin (vérification pour chaque entier entre 2 et 16) est un peu fastidieuse.

(Pour une démo vraiment HP mais immédiate, en revanche, le théorème de Lagrange nous assure que l'ordre de tout élément divise l'ordre du groupe, donc l'ordre de x divise 13 et 17, donc leur pgcd qui est 1:youpi)

Un_ignorant

Invité

Re : problème à résoudre

Je faisais la remarque sur la mise à la puissance (et sur Z/17Z) car c'était l'idée de Marioss, qui fonctionne. Malheureusement, la raison pour laquelle mettre à une puissance de Z n'est pas absurde est hors-programme.