Congruence arithmétique questions indépendantes ,sujet


  • M

    Bonjour , j'ai répondu aux questions de la partie 1 de ce devoir, mais je voulais savoir si quelqu'un pourrai corrigé mes éventuelles erreurs svp?

    I. Soit p un nombre premier, et a un entier non multiple de p.
    Dans cette question, on va d´démontrer la congruence
    a
    p−1 ≡ 1 mod p
    connue sous le nom de petit théorème de Fermat.
    On considère l’ensemble A = {a, 2a, . . . ,(p − 1)a} = {ka, 1 ≤ k ≤ p − 1}.

    1. Soit k un entier relatif ; montrer que p divise ka si, et seulement si p divise
      k. En d´déduire que p ne divise aucun des ´éléments de A.
    2. Pour 1 ≤ i ≤ p − 1, on note ai
      le reste de la division euclidienne de ia par
      p.
      a. Montrer que les ai
      , 1 ≤ i ≤ p − 1 sont non nuls, et deux `a deux
      distincts.
      b. En d´déduire qu’on a {ai
      , 1 ≤ i ≤ p − 1} = {1, . . . , p − 1}.
    3. On note P le produit de tous les ´éléments de A. Montrer qu’on a l’égalité
      P = a
      p−1
      (p − 1)!, et la congruence P ≡ (p − 1)! mod p.
    4. En déduire le résultat.

    II. On pose p = 19 et a = 2 dans cette question.

    1. Montrer que a et p sont premiers entre eux, qu’il existe un plus petit
      entier naturel non nul k tel que 2k ≡ 1 mod 19, et que cet entier k est
      inférieur ou ´égal `a 18.
      Définition. On appelle l’entier k d´défini ci-dessus l’ordre de 2, et on le
      note ord(2). On dit que 2 est primitif modulo 19 si ord(2) = 18.
    2. Soit k un entier naturel. Montrer que 2k ≡ 1 mod 19 si, et seulement si
      ord(2) divise k.
    3. En d´déduire que ord(2) est un diviseur de 18.
    4. Ecrire un algorithme permettant de calculer l’ordre de 2. ´
    5. a. Déterminer l’ensemble des diviseurs de 18.
      b. Montrer que 2 est primitif modulo 19 si, et seulement si on a 29 6≡ 1
      mod 19 et 22 6≡ 1 mod 19.
      c. En d´déduire que 2 est primitif modulo 19.

    Voila ma rédaction.

    1. ppp et aaa sont premiers entre eux.
      D'après le théorème de Gauss : ppp premier avec aaa donc ppp divise kakaka si et seulement si ppp divise kkk

    ppp est premier et 1≤k≤p−11\leq k\leq p-11kp1 donc ppp ne divise aucun nombre kkk avec 1≤k≤p−11\leq k \leq p-11kp1 donc d'après le raisonnement précédent ppp ne divise aucun kakaka avec 1≤k≤p−11\leq k \leq p-11kp1

    1. a. En considérant la division euclidienne par ppp on a : ia=pq+aiia=pq+a_iia=pq+ai avec 0≤ai≤p−10\leq a_i\leq p-10aip1
      ai=0a_i=0ai=0 implique ppp divise iaiaia en contradiction avec la question 1. donc les iaiaia sont non nuls.

    Les éléments de AAA étant 2 à 2 distincts les aia_iai sont 2 à 2 distincts.

    b. Les aia_iai sont (p−1)(p-1)(p1) entiers compris entre 1 et p−1p-1p1, 2 à 2 distincts donc ce sont les entiers compris au sens large entre 1 et p−1p-1p1
    Question 3)
    Pour chaque élément de A, le reste de la division euclidienne de ia par p est un des nombres de l'ensemble {1, 2, ..., p-1}. Donc, P est le produit de tous les éléments de l'ensemble {1, 2, ..., p-1}, c'est-à-dire le produit (p-1)!.

    Maintenant, pour montrer que P ≡ (p-1)! (mod p), nous pouvons exprimer chaque élément de A comme ai ≡ i (mod p). Donc, le produit P peut être écrit comme P ≡ 1 * 2 * ... * (p-1) (mod p), ce qui est équivalent à P ≡ (p-1)! (mod p).

    4)À partir de la congruence P ≡ (p-1)! (mod p), nous pouvons diviser les deux côtés par (p-1)! pour obtenir P/(p-1)! ≡ 1 (mod p).


Se connecter pour répondre