Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Congruencs

Posté par
cyrius
24-06-08 à 18:57

Bonjour, je n'arrive pas à résoudre cette équation ( je ne comprends pas le raisonnement en fait)

5x 7[16]

D'aprés Bezout, pgcd(5,7)=1
Donc 5x + 16y = 1

Et pour résoudre ça ?

Merci votre aide.

Posté par
disdrometre
re : Congruencs 24-06-08 à 19:13

salut

5x = 7 [16]
donc on peut écrire :

5x = 7 + 16k

comme on veut résoudre dans Z

alors  il faut que x soit dans Z

soit encore  (7+16k)/5  est un entier relatif


puisque 16k =15k +k

donc il faut (7+ k)/5  est entier de Z

si  k est de la forme 5q -7 avec q élément de Z

..

Posté par
raymond Correcteur
Congruences 24-06-08 à 19:19

Bonsoir.

5x 7 [16]

5x = 7 + 16k

5x - 16k = 7

On cherche une solution particulière, par exemple x = - 5 et k = - 2.

Donc 5(-5) - 16(-2) = 5x - 16k

On en déduit que :

5(x+5) = 16(k+2)

5 divise 16(k+2) et 5 est premier avec 16, donc 5 divise k+2.
Ainsi k+2 = 5.a

16 divise 5(x+5) et 16 premier avec 5, donc 16 divise x+5.
Ainsi x+5 = 16.b

En reportant, on trouve que a = b.

Conclusion : x = 16a - 5, a quelconque dans

Posté par
Pece
re : Congruencs 24-06-08 à 19:20

Méthode de résolution de Gauss, ça te dit qqch ?

Mais il y a plus simple. Tu dresses la table de congruence de 5x modulo 16 tout simplement

Posté par
lyonnais
re : Congruencs 24-06-08 à 19:25

Bonjour

Disdrometre t'a donné une méthode tout a fait juste.

Une légère variante consiste à considérer :

5x + 16y = 7

16 = 5.3 + 1   d'où  1 = 5.(-3) + 16.(1)

Et donc en multipliant le tout par 7 tu trouves que (-21,7) est solution de l'équation.

Donc en particulier comme 5.(-21) + 16.(7) = 7

5x + 16y = 5.(-21) + 16.(7)

d'où :

5(x+21) = 16.(7-y)

Ainsi 16|5(x+21)  or pgcd(16,5) = 1  donc par le théorème de Gauss,

16|(x+21)  et  donc  

Il existe k dans Z tq x = -21 + 16k = 11 + 16k'

A vérifier et Sauf erreurs

Posté par
lyonnais
re : Congruencs 24-06-08 à 19:27

Bonsoir Raymond

On est d'accord

Posté par
cyrius
re : Congruencs 24-06-08 à 19:50

ok merci à tous ! je bosse ça

Posté par
raymond Correcteur
re : Congruences 24-06-08 à 21:03

Bonsoir lyonnais.

A plus. RR.

Posté par
cyrius
re : Congruencs 25-06-08 à 00:51

Bonsoir, en fait je ne comprends pas le passage entre


16|5(x+21)  or pgcd(16,5) = 1  donc 16|(x+21)  

et  

Il existe k dans Z tq x = -21 + 16k = 11 + 16k'

Si vous pouviez le développer un petit peu plus ....
Merci !

Posté par
lyonnais
re : Congruencs 25-06-08 à 09:03

Bonjour

C'est un théorème. Déjà | veut dire "divise".

Regarde ici si tu veux plus d'informations :

Dis nous si tu as compris

Posté par
cyrius
re : Congruencs 25-06-08 à 10:29

Merci, je savais ce que voulais dire |
Le problème c'est le k et k'

Posté par
lyonnais
re : Congruencs 25-06-08 à 10:44

Ah dans ce cas, il n'y a pas de problème.

D'après mon développement, la réponse est :

x = -21 + 16k  avec k dans Z

Mais si tu poses par exemple k = k'+1, tu as toujours k' dans Z et alors :

x = -5 + 16k'  (solution de Raymond)

Et si tu poses k = k''+2, tu obtiens :

x = 11 + 16k''

C'était juste pour faire plus joli

En gros, pour faire simple, tu réponds

x 11 [16]

A bientôt

Posté par
cyrius
re : Congruencs 25-06-08 à 10:53

ok je crois avoir compris. Merci

Posté par
cyrius
re : Congruencs 25-06-08 à 11:05

Bon j'ai réessayé une autre équation, mais toujours bloqué au même point:

(E1):  6x8[16]

6x + 16y = 8
3x+8y=4

D'aprés boezout et pgcd=1 :

3x' + 8y' = 1

Solution particuliére; 3,-1

Donc
3x+8y=3(12)+16(-4)

Donc 3 | y+4  &  8 | x-12

Et .... ?

Posté par
cyrius
re : Congruencs 25-06-08 à 11:11

Alors ne fait je trouverai :  x = 12[16] comme solution générale
soit x = 12 + 16k avec k Z

Est ce ca ?

Posté par
Camélia Correcteur
re : Congruencs 25-06-08 à 14:30

Bonjour

Tu n'as pas toutes les solutions: 4+16k convient aussi

Posté par
lyonnais
re : Congruencs 25-06-08 à 15:58

Bonjour

Il faut garder l'équation de départ ...

3x - 8y = 4   (*)

8 = 3.(2) + 2
3 = 2.(1) + 1

d'où

1 = 3-2.(1) = 3-(1).(8-3.2) = 3.(3)-8.(1)

Une solution particulière de (*) est donc : (12,4)

3x - 8y = 3.(12) - 8.(4)

3(x-12) = 8(y-4)

8|3(x-12)  pgcd(8,3) = 1  donc il existe k tq : x = 12+8k

ie  x 4 [8]

Posté par
lafol Moderateur
re : Congruencs 27-06-08 à 00:39

Bonsoir
petite variante pour la première : 5 étant premier avec 16 est inversible modulo 16, et comme 5*(-3) = -15 = -16 + 1, son inverse est -3

donc 5x \eq 7[16] <==> x\eq 7*(-3) [16] ou encore x \eq -5 [16] ou encore x \eq 11 [16]

Posté par
lyonnais
re : Congruencs 01-07-08 à 14:40

Bonjour lafol >

En fait, on se place sans le dire dans Z/16Z. On a :

5x = 7 dans Z/16Z

On cherche l'inverse de 5. Pour cela,

16 = 3.5 + 1 donc  1 = 16 + 5.(-3)

Donc l'inverse de 5 est -3 dans Z/16Z et alors :

5x = 7 donne x = 7.(-3) = -21 = -5 dans Z/16Z d'où le résultat.

( En gros, j'ai réécris ce que tu as écris plus haut )

A bientôt

Posté par
lafol Moderateur
re : Congruencs 01-07-08 à 22:12

en gros, oui

les Z/nZ à mon époque, on les fréquentait déjà au collège, avec de petites valeurs de n. les réflexes restent .....



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 1674 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 !