Université Claude Bernard Lyon Master MAIM 1ère année Arithmétique et combinatoire Année
5
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
5
pages
Français
Ebook
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Niveau: Supérieur
Université Claude Bernard Lyon 1 Master MAIM (1ère année) Arithmétique et combinatoire Année 2011-12 Partiel du 30 mars 2012 Correction. Exercice 1 (a) Comme 19 est un nombre premier, on a ?(19) = 19? 1 = 18. Ainsi 13 est une racine primitive de 19 si et seulement si l'ordre de 13 dans (Z/19Z)? est 18. L'ordre de tout élément devant diviser 18 = 2 ? 32, les seules possibilités sont 2, 3, 6, 9 ou 18. Il faut donc calculer 132, 133, 136 et 139. On a 132 = 169 ? 17 ? ?2 (mod 19) 133 = 13? 132 ? ?26 ? 12 (mod 19) 136 = (132)3 ? ?23 ? 11 (mod 19) 139 = 13? (132)4 ? 13? 24 ? 18 ? ?1 (mod 19). Comme 132, 133, 136 et 139 ne sont pas congrus à 1 modulo 19, on en déduit que 13 est une racine primitive de 19. (b) Remarquons que 19 divise 23n+4 + 32n+1 si et seulement si 23n+4 + 32n+1 ? 0 (mod 19), c'est-à-dire 24 ? 8n ? ?3? 9n (mod 19).
Voir
Université Claude Bernard Lyon 1 Master MAIM (1ère année) Arithmétique et combinatoire Année 2011-12 Partiel du 30 mars 2012 Correction. Exercice 1 (a) Comme 19 est un nombre premier, on a ?(19) = 19? 1 = 18. Ainsi 13 est une racine primitive de 19 si et seulement si l'ordre de 13 dans (Z/19Z)? est 18. L'ordre de tout élément devant diviser 18 = 2 ? 32, les seules possibilités sont 2, 3, 6, 9 ou 18. Il faut donc calculer 132, 133, 136 et 139. On a 132 = 169 ? 17 ? ?2 (mod 19) 133 = 13? 132 ? ?26 ? 12 (mod 19) 136 = (132)3 ? ?23 ? 11 (mod 19) 139 = 13? (132)4 ? 13? 24 ? 18 ? ?1 (mod 19). Comme 132, 133, 136 et 139 ne sont pas congrus à 1 modulo 19, on en déduit que 13 est une racine primitive de 19. (b) Remarquons que 19 divise 23n+4 + 32n+1 si et seulement si 23n+4 + 32n+1 ? 0 (mod 19), c'est-à-dire 24 ? 8n ? ?3? 9n (mod 19).
- db2
- carré modulo
- x1?a ?
- question précédente
- morphisme de groupes surjectifs
- db2 ?
- considérons ?
- n? db2
- ??
- loi de réciprocité quadratique
UniversitÉ Claude Bernard Lyon 1 ArithmÉtique et combinatoire
Master MAIM (1Ère annÉe) AnnÉe 2011-12
Partiel du 30 mars 2012 Correction.
Exercice 1 (a) Comme19est un nombre premier, on aϕ(19) = 19−1 = 18. Ainsi13est une ∗ racine primitive de19si et seulement si l’ordre de13dans(Z/19Z)est18. 2 L’ordre de tout ÉlÉment devant diviser18 = 2×3, les seules possibilitÉs sont 2 3 69 2,3,6,9ou18. Il faut donc calculer13,13,13et13. On a 2 13 =169≡17≡ −2 (mod19) 3 2 13 =13×13≡ −26≡12 (mod19) 6 23 3 13 =(13 )≡ −2≡11 (mod19) 9 24 4 13 =13×(13 )≡13×2≡18≡ −19)1 (mod. 2 3 69 Comme13,13,13et13ne sont pas congrus À1modulo19, on en dÉduit que13est une racine primitive de19. 3n+4 2n+1 3n+4 2n+1 (b) Remarquonsque19divise32 +si et seulement si2 +3≡0 (mod 19), c’est-À-dire 4n n 2×8≡ −3×9 (mod19).(1) 4 Or2 =16≡ −19)3 (mod. Comme16et19sont premiers entre eux,16est inversible modulo19et l’Équation (1) est Équivalente À n n 8≡19)9 (mod. (c) Onapplique l’algorithme d’Euclide qui donne les divisions successives 19 = 8×2 + 3,8 = 3×2 + 2,3 = 2×1 + 1, ce qui donne 1 = 3−1×2 = 3−(8−3×2) =−8 + 3×3 =−8 + 3(19−2×8) = 3×19−7×8. Ainsi, l’inverse de8modulo19est−7≡12 (mod19). 3n+4 2n+1 (d) D’aprÈs les questions (b) et (c),19divise2 +3si et seulement si n (9×12)≡19)1 (mod. Or9×12≡13 (mod19). Ainsi on obtient que19 3n+4 2n+1n divise32 +si et seulement si13≡1 (mod19). Comme13est une racine primitive de19, on obtient que l’ensemble des entiersntels que19divise 3n+4 2n+1 2 +3est l’ensemble des multiples de18. Exercice 2 (a) On raisonne par l’absurde en supposant qu’il existe un facteur premierpde 2 Nqui est infÉrieur ou Égal Àn. Alorspdivise aussi(n!)et doncpdivise 2 N−5(n!) =−1, ce qui est absurde. Autrement dit, tous les facteurs premiers deNsont strictement plus grand quen.
