Exercice CRPE

[minidiane]

Bonsoir, j'essaye de faire un exercice qui normalement est facile mais je n'y arrive pas du tout ce soir...

"Quel est le plus petit nombre entier qui a à la fois :
pour reste 4 dans la division euclidienne par 5,
pour reste 3 dans la division euclidienne par 4,
pour reste 2 dans la division euclidienne par 3,
pour reste 1 dans la division euclidienne par 2?"

J'essaye de le résoudre à l'aide des congruences mais je ne vois pas bien comment procéder :mur:

[Luc]

Bonsoir,

pas évident cet exercice! J'ai du regarder wikipedia pour trouver la solution :we:
Déjà, tu peux remarquer que si un nombre a pour reste 3 dans la division euclidienne par 4, alors forcement il est impair, donc il a pour reste 1 dans la division euclidienne par 2. Donc on peut enlever la dernière ligne sans perte de généralité.
L'avantage, c'est qu'il nous reste juste des congruences modulo 3,4 et 5, et que ces trois entiers sont premiers entre eux.
Si on considère le produit 3*4*5=60, on remarque que si n est solution, alors n+60 est aussi solution, ainsi que n+60+60, etc.
Le fait que n soit solution ne dépend donc que de n modulo 60.
Après, on peut utiliser de l’arithmétique (relation de Bézout) pour trouver la solution, sinon on essaye tous les entiers de 1 a 60 et on trouve la solution.

EDIT : il y a des astuces pour utiliser Bézout sans toute la théorie, pour trouver une solution particulière sans tester tous les entiers. L’idée est de remarquer que si tu trouves trois entiers, chacun respectant une congruence de l’énoncé et étant congru a 0 modulo les autres entiers, tu peux faire la somme de ces trois entiers et trouver une solution particulière a ce système de congruences. Par exemple, 20 est congru a 2 modulo 3, et a 0 modulo 4 et modulo 5. Je te laisse trouver les deux autres entiers, et faire leur somme pour trouver une solution (qui sera la plus petite si elle est plus petite que 60).

[minidiane]

J'ai trouvé mais pourrais tu me rappeler le théorème de Bézout car je ne m'en souviens plus.
J'ai trouvé en cherchant donc un nombre congru à 3 modulo 4 et à 0 modulo 3et 5. J'ai trouvé 15.
Ensuite j'ai cherché un nombre congru à 4 modulo 5 et à 0 modulo 3 et 4, j'ai trouvé 24.
Donc au finale ça donne: 20+15+24=59.

[Luc]

J'ai trouvé mais pourrais tu me rappeler le théorème de Bézout car je ne m'en souviens plus.
J'ai trouvé en cherchant donc un nombre congru à 3 modulo 4 et à 0 modulo 3et 5. J'ai trouvé 15.
Ensuite j'ai cherché un nombre congru à 4 modulo 5 et à 0 modulo 3 et 4, j'ai trouvé 24.
Donc au finale ça donne: 20+15+24=59.

L’idée d'utiliser Bézout, c'est pour trouver des "solutions élémentaires" des congruences, qui valent 1 pour une certaine congruence et 0 pour toutes les autres.

Bézout te dit que si deux entiers a et b sont premiers entre eux (ça veut dire que leur pgcd vaut 1), on peut trouver des entiers relatifs u et v tels que au+bv=1.

En prenant pour a et b 3 et 60/3=20, on obtient que 3u+20v=1, qui marche par exemple avec u=-13 et v=2. Modulo 3, 20*2=1. 40 est donc solution élémentaire pour le modulo 3.
Pour récupérer une solution du système entier N a partir des solutions élémentaires N2,N3,N5, on écrit ici N=N2+2N3+4N5

[minidiane]

J'ai du mal à comprendre cette partie

20*2=1. 40 est donc solution élémentaire pour le modulo 3.
Pour récupérer une solution du système entier N a partir des solutions élémentaires N2,N3,N5, on écrit ici N=N2+2N3+4N5

[Luc]

J'ai du mal à comprendre cette partie

20*2=1. 40 est donc solution élémentaire pour le modulo 3.
Pour récupérer une solution du système entier N a partir des solutions élémentaires N2,N3,N5, on écrit ici N=N2+2N3+4N5

Je n'ai pas très bien expliqué

On trouve une solution élémentaire pour le modulo 3 : 40=N3
De même, on trouve une solution élémentaire pour le modulo 2 : 1*15=1 (modulo 2) : 15=N2
De même, on trouve une solution élémentaire pour le modulo 5 : 3*12=1 (modulo 5) : 36=N5

Donc N=15+2*40+4*36=15+80+144=239 est solution particulière.
Donc la plus petite solution est 239-3*60=59.

[minidiane]

J'ai encore un peu du mal à comprendre.
Comment on trouve 15 et 12 pour N2 et N3, je n'arrive pas à les trouver.
Pourquoi on n'a pas N4?

[Luc]

J'ai encore un peu du mal à comprendre.
Comment on trouve 15 et 12 pour N2 et N3, je n'arrive pas à les trouver.
Pourquoi on n'a pas N4?

Effectivement, j'ai fait une erreur, 15 correspond à N4, solution élémentaire de la congruence modulo 4.
N3 est bien une solution élémentaire de la congruence modulo 3.
Le principe pour trouver une solution élémentaire de la congruence modulo 3 est de trouver une relation de Bézout entre 3 et ppcm(3,4,5)/3=60/3=20; pour la congruence modulo 4 c'est une relation de Bézout entre 4 et ppcm(3,4,5)/4=15; pour la congruence modulo 5 c'est une relation de Bézout entre 5 et ppcm(3,4,5)/5=12.

[minidiane]

ok je comprend mieux déjà, maintenant par contre je ne trouve pas N.
Si j'ai bien compris N=N2+2N3+3N4+4N5 mais je n'arrive toujours pas à le calculer correctement.

[Luc]

ok je comprend mieux déjà, maintenant par contre je ne trouve pas N.
Si j'ai bien compris N=N2+2N3+3N4+4N5 mais je n'arrive toujours pas à le calculer correctement.

En fait il faut considérer N=2N3+N4+4N5, car 2 n'étant pas premier avec 4, il fait tout planter. (La méthode des solutions élémentaires est généralisable à des entiers non premiers entre eux, mais c'est plus compliqué).
De toutes façons, on a remarqué que la congruence modulo 2 est entrainée par la congruence modulo 4. Donc le système de congruences initial est équivalence au système de congruences obtenu en enlevant la congruence modulo 2. Ensuite, si tu arrives a calculer N3, N4 et N5 séparément, tu devrais à calculer N. Quel est le nombre que tu n'arrives pas à calculer?

[minidiane]

Le N5 je trouve 24 et pas 36, je ne vois pas où est mon erreur.
J'ai fais 5u+12v=1 et j'ai trouvé u=-5 et v=2 d'où N5=24

[Luc]

Le N5 je trouve 24 et pas 36, je ne vois pas où est mon erreur.
J'ai fais 5u+12v=1 et j'ai trouvé u=-5 et v=2 d'où N5=24

Attention, -25+24 est égal à -1, pas à 1.

[minidiane]

Ah oui mince, ok donc c'est bon j'ai trouvé.
Après je ne me souviens plus pourquoi on fait N-3*60 et pas autre chose

[minidiane]

Est ce que c'est parce qu'on à trois solutions élémentaires?

[Luc]

Est ce que c'est parce qu'on à trois solutions élémentaires?

Non c'est parce qu'on nous demande la plus petite solution, et que connaissant une solution particulière, toutes les solutions s'en déduisent en ajoutant ou soustrayant un multiple de 60. Donc ici on enlève 3*60 à la solution particulière parce qu'on ne peut pas enlever 4*60.

[minidiane]

ah ok merci