Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Algorithme d euclide

Posté par
rycker
21-01-16 à 17:28

Salut les amis aidez moi on a
(E): 7x-11y=2
On me demande d utiliser  l algorithme d Euclide pour trouver une solution particulière

Posté par
mathafou Moderateur
re : Algorithme d euclide 21-01-16 à 17:40

Bonjour,
tu ne connais pas l'algorithme d'Euclide (celui pour trouver le PGCD) ?

en "remontant" cet algorithme à partir du dernier reste (= le PGCD = 1) et en faisant les calculs "à l'envers"
(en écrivant que a = bq + r donne r = a - bq) on obtient les valeurs numériques de a et b avec
1 = 7a + 11b (ne pas développer outre mesure les produits !! sous peine d'obtenir le peu intéressant 1 = 1)

en multipliant les deux membres de cette égalité par 2 on obtient ce qu'on cherche.

il existe aussi une variante qui fait les calculs "en marche avant" (au fur et à mesure sans attendre la fin pour remonter) mais elle est un peu plus compliquée à comprendre et expliquer. quoique ...

Posté par
rycker
re : Algorithme d euclide 21-01-16 à 18:02

Merci j'ai trouver
et si on a 14x-22y=4
et on me demande que cette équation admet au moins une solution comment dois faire?

Posté par
mathafou Moderateur
re : Algorithme d euclide 21-01-16 à 18:07

j'espère que tu vois/sais bien que diviser les deux membres d'une égalité par 2 donne une égalité équivalente

et donc que si cette égalité est une équation, ça donne une équation équivalente ...
qui a donc exactement les mêmes solutions que l'équation de départ

Posté par
rycker
re : Algorithme d euclide 21-01-16 à 18:27

Oui oui mais ici on me demande de démontré que l'équation admet au moins une solution

Posté par
mathafou Moderateur
re : Algorithme d euclide 21-01-16 à 18:32

si une équation E admet une solution
et une équation E' est équivalente à E, alors E' admet une solution ....
et vice versa et pareil si elles n'admettent pas de solution

E admet une solution si et seulement si E' admet une solution

tu comprends ce que veut dire des équations sont équivalentes ??

Posté par
rycker
re : Algorithme d euclide 21-01-16 à 18:36

Oui oui
Merci pour ton aide j'ai une dernière question  on me demande de déterminé tout les éléments (a;b) appartenant a N x N qui vérifie 7ppcm(a;b)-11pgcd(a;b) =3
avec PPCM  (a;b) = T et PGCD (a;b) = Y

Posté par
mathafou Moderateur
re : Algorithme d euclide 21-01-16 à 19:28

déja tu peux chercher les solutions de 7T - 11Y = 3
c'est quasiment déja fait : tu as "immédiatement" une solution particulière dans Z×Z (questions d'avant)
il reste à trouver les solutions générales.

puis une fois toutes les solutions dans Z×Z obtenues il n'est pas difficile de restreindre et trouver toutes les solutions dans N×N

et pour chacune de ces solutions {Y, T} là (il n'y en a pas tant que ça) tu résous le système en les inconnues a et b
PGCD(a, b) = Y
PPCM(a, b) = T

ça se résout en écrivant que a = Yu et b = Yv avec u et v premiers entre eux
et donc PPCM = Yuv, et la décomposition de T en produits de facteurs donne les solutions.

Posté par
rycker
re : Algorithme d euclide 21-01-16 à 20:20

Je comprends toujours pas car je trouve des solutions  négatives

Posté par
mathafou Moderateur
re : Algorithme d euclide 21-01-16 à 20:44

les solutions de quoi ? en a et b ? ou en T et Y ?

par contre avec l'équation proposée, le plan que je proposais est "un peu foireux" (l'énoncé est conçu pour envoyer dans cette impasse, en faisant résoudre des équations diophantiennes avant)
ça reviendrait à recenser tous les diviseurs de 2+11k pour tout entier k dans N !!! tâche sans fin

désolé pour t'avoir embarqué là dedans.

une autre approche est de remarquer que le PPCM est forcément un multiple du PGCD
et donc 7T - 11Y est un multiple de ce PGCD, en d'autres termes le PGCD divise 7T - 11Y

or comme c'est égal à 3, ça veut dire que ce PGCD (qui divise donc 3) est forcément 1 ou 3

ça va limiter pas mal !!! de savoir que T = 1 ou 3 et c'est tout !
surtout si ni 7 - 11Y = 3, ni 21 - 11Y = 3 n'ont de solution pour Y entier !
et donc cette approche est la bonne.

Posté par
mathafou Moderateur
re : Algorithme d euclide 21-01-16 à 20:48

oups. j'ai inversé le PGCD et le PPCM dans mon équation, ça ne change pas grand chose à la méthode.
à la conclusion, si ...
vu qu'il s'agit de résoudre
7T - 11 = 3 et 7T - 33 = 3



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !