[Spé TS] - Equations de Diophante

[invitea1b49bb7]

Bonjour à tous !!!

Bon dans mes révisions de vacances pr le BAC je suis tombé sur un exo qui est sans doute relativement simple mais je bloque sur une question. En fait je ne dois pas être très loin mais il manque qqch (je pense). Alors je vais d'abord mettre l'énoncé en gras, pr que vous voyiez l'esprit de l'exercice, puis les réponses que j'ai trouvées. En bref je voudrais une piste de réflexion (voire même un ersatz de solution lol) pour la question 1.b

On considère : 109x - 226y = 1 (E)
1 /

a) calculer pgcd(109, 226)

b) Montrer que l'ensemble des solutions de (E) est l'ensemble des couples de la forme (141+226k,68+109k), k est un entier relatif
En déduire qu'il existe un unique entier naturel non nul d inférieur ou égal à 226 et un unique entier naturel non nul e tq : 109d = 1+226 (on précisera les valeurs de d et de e)

2/ démontre que 227 est premier

3/ On note A l'ensemble des 227 entiers naturels "a" tq a<= 226
On considère f et g de A dans A tq
à tout a , f associe le reste de la div. eucl. de a¹⁰⁹ par 227.
à tout a , g associe le reste de la div. eucl. de a¹⁴¹ par 227.

a) vérifier que gof(0) = 0
- rappel du petit théorème de fermat (si p est premier et a un entier non divisible par p alors a^p-1 est congru à 1 modulo p.)

b) Montrer que pour tout a non nul de A a²²⁶ est congru à 1 modulo 227

c) en utilisant la 1-b) en déduire que, quel que soit l'entier non nul a de A, gof(a)=a
Que peut-on dire de f(g(a))=a ?


Voilà. Donc voici ce que j'ai trouvé :


1-a) pgcd = 1

b) là je bloque

j'ai fait une dicision euclidienne successive:
-226=-2x109 - 8
109 = -8x-13 + 5
613 = 5x-2 - 3
-2 = -3 x 0 - 2 (ou sinon p-etre = 1x-3 + 1 je sais pas)

ensuite j'ai esayé de remonter en prenant a=109 et b=-226 mais au final, en recombinant les égalités (du style :
-8 = -226 + 2x109
<=> -8 = b + 2a
je trouve alors : 10 = 54a + 26b

comment faire pour retomber sur une égalité du type :

1= xa + yb ???

et aussi je veux bien enxuite une piste pr la deuxieme partie de la question ; je ne vois pas exactement comme on montre ça.

2) test de primalité (avec racine carrée) ça pas de problème

3) a) c bon ca se vérifie en une seconde 0^141 = 0

b) ave cfermat c'est facile => a <= 226 => p ne divisa pas a car p=227 > a

=> a²²⁶ congru à 1 modulo 227

c) bah là je trouve pas puisque j'ai pas la 1-b) je veux bien une piste de réflexion pour cette question parce que je vois pas trop trop comment je pourrais faire, meme avec la 1-b


Merci (beaucoup) d'avance, parce que je n'aime pas rester sur un exo que j'ai pas trouvé. Merci !!!
-----

[invite78bdfa83]

j'ai fait une dicision euclidienne successive:
-226=-2x109 - 8
109 = -8x-13 + 5
613 = 5x-2 - 3
-2 = -3 x 0 - 2 (ou sinon p-etre = 1x-3 + 1 je sais pas)

c'est la que tu t'es trompé, il faut faire attention quand tu fait la division euclidienne a bien identifier a, b, q et r ( dans l'expression a=b*q+3)
Tou d'abord c'est 13 et non 613, et puis ensuite regarde 13 et 8 .. lequel prendre pour la division suivante ??
Normalement tu devrais arriver a trouver a solution ...(tu trouve pour la derniere division euclidienne a=b*q + 1 et il te suffit alors de "remonter"

Cordialement

[invite78bdfa83]

un autre petit conseil... fait toujours tes divisions euclidiennes dans N c'est plus facile, et plus visuel

[invitea1b49bb7]

dajety >> oui c'est 13 je me suis trompé en tapant le texte. Sinon merci beaucoup justement j'essayais d'arriver à a=b*q + 1.. mais dans l'absolu je choisis comment le nombre que je divise... ???
Merci kan même !!!!

re-dajety >> j'avais peur de me gourer dans les signes en remontant, je sais pas si c'était pareil. thanks.

[A voir en vidéo sur Futura]

[invite78bdfa83]

on va mettre des indices c'est un peu plus parlant...:
cela s'apelle l'algorithme d'euclide a propos...
Tu prend deux nombres a et b
on suppose par exemple a>b
on fait a=b*q1+r1 ( division euclidienne)
ensuite si r1 est non nul on réitere le procédé comme ceci :
b=r1*q2+r2
c'est possible car r1<b et puis tu continues juqua ce que le reste soit nul et en fait le dernier reste non nul te donne le pgcd des deux nombres de départ..
regarde le lien : c'est mieux expliqué que moi..
http://forums.futura-sciences.com/ne...reply&t=129072

[invitea1b49bb7]

((ah oui oki dsl))

bon alors je trouve bien le résultat demandé pr l'exercice, mais la suite (suite du 1.b + dernière question) reste relativement obscure.

Merci d'éclairer ma lanterne lol

[invitea1b49bb7]

Slt !

=> et surtout comment prouver qu'il existe un entier UNIQUE ??? (1.b partie 2)