Université Claude Bernard Lyon Master MAIM 1ère année Arithmétique et combinatoire Année

Claude Bernard Lyon

Description

Niveau: Secondaire, Lycée, Première
Université Claude Bernard Lyon 1 Master MAIM (1ère année) Arithmétique et combinatoire Année 2011-12 Feuille 3 : Résidus quadratiques Exercice 1 Soit p un nombre premier impair. Déterminer ( p+1 2 p ) et ( p?1 2 p ) . Exercice 2 1. Déterminer les p premiers pour lesquels l'équation x2 ? 3 (mod p) admet au moins une solution ? 2. Pour quels p premiers l'équation x2 ? 5 (mod p) a-t-elle des solutions ? Exercice 3 131 et 263 sont premiers. Calculer O263(131) avec un minimum de calculs. Exercice 4 Montrer que les diviseurs premiers de 4n2 + 1 sont de la forme 4k+ 1. Exercice 5 Résoudre l'équation x2 + 3x+ 7 ? 0 (mod 115). Exercice 6 (La méthode de Hensel) Soit p un nombre premier impair, n ≥ 1 et a ? Z tel que (a, p) = 1. (a) Montrer que a¯ ? (Z/pnZ)?. (b) On suppose que x21 ? a (mod p). Montrer que, pour tout entier n ≥ 1, il existe un entier xn, unique modulo pn, qui vérifie xn ? x1 (mod p), x 2 n ? a (mod p n).

• résidus quadratiques


• équation x2


• résolution de x2 ?


• entier impair


• racine carré


• carré modulo


• algorithme de calcul

Informations

• Publié par: profil-ondu-2012
• Nombre de lectures: 82
• Langue: Français

Extrait

UniversitÉ Claude Bernard Lyon 1 ArithmÉtique et combinatoire

Master MAIM (1Ère annÉe) AnnÉe 2011-12

Feuille 3 : RÉsidus quadratiques

 ! ! p+1p−1 2 2 Exercice 1Soitpun nombre premier impair. DÉtermineret. p p

Exercice 2 2 1. DÉterminerlesppremiers pour lesquels l’Équationx≡3 (modp)admet au moins une solution? 2 2. Pourquelsppremiers l’Équationx≡5 (modp)a-t-elle des solutions?

Exercice 3131et263sont premiers. CalculerO 263 (131)avec un minimum de calculs.

2 Exercice 4Montrer que les diviseurs premiers de4n+ 1sont de la forme4k+ 1. 2 Exercice 5RÉsoudre l’Équationx+ 3x+ 7≡0 (mod115). Exercice 6 (La mÉthode de Hensel)Soitpun nombre premier impair,n≥1 eta∈Ztel que(a, p) = 1. n∗ (a) Montrerquea¯∈(Z/pZ). 2 (b) Onsuppose quex≡a(modp). Montrer que, pour tout entiern≥1, il existe 1 n un entierx n , unique modulop, qui vÉrifie 2n ≡a(m x n ≡x 1 (modp), x n odp). Indication :lesx n se construisent par rÉcurrence, en cherchantx n+1 sous la forme n x n+1 =x n +p u, oÙuest un nombre entier À dÉterminer. 2n (c) EndÉduire que la congruencex≡a(modp)admet des solutions si et seule-   a ment si= 1, et dans ce cas, elle admet exactement deux solutions modulo p n p. 2 (d)Application :rÉsoudrex+x+ 3≡0 (mod 125). 2n Exercice 7 (RÉsolution dex≡a)(mod 2(aimpair)) 2 1. Soitn≥3,aun entier impair. DÉmontrer que si la congruencex≡a n (mod 2)a des solutions, alorsa≡8)1 (mod. 2 2. On supposea≡1 (mod8). DÉmontrer quex≡a(mod 8)admet exacte- ment 4 solutions modulo8. 3. Supposons quea≡8)1 (modet supposons qu’il existe un entierxtel que 2n x≡a)(mod 2. n+1 (a) Montrerqueaest un carrÉ modulo2. n−1 2 Indication :on pourra calculer poury∈N,(x+y2 ).