Congruences TS-Spé Maths

[Poubellion]

Bonjour,

j'étudie actuellement les congruences en spé maths, et je bloque complètement sur un exercice.

En utilisant le théorème des restes chinois, je dois résoudre le système

n 3 [27]
n 2 [23]

Edit : je vais quand même vous rappeler le théorème des restes chinois :
« Soit m et n, deux entiers naturels premiers entre eux.
x a [n] et x b [m] x avn + bum [[I]mn] où u et v sont deux entiers relatifs satisfaisant l'identité de Bézout mu + nv[/I] = 1. »

Merci beaucoup de votre aide !
x

[Luc]

Salut,

déjà pour respecter les notations du théorème, je te conseille de remplacer n par x. Ensuite, pour se mettre dans les conditions du théorème, que dois-tu choisir pour n et m? Sont-ils premiers entre eux?
Peux tu trouver une relation de Bézout entre ces deux entiers?

[Poubellion]

Ah vrai dire, j'ai avancé jusqu'à là :

x ;) (27x3xV + 23x2xU) [27x23]
x ;) 81v + 46u [621]

D'où l'identitdé de Bézout : 23u + 27v =1
Et là... je n'arrive pas à la résoudre.

J'ai bien essayé ainsi par exemple :
27 = 23x1 + 4
23 = 4x5 + 3
5 = 3x1 + 1
3 = 2x1 + 1
------------------
1 = 3-2
1 = 3-1*(5-3)
1 = 3-1*(5-1*(23-5*4))
1 = 3-1*(5-1*(23-5*(27-23*1)))
1 = 3-5+23-135+250
1 = 23u + 27v

Donc il faut que je trouve u et v, mais ça m'est impossible...
Si je les ai, je les remplace là-dedans :
x ;) 81v + 46u [621]
Et j'ai terminé l'exercice en fait...

x

[Luc]

Pour trouver u et v, il suffit d'appliquer l'algorithme d'Euclide à 23 et 27, pour obtenir le pgcd de 23 et 27 (qui vaut 1). Si tu ne connais pas l'algorithme d'Euclide, http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide#Description_de_l.27algorithme

On commence par : 27=1*23+4
23=5*4+3,
etc.

Les entiers u et v sont un sous-produit de cet algorithme.

[Poubellion]

C'est ce que j'ai fait il me semble...
Mais je suis coincé comme je l'ai dit plus haut... :/

27 = 1x23+4
23 = 5x4+3
5 = 1x3+2
1 = 2x... + ... ?

x

[Luc]

C'est ce que j'ai fait il me semble...
Mais je suis coincé comme je l'ai dit plus haut... :/

27 = 1x23+4
23 = 5x4+3
5 = 1x3+2
1 = 2x... + ... ?

x

Désolé, je n'avais pas vu.
Pour avoir u et v, on remonte les lignes de calculs de bas en haut en remplaçant à chaque fois le reste par les nombres plus gros. Par substitution successive, on a que du 23 et du 27 qui font 1. (c'est vague mais c'est difficile à expliquer sans un exemple).

[Poubellion]

1 = 3-2
1 = 3-1*(5-3)
1 = 3-1*(5-1*(23-5*4))
1 = 3-1*(5-1*(23-5*(27-23*1)))
1 = 3-5+23-135+250

Oui, comme ça quoi ?

x

[Luc]

1 = 3-2
1 = 3-1*(5-3)
1 = 3-1*(5-1*(23-5*4))
1 = 3-1*(5-1*(23-5*(27-23*1)))
1 = 3-5+23-135+250

Oui, comme ça quoi ?

x

Oui, mais il faut aussi remplacer le 3 de gauche et surtout ne pas calculer les multiplications (il faut laisser apparaître 23 et 27). Ce n'est pas très naturel mais on s'y fait.

[Poubellion]

Donc le 5 aussi ?

1 = (23 - 5 x (27 - 23)) - (5 - 1 x (23 - 5 x (27 - 23)))
Mais par quoi ? 3x1 +1 ?

x

[Luc]

Donc le 5 aussi ?

1 = (23 - 5 x (27 - 23)) - (5 - 1 x (23 - 5 x (27 - 23)))
Mais par quoi ? 3x1 +1 ?

x

Il y a une erreur dans l'algorithme, ce ne sont pas les bons restes.
Il faut procéder comme ceci :
27=1*23+4
23=5*4+3
4=1*3+1
3=3*1+0, on s'arrête.

Donc on remplace :
1 par 4-3
3 par 23-5*4
4 par 27-23

Et on a terminé.

[Poubellion]

1= 6 x 27 + -7 x 23

x ;) 486 + 322 [621]
x ;) 164 [621]

C'est ça il me semble ?

Merci !!!

x

[Luc]

Ça m'a l'air correct : tu peux vérifier que 164 est bien solution particulière.