UPMC — Licence d’informatique 2M120 — 2014-2015 ´ ements d’arithm´etique 2M120 — El´ Examen partiel du 12 novembre 2014 Dur´ee 1 heure 30 Aucun document n’est autoris´ e. L’utilisation de tout appareil ´ electronique de calcul et des t´ el´ ephones portables est interdite. Les correcteurs tiendront compte de la qualit´e de la r´edaction et de la pr´ecision des raisonnements. Les questions marqu´ees d’une (?) ne sont pas compt´ees dans le bar`eme. Elles rapportent des points suppl´ementaires si elles sont trait´ees. Exercice 1 — Algorithme d’Euclide (4 points) Soit a = 1073 et b = 406. ` l’aide de l’algorithme d’Euclide, d´eterminer le pgcd d de a et b, et 2 entiers u et v tels que 1. A au + bv = d 2. V´erifier que le r´esultat obtenu est correct. Exercice 2 — Congruences (10 points) 1. Soit p ≥ 3 un nombre premier. Montrer que 2p−1 ≡ 1 mod p. 2. Quel est le reste de la division euclidienne de 2014 par 4 ? En d´eduire l’entier 0 ≤ a < 5 ´egal a` 22014 mod 5. 3. D´eterminer l’entier 0 ≤ b < 13 ´egal a` 22014 mod 13. 4. D´eterminer u et v tels que 5u + 13v = 1, x ≡ a mod 5 puis r´esoudre dans Z le syst`eme d’´equations : x ≡ b mod 13 On donnera en particulier le plus petit nombre d ≥ 0 solution du syst`eme d’´equations. 5. D´eterminer l’entier 0 ≤ c < 31 ´egal a` 22014 mod  31. x ≡ a mod 5 6. (?) R´esoudre dans Z le syst`eme d’´equations : x ≡ b mod 13  x ≡ c mod 31 On donnera en particulier le plus petit nombre e ≥ 0 solution du syst`eme d’´equations. 7. (?) D´eterminer l’entier 0 ≤ n < 2015 ´egal a` 20132014 mod 2015. Exercice 3 — G´ en´ erateurs du groupe multiplicatif Z/41Z ∗ (6 points) 1. Compl´eter le tableau suivant des puissances de 2 dans Z/41Z : 14 15 16 17 18 19 20 9 18 36 ∗ En d´eduire les ordres respectifs de 2, 4, 5 et 9 dans Z/41Z , puis ceux de 3 et 6. ∗ Lequel des nombres 2, 3, 4, 5, 6 est-il g´en´erateur de Z/41Z ? ∗ Le nombre 7 est-il un g´en´erateur de Z/41Z ? Pourquoi ? ∗ (?) Combien y a-t-il de g´en´erateurs de Z/41Z ? Justifier le calcul. (?) D´eterminer un entier 0 ≤ i < 40 tel que 2 ≡ 6i mod 41. Cet entier est-il unique ? Pourquoi ? (?) D´eduire de la question pr´ec´edente un entier 0 ≤ j < 40 tel que 3 ≡ 6j mod 41. n 2n 2. 3. 4. 5. 6. 1 2 3 4 5 6 2 4 8 7 8 9 10 11 12 13 5 10 20