Nombres premiers et petit théorème de Fermat

• \(97\) : aucun diviseur parmi \(2\), \(3\), \(5\), \(7\) : premier.
• \(91 = 7 \times 13\) : pas premier.
• \(221 = 13 \times 17\) : pas premier.
• \(101\) : aucun diviseur parmi \(2\), \(3\), \(5\), \(7\) (\(10^2 = 100 \leqslant 101 < 121\)) : premier.

🔍 Vérification : \(13 \times 17 = 221\) ✓

\(\boxed{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}\) (\(15\) nombres premiers).

🔍 Vérification : \(49 = 7^2\) est barré, \(47\) non ✓

a) \(\boxed{360 = 2^3 \times 3^2 \times 5}\)
b) \(\boxed{1\,001 = 7 \times 11 \times 13}\)
c) \(\boxed{2\,026 = 2 \times 1\,013}\)

🔍 Vérification : \(7 \times 11 \times 13 = 77 \times 13 = 1\,001\) ✓

\((3 + 1)(2 + 1)(1 + 1) = \boxed{24}\).

🔍 Vérification : voir l'exemple du cours ✓

\(84 = 2^2 \times 3 \times 7\) et \(360 = 2^3 \times 3^2 \times 5\) : \(\operatorname{PGCD} = 2^2 \times 3 = \boxed{12}\).

🔍 Vérification : l'algorithme d'Euclide donne aussi \(12\) ✓

Si \(p \geqslant 3\) était pair, \(2\) serait un diviseur de \(p\) distinct de \(1\) et de \(p\) : \(p\) ne serait pas premier. Donc \(p\) est impair ✓.

🔍 Vérification : \(2\) est le seul nombre premier pair ✓

\(2^{10} = 1\,024 = 11 \times 93 + 1\) ✓. \(3^3 = 27 \equiv 1 \ [13]\), donc \(3^{12} = (3^3)^4 \equiv 1 \ [13]\) ✓.

🔍 Vérification : ce sont les cas \(p = 11\), \(a = 2\) et \(p = 13\), \(a = 3\) du théorème de Fermat ✓

\(100 = 6 \times 16 + 4\), donc \(5^{100} \equiv 5^4 = 625 \ [7]\). Or \(625 = 7 \times 89 + 2\) : reste \(\boxed{2}\).

🔍 Vérification : \(5^2 = 25 \equiv 4\) et \(4^2 = 16 \equiv 2 \ [7]\) ✓

\(2\,047 = 23 \times 89\) : pas premier (bien que \(11\) soit premier).

🔍 Vérification : \(23 \times 89 = 2\,047\) ✓

Tous les exposants (\(2\), \(4\), \(2\)) sont pairs : c'est le carré de \(2 \times 3^2 \times 5 = \boxed{90}\) (\(90^2 = 8\,100\)).

🔍 Vérification : \(4 \times 81 \times 25 = 8\,100\) ✓

\(143\) n'est divisible ni par \(2\), ni par \(3\), ni par \(5\), ni par \(7\) ; \(143 = 11 \times 13\) : le plus petit diviseur premier est \(\boxed{11}\).

🔍 Vérification : \(11^2 = 121 \leqslant 143\) ✓

a) \(n^2 - 1 = (n - 1)(n + 1)\).

b) Pour être premier, il faut que le plus petit facteur vaille \(1\) : \(n - 1 = 1\), soit \(n = 2\), et alors \(n^2 - 1 = 3\), premier. Pour \(n \geqslant 3\), les deux facteurs sont au moins \(2\) ; pour \(n \leqslant 1\), \(n^2 - 1 \leqslant 0\). Réponse : \(\boxed{n = 2}\).

🔍 Vérification : \(n = 4\) : \(15 = 3 \times 5\) ✓

a) Voir la partie 3 du cours.

b) \(7\) premier divise \(n \times n\), donc (lemme d'Euclide) \(7\) divise \(n\) ✓.

🔍 Vérification : faux pour un non premier : \(4 \mid 2^2\) mais \(4 \nmid 2\) ✓

a) \(\dfrac{a^2}{b^2} = 2\), donc \(a^2 = 2b^2\).

b) Dans la décomposition d'un carré, l'exposant de \(2\) est pair. Celui de \(a^2\) est pair, celui de \(2b^2\) est impair (un de plus que celui de \(b^2\)). L'unicité de la décomposition donne une contradiction : \(\boxed{\sqrt{2} \text{ est irrationnel}}\).

🔍 Vérification : \(1{,}41^2 = 1{,}9881 \ne 2\), et aucune fraction ne convient ✓

a) \(6 = 6\) ou \(6 = 3 \times 2\) : \(n = p^5\) ou \(n = p^2q\) (\(p\), \(q\) premiers distincts).

b) \(2^5 = 32\) ; \(2^2 \times 3 = 12\) ; \(3^2 \times 2 = 18\)… Le plus petit est \(\boxed{12}\) (diviseurs : \(1, 2, 3, 4, 6, 12\)).

🔍 Vérification : \(12\) a bien \(6\) diviseurs ✓

Voir l'exemple du cours : reste \(\boxed{10}\).

🔍 Vérification : \(2026 \equiv 10 \ [12]\) et \(2^{10} = 1\,024 \equiv 10 \ [13]\) ✓

\(n^5 \equiv n \ [5]\) pour tout entier \(n\), donc \(5 \mid n^5 - n\) ✓.

🔍 Vérification : \(n = 3\) : \(243 - 3 = 240 = 5 \times 48\) ✓

a) \(n^7 \equiv n \ [7]\) (Fermat) : \(7 \mid n^7 - n\).

b) \(n^7 - n = n(n^6 - 1) = n(n^3 - 1)(n^3 + 1) = (n - 1)n(n + 1)(n^2 + n + 1)(n^2 - n + 1)\) contient le produit de trois entiers consécutifs \((n - 1)n(n + 1)\), divisible par \(2\) et par \(3\). Comme \(2\), \(3\) et \(7\) sont premiers entre eux deux à deux, \(2 \times 3 \times 7 = \boxed{42}\) divise \(n^7 - n\).

🔍 Vérification : \(n = 2\) : \(126 = 42 \times 3\) ✓

a) \(2^4 = 16 \equiv 1 \ [15]\), donc \(2^{14} = (2^4)^3 \times 2^2 \equiv 4 \ [15]\).

b) Si \(15\) était premier, on aurait \(2^{14} \equiv 1 \ [15]\) (Fermat). Ce n'est pas le cas : \(15\) n'est pas premier (\(2\) est un « témoin »).

🔍 Vérification : \(15 = 3 \times 5\) ✓

a) \(63 = 7 \times 9\) ✓.

b) Avec \(X = 2^a\) : \(2^{ab} - 1 = X^b - 1 = (2^a - 1)(X^{b-1} + \cdots + 1)\) ✓.

c) Si \(n = ab\) avec \(1 < a < n\), alors \(2^a - 1\) est un diviseur de \(2^n - 1\) strictement compris entre \(1\) et \(2^n - 1\) : \(2^n - 1\) n'est pas premier. Par contraposée, si \(2^n - 1\) est premier, \(n\) est premier ✓.

🔍 Vérification : la réciproque est fausse : \(n = 11\) est premier mais \(2^{11} - 1 = 2\,047\) ne l'est pas (exercice 9) ✓

\(\boxed{(3 ; 5),\ (5 ; 7),\ (11 ; 13),\ (17 ; 19),\ (29 ; 31),\ (41 ; 43)}\).

🔍 Vérification : \((23 ; 25)\) ne convient pas, car \(25 = 5^2\) ✓

a) \(a = 600\), \(b = 630\), \(\operatorname{PGCD} = 2 \times 3 \times 5 = \boxed{30}\).

b) Plus petit multiple commun : \(2^3 \times 3^2 \times 5^2 \times 7 = \boxed{12\,600}\). Et \(30 \times 12\,600 = 378\,000 = 600 \times 630\) ✓.

🔍 Vérification : \(12\,600 = 600 \times 21 = 630 \times 20\) ✓

a) \((n^2 + 2 - 2n)(n^2 + 2 + 2n) = (n^2 + 2)^2 - (2n)^2 = n^4 + 4n^2 + 4 - 4n^2 = n^4 + 4\) ✓.

b) Le petit facteur \(n^2 - 2n + 2 = (n - 1)^2 + 1\) vaut \(1\) seulement pour \(n = 1\) ; alors \(n^4 + 4 = 5\), premier. Pour \(n \geqslant 2\), les deux facteurs sont au moins \(2\) : pas premier. Pour \(n = 0\) : \(4\), pas premier. Réponse : \(\boxed{n = 1}\).

🔍 Vérification : \(n = 3\) : \(85 = 5 \times 17\) ✓

a) Si \(a \equiv 1\) et \(b \equiv 1 \ [4]\), alors \(ab \equiv 1 \ [4]\) ; par récurrence, tout produit de tels nombres est congru à \(1\).

b) Un entier impair a des facteurs premiers impairs, donc congrus à \(1\) ou \(3\) modulo \(4\). S'ils étaient tous congrus à \(1\), l'entier serait congru à \(1\) (a). Donc un entier \(\equiv 3 \ [4]\) a un facteur premier \(\equiv 3 \ [4]\). Avec \(35 = 5 \times 7\) : \(7 \equiv 3 \ [4]\) ✓.

🔍 Vérification : \(2\,027 \equiv 3 \ [4]\) est lui-même premier : son facteur est \(2\,027\) ✓

a) Démonstration d'Euclide (partie 2).

b) \(N = 30\,031 = 59 \times 509\) : pas premier. Cela ne contredit rien : la démonstration montre seulement que les facteurs premiers de \(N\) (\(59\) et \(509\)) ne sont pas dans la liste.

🔍 Vérification : \(59 \times 509 = 30\,031\) ✓

a) \(k\dbinom{p}{k} = p\dbinom{p-1}{k-1}\), donc \(p \mid k\dbinom{p}{k}\). Comme \(1 \leqslant k \leqslant p - 1\), \(p\) ne divise pas \(k\) ; le lemme d'Euclide donne \(p \mid \dbinom{p}{k}\).

b) \((a + 1)^p = a^p + \displaystyle\sum_{k=1}^{p-1} \binom{p}{k} a^k + 1 \equiv a^p + 1 \ [p]\), car tous les termes du milieu sont multiples de \(p\).

c) \(0^p = 0\) ✓. Si \(a^p \equiv a\), alors \((a + 1)^p \equiv a^p + 1 \equiv a + 1 \ [p]\) ✓. Donc \(a^p \equiv a \ [p]\) pour tout entier naturel \(a\).

🔍 Vérification : \(p = 7\) : \(\dbinom{7}{k} = 7, 21, 35, 35, 21, 7\), tous multiples de \(7\) ✓

a) \(3 \times 27 = 81 = 2 \times 40 + 1\) ✓.

b) \(c \equiv 2^3 = \boxed{8} \ [55]\).

c) \(8^2 = 64 \equiv 9\), \(8^4 \equiv 81 \equiv 26\), \(8^8 \equiv 676 \equiv 16\), \(8^{16} \equiv 256 \equiv 36\). Or \(27 = 16 + 8 + 2 + 1\) : \(8^{27} \equiv 36 \times 16 \times 9 \times 8 \ [55]\). \(36 \times 16 = 576 \equiv 26\) ; \(26 \times 9 = 234 \equiv 14\) ; \(14 \times 8 = 112 \equiv 2\). On retrouve \(\boxed{m = 2}\) ✓.

🔍 Vérification : \(8^{27} \bmod 55 = 2\) (calcul confirmé par ordinateur) ✓

a) \(561 = 3 \times 11 \times 17\) : pas premier.

b) \(561\) vérifie \(2^{560} \equiv 1 \ [561]\) comme s'il était premier. Le petit théorème de Fermat donne une condition nécessaire de primalité, pas suffisante : un nombre composé peut la vérifier (c'est un « nombre de Carmichael »).

🔍 Vérification : \(3 \times 11 \times 17 = 33 \times 17 = 561\) ✓

a) Diviseurs de \(28\) autres que lui-même : \(1, 2, 4, 7, 14\), de somme \(28\) : parfait ✓.

b) \(p = 5\) : \(2^5 - 1 = 31\) est premier, et \(2^4 \times 31 = 496\). Diviseurs propres : \(1, 2, 4, 8, 16, 31, 62, 124, 248\), de somme \(496\) ✓.

🔍 Vérification : \(1 + 2 + 4 + 8 + 16 = 31\) et \(31 + 62 + 124 + 248 = 465\) ; \(31 + 465 = 496\) ✓

a) \(N = 4p_1 \cdots p_k - 1 \equiv -1 \equiv 3 \ [4]\), et \(N\) est impair (un multiple de \(4\) moins \(1\)).

b) D'après l'exercice 24, \(N\) a un facteur premier \(q \equiv 3 \ [4]\), donc \(q\) est l'un des \(p_i\). Mais alors \(q\) divise \(4p_1 \cdots p_k\) et \(N\), donc leur différence \(1\) : impossible. Il y a donc une infinité de nombres premiers congrus à \(3\) modulo \(4\) ✓.

c) \(N = 4 \times 3 \times 7 - 1 = 83\), qui est premier, congru à \(3\) modulo \(4\), et absent de la liste ✓.

🔍 Vérification : \(83 = 4 \times 20 + 3\) ✓