Nombres premiers et petit théorème de Fermat

Chiffrement RSA complet avec p = 5 et q = 11. On pose n = p×q et on choisit e = 3. a) Calculer n et φ(n) = (p−1)(q−1). b) Déterminer la clé privée d telle que 3d ≡ 1 [φ(n)]. c) Chiffrer le message m = 7. d) Retrouver m en déchiffrant le chiffré obtenu (on pourra travailler modulo 5 et modulo 11).

On veut montrer qu'il existe une infinité de nombres premiers congrus à 3 modulo 4. a) Montrer que tout entier N ≥ 2 impair congru à 3 modulo 4 possède au moins un facteur premier congru à 3 modulo 4. b) On suppose qu'il n'existe qu'un nombre fini de tels premiers q₁, …, $q_{m}$ (dont 3). En considérant N = 4(q₁×…×$q_{m}$) − 1, obtenir une contradiction.

On travaille modulo 7. a) Calculer successivement 3¹, 3², 3³, 3⁴, 3⁵, 3⁶ modulo 7 et en déduire l'ordre de 3 modulo 7. b) Justifier que 3 est une racine primitive modulo 7. c) Déterminer le reste de 3¹⁰⁰⁰ dans la division par 7. d) Résoudre $3^{x}$ ≡ 5 [7] d'inconnue l'entier naturel x.

Le but est de démontrer que pour tout entier n, 30 divise n⁵ − n. a) Rappeler pourquoi, pour p premier et PGCD(a ; p) = 1, on a $a^{p}$ ≡ a [p], puis montrer que cette congruence reste vraie si p divise a. b) En déduire que n⁵ − n est divisible par 2, par 3 et par 5. c) Conclure.

On considère l'entier 2025. a) Décomposer 2025 en produit de facteurs premiers et donner son nombre de diviseurs. b) Combien de diviseurs de 2025 sont des carrés parfaits ? c) Combien de diviseurs de 2025 sont des multiples de 15 ?

Déterminer tous les couples d'entiers naturels (a ; b) avec a ≤ b tels que PGCD(a ; b) = 6 et PPCM(a ; b) = 90. a) Justifier la méthode utilisée. b) Donner tous les couples et vérifier.

On veut déterminer le reste de 2⁷⁰ dans la division par 77, sachant que 77 = 7 × 11. a) Déterminer le reste de 2⁷⁰ modulo 7. b) Déterminer le reste de 2⁷⁰ modulo 11. c) En déduire le reste de 2⁷⁰ modulo 77.

On s'intéresse aux nombres de la forme 2ⁿ − 1. a) Montrer que si 2ⁿ − 1 est premier, alors n est premier. (On pourra utiliser l'identité 2^(ab) − 1 = ($2^{a}$ − 1)((2^a)^(b−1) + (2^a)^(b−2) + … + 1).) b) La réciproque est-elle vraie ? On étudiera le cas n = 11.

Soit p un nombre premier avec p > 3. Démontrer que p² ≡ 1 [24]. a) Montrer que 8 divise p² − 1. b) Montrer que 3 divise p² − 1. c) Conclure.

On étudie l'entier 561. a) Décomposer 561 en produit de facteurs premiers. b) Soit a un entier premier avec 561. En raisonnant modulo 3, modulo 11 et modulo 17, montrer que a⁵⁶⁰ ≡ 1 modulo chacun de ces trois nombres. c) En déduire que a⁵⁶⁰ ≡ 1 [561], bien que 561 ne soit pas premier.