Spé maths - Congruences - Exercice type bac : ax = b [mod 7]


  • B

    Bonjour. Je viens vous demander votre aide car je bloque complètement sur la deuxième partie de l'exercice. Je ne demande pas forcément les réponses toutes faites, ce n'est pas le but, j'aimerais juste comprendre la démarche à suivre dans un premier temps. Si quelqu'un aurait le temps et la patience de m'expliquer ? Merci beaucoup.

    1. On considère l'ensemble A7 = {1 ; 2 ; 3 ; 4 ; 5 ; 6}
      a) Pour tout élément a de A7, écrire dans le tableau figurant à la fin de l'exercice l'unique élément y de A7 tel que ay ≡ 1 (modulo 7).
      b) Pour x entier relatif, démontrer que l'équation 3x ≡ 5 (modulo 7) équivaut à x ≡ 4 (modulo 7).
      c) Si a est un élément de A7, montrer que les seuls entiers relatifs x solutions de l'équation ax ≡ 0 (modulo 7) sont les multiples de 7.

    2. Dans toute cette question, p est un nombre premier supérieur ou égal à 3. On considère l'ensemble Ap = {1 ; 2 ; ... ; p - 1} des entiers naturels non nuls et strictement inférieurs à p. Soit a un élément de Ap.
      a) Vérifier que a^{p - 2} est une solution de l'équation ax ≡ 1 (modulo p).

    b) On note r le reste dans la division euclidienne de a^{p - 2} par p. Démontrer que r est l'unique solution x dans Ap, de l'équation ax ≡ 1 (modulo p).
    c) Soient x et y deux entiers relatifs. Démontrer que xy ≡ 0 (modulo p) si et seulement si x est un multiple de p ou y est un multiple de p.
    d) Application : p = 31. Résoudre dans A31 les équations : 2x ≡ 1 (modulo 31) et 3x ≡ 1 (modulo 31). A l'aide des résultats précédents, résoudre dans Z l'équation 6x^2 - 5x + 1 ≡ 0 (modulo 31).


  • Zauctore

    si ça t'ennuie pas, ce serait bien d'avoir les réponses pour la partie 1... tu me dis si tu es d'accord avec moi.

    Partie 1

    1. On considère l'ensemble A(7) = {1 ; 2 ; 3 ; 4 ; 5 ; 6}.

    a) Pour tout élément a de A(7), écrire dans le tableau figurant à la fin de l'exercice l'unique élément y de A(7) tel que ay ≡ 1 (modulo 7).

    b) Pour x entier relatif, démontrer que l'équation 3x ≡ 5 (modulo 7) équivaut à x ≡ 4 (modulo 7).

    c) Si a est un élément de A(7), montrer que les seuls entiers relatifs x solutions de l'équation ax ≡ 0 (modulo 7) sont les multiples de 7.

    question a)

    un tableau comme celui-ci je suppose

    $\begin{array}{|c|c|c|c|c|c|c|} \hline a & 1 & 2 & 3 & 4 & 5 & 6 \ \hline y & 1 & 4 & 5 & 2 & 3 & 6 \ \hline \end{array}$

    question b)

    5 étant l'inverse de 3 modulo 7, on a 3x≡5;[7] ↔ 5×3x≡5×5;[7]3x \equiv 5 ; [7] \ \leftrightarrow \ 5\times 3x \equiv 5\times 5 ; [7]3x5;[7]  5×3x5×5;[7] car 3×5 = 1 [7] et on a 5×5 = 4 [7] : ok.

    question c)

    soit b l'inverse de a modulo 7, ie, l'unique nombre de A(7) tel que ba = 1 [7]. alors ax≡0;[7] ↔ bax≡0b;[7]↔x=0;[7]ax \equiv 0;[7] \ \leftrightarrow \ bax \equiv 0b ; [7] \leftrightarrow x = 0;[7]ax0;[7]  bax0b;[7]x=0;[7] puisque b×0 = 0.


  • B

    • J'ai trouvé les mêmes résultats à la question a)
    • Concernant la question b) je n'ai pas rédigé tout à fait de la même façon mais l'idée est à peu près la même.
      Je ne comprends pas parcontre, ici, le passage de bax ≡ 0b [7] à x≡ 0[7] ??

  • Zauctore

    pour tout a dans A(7) il existe un unique b dans A(7) aussi tel que ba = 1modulo 7.
    alors je multiplie tout par ce b. en quelque sorte ça permet de diviser par a.
    ok ?


  • B

    ah d'accord ! merci beaucoup
    serait-il possible d'avoir de l'aide pour la seconde partie ?
    j'ai montré que r était solution mais de là à dire que c'est la seule solution ?


  • Zauctore

    Partie 2
    2. Dans toute cette question, p est un nombre premier supérieur ou égal à 3.
    On considère l'ensemble A(p) = {1 ; 2 ; ... ; p - 1} des entiers naturels non nuls et strictement inférieurs à p.
    Soit a un élément de A(p).

    a) Vérifier que a^{p - 2} est une solution de l'équation ax ≡ 1 (modulo p).

    b) On note r le reste dans la division euclidienne de a^{p - 2} par p.
    Démontrer que r est l'unique solution x dans A(p), de l'équation ax ≡ 1 (modulo p).

    c) Soient x et y deux entiers relatifs.
    Démontrer que xy ≡ 0 (modulo p) si et seulement si x est un multiple de p ou y est un multiple de p.

    d) Application : p = 31.
    Résoudre dans A(31) les équations : 2x ≡ 1 (modulo 31) et 3x ≡ 1 (modulo 31).
    A l'aide des résultats précédents, résoudre dans Z l'équation 6x^2 - 5x + 1 ≡ 0 (modulo 31).

    question a) : a×ap−2=ap−1≡1;[p]a\times a^{p-2} = a^{p-1} \equiv 1 ; [p]a×ap2=ap11;[p] avec le petit théorème de Fermat.

    question b): la division euclidienne dit qu'il existe un unique couple (q,r)(q,r)(q,r) d'entiers tels que ap−2=qp+ra^{p-2} = qp + rap2=qp+r, où on a donc 0≤r≤p−10 \leq r \leq p-10rp1.

    tu embrayes sur la suite ? dis-moi ce que tu as fait pour prouver que r est solution...


  • B

    Je viens de relire ma réponse et finalement je viens de me rendre compte que je n'ai rien démontrer

    ap−2a^{p-2}ap2 = q * p + r avec 0 ≤ r ≤ p-1

    ap−2a^{p-2}ap2 ≡ r [p]

    Je suppose qu'il faut ensuite partir de la réponse à la question a) mais ... ?!


  • Zauctore

    en effet : on a
    a×ap−2=a(qp+r)=…,[p]a\times a^{p-2} = a(qp + r) = \dots , [p]a×ap2=a(qp+r)=,[p]

    tu poursuis ?


  • B

    a * ap−2a^{p-2}ap2 = a(qp+r) ≡ 1 [p]

    on pose qp+r = x
    donc ax ≡ 1 [p]


  • Zauctore

    mais il y a mieux : a(qp+r) ≡ 1 [p] ⇔ aqp + ar ≡ 1 [p] ⇔ ar ≡ 1 [p]

    ouf ça y est : r est solution de l'équation !


  • B

    Oui ouf ! merci beaucoup, c'est vraiment sympa de passer du temps à aider


  • Zauctore

    je t'en prie.

    laissons temporairement de côté l'unicité (je n'ai pas les idées claires sur la suffisance de l'argument) pour la q. 2.

    passons à la q. 3: tu en penses quoi ?


  • B

    d'accord.

    pour la c) je propose :

    xy ≡ 0 [p]

    donc x ≡ 0 [p] et y ≡ 0 [p]
    ce qui équivaut à x = p * q et y = p * q

    donc xy ≡ 0 [p] ⇔ x est un multiple de p ou y est un multiple de p

    le "ou" de la question est inclusif ?


  • Zauctore

    tu y vas fort !

    xy ≡ 0 [p] donc x ≡ 0 [p] et y ≡ 0 [p] est vrai mais pas automatiquement !

    la nature de p y est pour quelque chose !


  • B

    car x et y sont des entiers relatifs relatifs ?


  • Zauctore

    xy = 0 mod p signifie que p divise xy
    or p est un nombre premier, donc...


  • B

    un ami vient de m'expliquer et m'a aidé à faire le reste. Je tiens à remercier à nouveau pour l'aide et la rapidité des réponses.


  • Zauctore

    ce serait sympa alors que tu donnes rapidement tes idées sur les deux dernières questions, afin de rendre ce topic complet ; on ne sait jamais, ça peut intéresser quelqu'un d'autre...


Se connecter pour répondre