Nombres premiers

C. 2 — 1 n’a qu’un seul diviseur positif et 0 est divisible par tout entier non nul : aucun des deux n’est premier. 3 est premier, mais 2, qui n’a que les diviseurs 1 et 2, est plus petit : c’est aussi le seul nombre premier pair.

D. 61 — 39 = 3 × 13, 51 = 3 × 17 et 57 = 3 × 19 sont composés (somme des chiffres divisible par 3). Pour 61 : 7² = 49 ≤ 61 < 64, et ni 2, ni 3, ni 5, ni 7 ne le divisent : 61 est premier.

A. 7 × 13 — 91 est impair, la somme de ses chiffres vaut 10 et il ne se termine ni par 0 ni par 5 ; le premier essai qui aboutit est 7 : 91 = 7 × 13. Les autres produits valent 93, 221 et 95.

B. 15 — On multiplie les exposants augmentés de 1 : (4 + 1)(2 + 1) = 15. Multiplier les exposants eux-mêmes donnerait 8, les additionner 6 : ces calculs oublient l’exposant 0.

C. 10 — Ce sont 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29 : il y en a 10. On oublie souvent 2 à cause de sa parité.

D. 78 — 45 = 3² × 5, donc la somme vaut (1 + 3 + 9)(1 + 5) = 13 × 6 = 78. Vérification : 1 + 3 + 5 + 9 + 15 + 45 = 78.

A. les nombres premiers de 11 à 97 — Tout entier composé inférieur ou égal à 100 a un diviseur premier p tel que p² ≤ 100, donc p ≤ 10 : c’est 2, 3, 5 ou 7. Après ces quatre passages, les entiers restants sont exactement les nombres premiers ; 25 ou 77, impairs et non multiples de 3, sont bien rayés.

B. ni premier ni composé — Un nombre premier a exactement deux diviseurs positifs ; 1 n’en a qu’un. Un nombre composé est, par définition, un entier supérieur ou égal à 2 non premier : 1 n’entre dans aucune des deux catégories.

C. aᵖ⁻¹ ≡ 1 [p] — C’est l’énoncé du théorème : aᵖ⁻¹ ≡ 1 [p]. La forme valable pour tout entier a est aᵖ ≡ a [p], pas aᵖ ≡ 1. Et aᵖ⁻¹ ≡ 0 [p] signifierait que p divise aᵖ⁻¹, donc a, ce qui est exclu.

D. 1 — 13 est premier et ne divise pas 4 : d’après le petit théorème de Fermat, 4¹² ≡ 1 [13]. Le reste est 1.

A. 13 — 13² = 169 ≤ 173 < 196 = 14² : on teste 2, 3, 5, 7, 11 et 13. S’arrêter à 11 serait trop tôt ; tester 17 ou 83 est inutile, car 17² = 289 > 173. Aucun de ces nombres ne divise 173, qui est premier.

B. 6 — Facteurs communs : 2 et 3, chacun avec l’exposant minimal 1. Le PGCD vaut 2 × 3 = 6 ; 5 et 7 ne sont pas communs.

C. 2² × 3² × 13 — 468 = 2² × 117 et 117 = 3² × 13. L’écriture 2² × 3 × 39 donne bien 468, mais 39 = 3 × 13 n’est pas premier : ce n’est pas une décomposition en facteurs premiers.

D. 14 — 1 458 = 2 × 729 et 729 = 3⁶, donc 1 458 = 2 × 3⁶ et le nombre de diviseurs vaut (1 + 1)(6 + 1) = 2 × 7 = 14.

A. 663 — 1 326 = 2 × 3 × 13 × 17 et 1 989 = 3² × 13 × 17. Les facteurs communs avec l’exposant minimal donnent 3 × 13 × 17 = 663. 221 et 51 sont des diviseurs communs, mais plus petits ; 117 ne divise pas 1 326.

B. 252 — 84 = 2² × 3 × 7 et 126 = 2 × 3² × 7. Les exposants maximaux donnent 2² × 3² × 7 = 252. 42 est le PGCD, et 10 584 = 84 × 126 est un multiple commun, mais pas le plus petit.

C. 3 — 2 700 = 2² × 3³ × 5² : seul l’exposant de 3 est impair, donc k = 3, et 2 700 × 3 = 8 100 = 90².

D. 4 836 — 2 000 = 2⁴ × 5³, donc la somme vaut (1 + 2 + 4 + 8 + 16)(1 + 5 + 25 + 125) = 31 × 156 = 4 836.

A. 11/13 — 1 155 = 3 × 5 × 7 × 11 et 1 365 = 3 × 5 × 7 × 13 : le PGCD vaut 105, et la simplification laisse 11/13.

B. 9 450 — pgcd(a ; b) × ppcm(a ; b) = ab, donc ab = 15 × 630 = 9 450. La somme 15 + 630 = 645 n’a pas de sens ici.

C. 4 — 7 est premier et ne divise pas 3 : 3⁶ ≡ 1 [7]. Or 100 = 6 × 16 + 4, donc 3¹⁰⁰ ≡ 3⁴ = 81 [7], et 81 = 11 × 7 + 4. Le reste est 4.

D. 11 — 11 est premier, donc n¹¹ ≡ n [11] pour tout entier n. Les autres valeurs ne conviennent pas pour n = 2 : 2¹¹ − 2 = 2 046 n’est divisible ni par 10, ni par 12, ni par 9.

A. 49 divise n² — 7 est premier et divise n × n : par le lemme d’Euclide, 7 divise n, donc n = 7k et n² = 49k². En revanche n = 7 montre que 49 ne divise pas forcément n, et n = 21 que n n’est ni forcément 7, ni un multiple de 14.

B. 12 — 6 = 6 × 1 = 3 × 2 : les entiers ayant 6 diviseurs sont de la forme p⁵ ou p²q. Les plus petits sont 2⁵ = 32 et 2² × 3 = 12 : c’est 12 (1, 2, 3, 4, 6, 12). 18 en a aussi 6 mais est plus grand, et 30 = 2 × 3 × 5 en a 8.

C. 43 — On s’arrête à la racine carrée : 44² = 1 936 et 45² = 2 025, il suffit de tester les nombres premiers inférieurs ou égaux à 44, le plus grand étant 43 ; 47² = 2 209 dépasse 2 023. Ici, d’ailleurs, le premier essai utile suffit : 2 023 = 7 × 17².

D. l’ensemble des nombres premiers est infini — Le raisonnement montre seulement que la liste des nombres premiers ne peut pas être finie. L’entier construit n’est pas forcément premier (avec la liste {3 ; 7}, N = 22 = 2 × 11), l’infinité des nombres premiers jumeaux est une question ouverte, et des plages de composés arbitrairement longues existent.

A. n est un carré parfait — Le nombre de diviseurs (a₁ + 1) × … × (aᵣ + 1) est impair si et seulement si tous les exposants aᵢ sont pairs, ce qui caractérise les carrés parfaits. Un nombre premier a 2 diviseurs, 15 en a 4, 2 en a 2.

B. p divise a — C’est le lemme d’Euclide appliqué au produit a × a : p divise l’un des facteurs, donc a. En revanche p² ne divise pas a en général (p = a = 3), et a = 6, p = 3 contredit les deux dernières propositions.

C. un nombre premier — 14² = 196 ≤ 211 < 225 = 15² : on teste 2, 3, 5, 7, 11 et 13 sans succès (les quatre premiers laissent le reste 1 par construction, 11 × 19 = 209, 13 × 16 = 208). Donc 211 est premier, mais ce n’est pas une règle générale ; 13 × 17 vaut 221.

D. 6 — Il faut (a + 1)(b + 1) = 12 : les couples (a ; b) sont (11 ; 0), (5 ; 1), (3 ; 2), (2 ; 3), (1 ; 5) et (0 ; 11), soit 6 entiers distincts, par unicité de la décomposition.

A. n est un nombre premier — C’est la définition d’un nombre premier. Elle n’impose ni la parité (3 convient) ni une valeur particulière, et un carré parfait supérieur à 1 possède au moins trois diviseurs.

B. vraie pour tous entiers naturels non nuls — La relation pgcd(a ; b) × ppcm(a ; b) = ab donne directement le résultat quand le PGCD vaut 1. Les entiers n’ont pas besoin d’être premiers ni impairs : 8 et 9 sont premiers entre eux et ppcm(8 ; 9) = 72.

C. la réciproque du petit théorème de Fermat est fausse — 645 est composé et vérifie pourtant 2⁶⁴⁴ ≡ 1 [645] : la réciproque est fausse. Le théorème lui-même ne concerne que les nombres premiers, il n’est donc pas mis en défaut, et 2 n’est pas un témoin puisque le test réussit.

D. 2 — 101 est premier et ne divise ni 2 ni 3 : d’après le petit théorème de Fermat, 2¹⁰⁰ ≡ 1 [101] et 3¹⁰⁰ ≡ 1 [101]. La somme est congrue à 2.

A. 24 — p est un nombre premier différent de 3, donc 3 ne divise pas p, et p² ≡ 1 [3] (petit théorème de Fermat avec le module 3). p est impair : p − 1 et p + 1 sont deux pairs consécutifs, dont l’un est multiple de 4, donc 8 divise (p − 1)(p + 1). 3 et 8 n’ont aucun facteur premier commun : 24 divise p² − 1. Pour p = 5, p² − 1 = 24 n’est divisible ni par 48, ni par 30, ni par 36.

B. 8 — On additionne les exposants de 2 dans chaque facteur : 2 (1), 4 (2), 6 (1), 8 (3), 10 (1), soit 1 + 2 + 1 + 3 + 1 = 8. En effet 10! = 2⁸ × 3⁴ × 5² × 7.