Problème de congruance

a marqué ce sujet comme résolu.

Bonjour,

Je sais que :

12=1=296(5)32=2=296(7)122=11=296(19)1^2 = 1 = 296 (5) \\ 3^2 = 2 = 296 (7) \\ 12^2 = 11 = 296 (19)

Comment je peux en déduire une solution de x2=296(665)x^2 = 296 (665) ?

C’est une exercice d’un ancien examen dont je n’ai pas la solution.

PS: Je sais que 31 est la première solution (sinon la seule). En essayant à la main. Mais j’imagine que c’était pas ça qui est attendu.

+0 -0

Salut, Je suis pas très à l’aise avec les congruences.

Si je pose ton problème

x2=y(z)=296(z)x^2 = y(z) = 296(z)

Si je ne me trompe pas, on peut réécrire les congruences comme ça :

x2=αz+y296=γz+yx^2 = \alpha z + y\\ 296 = \gamma z + y

Si je soustrais, les deux équations j’obtiens

x2=(α−γ)z+296x^2 = (\alpha -\gamma)z +296

α\alpha et γ\gamma étant des constantes, peuvent se réécrire en une seule.

On doit donc juste résoudre l’équation

x2=zy+296x^2 = zy+296

avec zz fixé à 665

Donc il te reste à trouver les solutions entières d’une équation du second degré à 2 inconnues. Je sais pas trop comment faire mais Wolfram alpha à l’air d’y arriver (https://www.wolframalpha.com/input/?i=x%C2%B2+-+665y-296+%3D0+solution+enti%C3%A8re).

Il semble y avoir 8 solutions : 31,164,221,311,354,444,501,63431,164,221,311,354,444,501,634

En espérant avoir pu t’aider.

+0 -1

L’arithmétique ça se fait pas avec une calculatrice ;)

Comme l’énoncé te le suggère subtilement :

665=5×7×19665 = 5\times 7\times 19

Il s’agit donc d’appliquer correctement le théorème des restes chinois

Ce théorème dit que l’on a un isomorphisme

Z/665→Z/5×Z/7×Z/19\mathbf Z / 665 \to \mathbf Z/5 \times \mathbf Z/7 \times \mathbf Z/19

par la seule application raisonnable : x[665]x[665] est envoyé sur (x[5],x[7],x[19])(x[5],x[7],x[19]).

Maintenant, je cherche x2[665]=(12[5],32[7],122[19])x^2[665] = (1^2[5],3^2[7],12^2[19]). Cet isomorphisme est un isomorphisme d’anneaux, donc ça revient à chercher x[665]=(1[5],3[7],12[19])x[665]=(1[5],3[7],12[19]).

Comment déterminer xx ? On applique le petit algorithme du théorème des restes chinois.

  • On pose n5=7⋅19=133n_5 = 7\cdot 19 = 133, n7=5⋅19=95n_7=5\cdot 19=95 et n19=5⋅7=35n_{19}=5\cdot 7=35.
  • On résout une sorte de base pour chaque nombre premier : 2⋅n5−53⋅5=12\cdot n_5 - 53\cdot 5 = 1, 2⋅n7−27⋅7=12\cdot n_7 - 27\cdot 7=1 et enfin 6⋅n19−11⋅19=16\cdot n_{19} - 11\cdot 19=1. On pose avec ces résolutions e5=2⋅n5=266e_5 = 2\cdot n_5 = 266, e7=2⋅n7=190e_7 = 2\cdot n_7 = 190 et e19=6⋅n19=210e_{19} = 6\cdot n_{19} = 210.

La solution xx est alors donnée par

x=1⋅e5+3⋅e7+12⋅e19=266+570+2520=3356x = 1\cdot e_5 + 3\cdot e_7 + 12 \cdot e_{19} = 266 + 570 + 2520 = 3356

et 3356[665]=31[665]3356[665] = 31[665]. Ce qui te donne ta solution

+3 -0

Merci @Holosmos !

J’avais essayé l’algorithme des restes chinois mais je n’étais pas arrivé à un résultat concluant, je l’avais fais sur les carrés (1, 9, 144) plutôt que sur le 1, 3 et 12.

Du coup, je ne comprend pas :

Maintenant, je cherche x2[665]=(12[5],32[7],122[19])x^2[665] = (1^2[5],3^2[7],12^2[19]). Cet isomorphisme est un isomorphisme d’anneaux, donc ça revient à chercher x[665]=(1[5],3[7],12[19])x[665]=(1[5],3[7],12[19]).

Pourquoi ça revient à chercher x[665]=(1[5],3[7],12[19])x[665]=(1[5],3[7],12[19]) ?

Effectivement, j’ai refais l’algo (car j’ai pas compris ce que tu as fais en le lisant :honte: ) et je suis retombé sur le même résultat.

+0 -0

Ok !

Donc pour avoir le reste des solutions je n’ai cas prendre les antécédents de x2x^2, appliquer l’algorithme pour chacun et mis au carré ça j’obtiendrais 296.

12=(−1)2=1=296(5)32=(−3)2=2=296(7)122=(−12)2=11=296(19)1^2=(-1)^2=1=296(5) \\ 3^2=(-3)^2=2=296(7) \\ 12^2=(-12)^2=11=296(19)

Tout élément de {1,4}×{3,4}×{7,12}\{1,4\} \times \{3, 4\} \times \{7, 12\} me permet de retrouver une solution en appliquant l’algorithme des restes chinois. :D

Merci !

@Melcore, je ne t’ai pas répondu mais ton résultat se déduit simplement grâce à l’équation qu’on doit résoudre. x=296(655)  ⟺  x2=655y+296x = 296 (655) \iff x^2= 655y + 296.

Ce qui effectivement se résous avec wolfram alpha. Mais je pouvais également taper l’équation de base.

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte