Congruence arithmétique questions indépendantes ,sujet
-
MMarvin dernière édition par Marvin
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}.- 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. - 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}. - 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. - En déduire le résultat.
II. On pose p = 19 et a = 2 dans cette question.
- 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. - Soit k un entier naturel. Montrer que 2k ≡ 1 mod 19 si, et seulement si
ord(2) divise k. - En d´déduire que ord(2) est un diviseur de 18.
- Ecrire un algorithme permettant de calculer l’ordre de 2. ´
- 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.
- 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-11≤k≤p−1 donc ppp ne divise aucun nombre kkk avec 1≤k≤p−11\leq k \leq p-11≤k≤p−1 donc d'après le raisonnement précédent ppp ne divise aucun kakaka avec 1≤k≤p−11\leq k \leq p-11≤k≤p−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-10≤ai≤p−1
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)(p−1) entiers compris entre 1 et p−1p-1p−1, 2 à 2 distincts donc ce sont les entiers compris au sens large entre 1 et p−1p-1p−1
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).
- Soit k un entier relatif ; montrer que p divise ka si, et seulement si p divise