Nombres premiers

Décomposer chaque entier en produit de facteurs premiers, facteurs dans l’ordre croissant.

1. $588=2^a\times 3\times 7^c$ : exposant $a$ = et exposant $c$ =
   $588=2\times 294=2^2\times 147$. Puis $1+4+7=12$ est divisible par $3$ : $147=3\times 49$, soit $147=3\times 7^2$. Donc $588=2^2\times 3\times 7^2$.
2. $1125$ : exposant de $3$ = et exposant de $5$ =
   $1125$ est impair et se termine par $5$ : $1125=5\times 225=5^2\times 45=5^3\times 9$. Donc $1125=3^2\times 5^3$.
3. $2025$ : exposant de $3$ = et exposant de $5$ =
   $2025=5\times 405=5^2\times 81$ et $81=3^4$. Donc $2025=3^4\times 5^2$. Tous les exposants sont pairs : $2025$ est le carré de $3^2\times 5=45$.
4. Plus grand facteur premier de $1001$ :
   $1001$ est impair, $1+0+0+1=2$, il ne se termine ni par $0$ ni par $5$, et $1001=7\times 143$. Enfin $143=11\times 13$. Donc $1001=7\times 11\times 13$ : le plus grand facteur premier est $13$.

Fractions irréductibles et nombres premiers.

1. $\text{pgcd}(4095;5355)$ =
   $4095=5\times 819$ et $819=3^2\times 91=3^2\times 7\times 13$, donc $4095=3^2\times 5\times 7\times 13$. De même $5355=5\times 1071$ et $1071=3^2\times 119=3^2\times 7\times 17$, donc $5355=3^2\times 5\times 7\times 17$. Facteurs communs : $3^2\times 5\times 7$, soit $315$.
2. Forme irréductible de ${\displaystyle \frac{4095}{5355}}$ :
   En divisant par $315$ : ${\displaystyle \frac{4095}{5355}}={\displaystyle \frac{13}{17}}$, irréductible car $13$ et $17$ sont deux nombres premiers distincts.
3. Forme irréductible de ${\displaystyle \frac{2464}{3360}}$ :
   $2464=2^5\times 77=2^5\times 7\times 11$ et $3360=2^5\times 105=2^5\times 3\times 5\times 7$. Le PGCD vaut $2^5\times 7=224$, et ${\displaystyle \frac{2464}{3360}}={\displaystyle \frac{11}{15}}$ : $15=3\times 5$ ne partage aucun facteur premier avec $11$.
4. Démontrer que si $p$ et $q$ sont deux nombres premiers distincts, la fraction ${\displaystyle \frac{p}{q}}$ est irréductible. Valeur de $\text{pgcd}(p;q)$ :
   Rédaction attendue. Soit $d=\text{pgcd}(p;q)$. Comme $d$ est un diviseur positif de $p$ et que $p$ est premier, $d=1$ ou $d=p$. Si $d=p$, alors $p$ divise $q$ ; comme $q$ est premier et $p⩾2$, cela impose $p=q$, ce qui est exclu. Donc $d=1$ : $p$ et $q$ sont premiers entre eux et la fraction ${\displaystyle \frac{p}{q}}$ est irréductible.

Nombres premiers et parité.

1. Nombre de nombres premiers inférieurs à $100$ :
   $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$, $59$, $61$, $67$, $71$, $73$, $79$, $83$, $89$ et $97$ : il y en a $25$.
2. Démontrer que si $n$ et $n+1$ sont tous deux premiers, alors $n=2$. Valeur de $n$ :
   Rédaction attendue. Parmi deux entiers consécutifs, l’un est pair. Or le seul nombre premier pair est $2$. Si $n+1=2$, alors $n=1$, qui n’est pas premier : impossible. Donc $n=2$, et réciproquement $2$ et $3$ sont bien premiers.
3. Démontrer que tout nombre premier $p⩾3$ s’écrit $4k+1$ ou $4k+3$ avec $k$ entier naturel. Reste de la division de $97$ par $4$ :
   Rédaction attendue. La division euclidienne de $p$ par $4$ donne $p=4k+r$ avec $r\in \{0;1;2;3\}$. Si $r=0$, $p=4k=2\times 2k$ ; si $r=2$, $p=4k+2=2(2k+1)$. Dans les deux cas $p$ serait pair et, comme $p⩾3$, différent de $2$ : il ne serait pas premier. Ainsi $r=1$ ou $r=3$. Pour $97$ : $97=4\times 24+1$, le reste est $1$.

Pour chaque entier, on cherche s’il est premier en testant les nombres premiers jusqu’à sa racine carrée.

1. Plus petit diviseur premier de $209$ :
   ${14}^2=196⩽209<225={15}^2$ : on teste jusqu’à $13$. $209$ est impair, $2+0+9=11$, il ne se termine ni par $0$ ni par $5$, $7\times 29=203$ (reste $6$), et $209=11\times 19$ : $209$ est composé.
2. $251$ est premier. Plus grand nombre premier qu’il faut tester pour le prouver :
   ${15}^2=225⩽251<256={16}^2$ : on teste $2$, $3$, $5$, $7$, $11$ et $13$. $251$ est impair, $2+5+1=8$, il ne se termine ni par $0$ ni par $5$, $7\times 35=245$ (reste $6$), $11\times 22=242$ (reste $9$), $13\times 19=247$ (reste $4$). Aucun reste nul : $251$ est premier.
3. Plus petit diviseur premier de $343$ :
   $343$ est impair, $3+4+3=10$, il ne se termine ni par $0$ ni par $5$, et $343=7\times 49=7^3$ : $343$ est composé.
4. Plus petit diviseur premier de $391$ :
   ${19}^2=361⩽391<400={20}^2$ : on teste jusqu’à $19$. $2$, $3$, $5$ ne conviennent pas ; $7\times 55=385$ (reste $6$), $11\times 35=385$ (reste $6$), $13\times 30=390$ (reste $1$), puis $391=17\times 23$ : $391$ est composé.

On applique le crible d’Ératosthène aux entiers de $2$ à $150$.

1. Plus grand nombre premier dont on raye les multiples :
   On raye les multiples de $p$ tant que $p^2⩽150$ : ${11}^2=121⩽150$, mais ${13}^2=169>150$. On raye donc les multiples de $2$, $3$, $5$, $7$ et $11$.
2. Premier entier rayé comme multiple de $11$ :
   Les multiples $22$, $33$, …, $110$ s’écrivent $11\times k$ avec $k⩽10$ : ils ont un facteur premier inférieur à $11$ et sont déjà rayés. Le premier multiple nouveau est ${11}^2=121$.
3. Nombre de nombres premiers inférieurs ou égaux à $150$ :
   On en compte $25$ jusqu’à $100$, puis $101$, $103$, $107$, $109$, $113$, $127$, $131$, $137$, $139$ et $149$ : $25+10=35$.

Le plus petit diviseur d’un entier.

1. Démontrer que le plus petit diviseur $d⩾2$ d’un entier $n⩾2$ est un nombre premier. Plus petit diviseur supérieur ou égal à $2$ de $1517$ :
   Rédaction attendue. L’ensemble des diviseurs de $n$ supérieurs ou égaux à $2$ contient $n$ : c’est une partie non vide de $\mathbb{N}$, qui a un plus petit élément $d$. Si $d$ n’était pas premier, il aurait un diviseur $d\prime$ avec $2⩽d\prime <d$, et $d\prime$ diviserait $n$ (car $d\prime$ divise $d$ qui divise $n$) : cela contredit la minimalité de $d$. Donc $d$ est premier. Pour $1517$ : ${38}^2=1444⩽1517<1521={39}^2$ ; les nombres premiers de $2$ à $31$ ne le divisent pas, et $37$ divise $1517$ : le plus petit diviseur cherché est $37$.
2. Plus grand facteur premier de $1517$ :
   $1517÷37=41$, et $41$ est premier ($6^2=36⩽41<49$ ; ni $2$, ni $3$, ni $5$ ne le divisent). Donc $1517=37\times 41$ n’est pas premier.

Le critère de la racine carrée.

1. Démontrer que si un entier $n⩾2$ est composé, il admet un diviseur premier $p$ tel que $p^2⩽n$. Nombre de nombres premiers à tester pour montrer que $1009$ est premier :
   Rédaction attendue. Si $n$ est composé, $n=ab$ avec $2⩽a⩽b$, donc $a^2⩽ab=n$. L’entier $a⩾2$ admet un diviseur premier $p⩽a$, donc $p^2⩽a^2⩽n$ ; et $p$ divise $a$ qui divise $n$. Pour $1009$ : ${31}^2=961⩽1009<1024={32}^2$ ; on teste $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$ et $31$, soit $11$ nombres premiers, et aucun ne divise $1009$.
2. Plus petit diviseur premier de $1147$ :
   ${33}^2=1089⩽1147<1156={34}^2$ : on teste jusqu’à $31$. Les nombres premiers de $2$ à $29$ échouent, et $1147=31\times 37$ : le dernier test est le bon.
3. Un élève teste la divisibilité de $1009$ par tous les entiers de $2$ à $504$. Nombre de divisions qu’il effectue en plus par rapport au critère :
   De $2$ à $504$, il y a $503$ entiers. Le critère n’en demande que $11$ (les nombres premiers jusqu’à $31$). L’élève fait donc $503-11=492$ divisions inutiles.

On reprend la construction de la démonstration avec la liste $\{3;5;7\}$.

1. $N=3\times 5\times 7+1$ =
   $3\times 5\times 7=105$, donc $N=106$.
2. Reste de la division de $N$ par $7$ :
   $106=7\times 15+1$. De même $106=3\times 35+1=5\times 21+1$ : par construction, aucun nombre de la liste ne divise $N$.
3. Plus grand facteur premier de $N$ :
   $106=2\times 53$, et $53$ est premier ($7^2=49⩽53<64$ ; ni $2$, ni $3$, ni $5$, ni $7$ ne le divisent). Les facteurs premiers $2$ et $53$ sont hors de la liste.

On considère $30031=2\times 3\times 5\times 7\times 11\times 13+1$.

1. Reste de la division de $30031$ par $13$ :
   $30031=13\times 2310+1$ : par construction, la division de $30031$ par chacun des nombres $2$, $3$, $5$, $7$, $11$ et $13$ laisse le reste $1$.
2. Plus petit diviseur premier de $30031$ :
   Aucun des six premiers nombres premiers ne convient. On poursuit : $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$ et $53$ échouent, puis $30031=59\times 509$. Enfin $509$ est premier : ${22}^2=484⩽509<529={23}^2$, et aucun nombre premier jusqu’à $19$ ne le divise.
3. Justifier que ce résultat ne met pas en défaut la démonstration d’Euclide. Nombre de facteurs premiers de $30031$ absents de la liste $2,3,5,7,11,13$ :
   Rédaction attendue. La démonstration n’affirme jamais que $p_1\times \dots \times p_r+1$ est premier : elle affirme que cet entier admet un diviseur premier, et que ce diviseur n’est aucun des $p_i$ (sinon il diviserait $1$). C’est ce que l’on observe : $30031=59\times 509$ n’est pas premier, mais ses deux facteurs premiers $59$ et $509$ sont nouveaux.

On pose $f(n)=n^2+n+41$ pour tout entier naturel $n$. On admet que $f(0)$, $f(1)$, …, $f(39)$ sont tous premiers.

1. $f(40)$ =
   $f(40)=1600+40+41=1681$.
2. $f(40)$ est le carré d’un nombre premier. Lequel ?
   $f(40)=40\times 40+40+41$ $=40\times 41+41$ $=41\times 41={41}^2$. Donc $f(40)$ n’est pas premier.
3. Démontrer que $41$ divise $f(41)$. Quotient $f(41)÷41$ :
   Rédaction attendue. $f(41)={41}^2+41+41$ $=41\times (41+1+1)$ $=41\times 43$. Comme $1<41<f(41)$, $f(41)$ est composé. Une formule qui donne des nombres premiers pour les premières valeurs ne prouve rien : le théorème d’Euclide ne fournit aucune formule des nombres premiers.

On veut démontrer qu’il existe une infinité de nombres premiers de la forme $4k+3$, avec $k$ entier naturel.

1. Démontrer que le produit de deux entiers de la forme $4a+1$ est encore de cette forme. Reste de la division de $13\times 17$ par $4$ :
   Rédaction attendue. $(4a+1)(4b+1)=16ab+4a+4b+1$ $=4(4ab+a+b)+1$, avec $4ab+a+b$ entier. Par récurrence, tout produit d’entiers de la forme $4k+1$ est de cette forme. Exemple : $13\times 17=221=4\times 55+1$.
2. Pour illustrer, on imagine que la liste des nombres premiers de la forme $4k+3$ soit $3$, $7$, $11$, et on pose $M=4\times 3\times 7\times 11-1$. $M$ =
   $4\times 3\times 7\times 11=924$, donc $M=923$.
3. Reste de la division de $M$ par $4$ :
   $923=4\times 230+3$. En général, $M=4q_1\cdots q_s-1$ $=4(q_1\cdots q_s-1)+3$ est de la forme $4k+3$.
4. On a $M=13\times 71$. Démontrer qu’il existe une infinité de nombres premiers de la forme $4k+3$. Facteur premier de $M$ de la forme $4k+3$ :
   Rédaction attendue. $13=4\times 3+1$ et $71=4\times 17+3$ : c’est $71$, absent de la liste. Cas général, par l’absurde : soit $q_1,\dots ,q_s$ tous les nombres premiers de la forme $4k+3$ (la liste contient $3$) et $M=4q_1\cdots q_s-1⩾11$, de la forme $4k+3$. $M$ est impair : ses facteurs premiers sont de la forme $4k+1$ ou $4k+3$. S’ils étaient tous de la forme $4k+1$, leur produit $M$ le serait aussi, ce qui est faux. Donc $M$ a un facteur premier $q$ de la forme $4k+3$, égal à un $q_i$. Alors $q$ divise $4q_1\cdots q_s$ et $M$, donc leur différence $1$ : contradiction.

Diviseurs de $1452$ et de $507$.

1. Nombre de diviseurs positifs de $1452$ :
   $1452=2\times 726=2^2\times 363$ et $363=3\times 121$, soit $363=3\times {11}^2$, donc $1452=2^2\times 3\times {11}^2$. Nombre de diviseurs : $(2+1)(1+1)(2+1)=18$.
2. Somme des diviseurs positifs de $1452$ :
   $\sigma (1452)=(1+2+4)(1+3)$ $\times (1+11+121)$ $=7\times 4\times 133=28\times 133$ $=3724$.
3. $507=3\times {13}^2$. Plus grand diviseur positif de $507$ autre que $507$ :
   Les diviseurs sont les $3^b\times {13}^c$ avec $b\in \{0;1\}$ et $c\in \{0;1;2\}$ : $1$, $3$, $13$, $39$, $169$ et $507$. Le plus grand diviseur strict est $169$.

On pose $n=8820$.

1. Démontrer que $n$ n’est pas un carré parfait. Exposant de $5$ dans la décomposition de $n$ :
   Rédaction attendue. $8820=2\times 4410=2^2\times 2205$ ; $2+2+0+5=9$, donc $2205=3^2\times 245=3^2\times 5\times 7^2$. Ainsi $8820=2^2\times 3^2\times 5\times 7^2$. Un entier est un carré parfait si et seulement si tous les exposants de sa décomposition sont pairs ; ici l’exposant de $5$ vaut $1$ : $8820$ n’est pas un carré parfait.
2. Plus petit entier $k⩾1$ tel que $8820k$ soit un carré parfait :
   Il faut rendre tous les exposants pairs. Seul celui de $5$ est impair : $k=5$ suffit, et c’est le plus petit, car $k$ doit contenir le facteur $5$.
3. Racine carrée de $8820\times 5$ :
   $8820\times 5=2^2\times 3^2\times 5^2\times 7^2$ $=(2\times 3\times 5\times 7{)}^2$ $={210}^2=44100$.
4. Plus petit entier $m⩾1$ tel que $8820m$ soit un cube parfait :
   Chaque exposant doit devenir un multiple de $3$ : il manque $2^1$, $3^1$, $5^2$ et $7^1$. Donc $m=2\times 3\times 25\times 7=1050$, et $8820\times 1050$ $=2^3\times 3^3\times 5^3\times 7^3={210}^3$.

Le lemme d’Euclide et ses conséquences.

1. Démontrer le lemme d’Euclide à partir du théorème de Gauss. Plus petit entier $m⩾2$ qui divise un produit de deux entiers sans diviser aucun des deux facteurs :
   Rédaction attendue. Soit $p$ premier divisant $ab$. Si $p$ ne divise pas $a$, $\text{pgcd}(a;p)=1$, car les seuls diviseurs positifs de $p$ sont $1$ et $p$ ; le théorème de Gauss donne alors $p$ divise $b$. Les entiers $2$ et $3$ sont premiers et vérifient donc le lemme. En revanche $4$ divise $2\times 2=4$ sans diviser $2$ : le plus petit est $4$.
2. On suppose que $7$ divise $n^2$. Démontrer que $49$ divise $n^2$. Pour $n=42$, quotient $n^2÷49$ :
   Rédaction attendue. $7$ est premier et divise $n\times n$ : d’après le lemme d’Euclide, $7$ divise $n$. Donc $n=7k$ avec $k$ entier, et $n^2=49k^2$ : $49$ divise $n^2$. Pour $n=42=7\times 6$ : $n^2=1764=49\times 36$.
3. Démontrer qu’il n’existe aucun couple $(a;b)$ d’entiers naturels non nuls tels que $2^a=5^b$. Nombre de tels couples :
   Rédaction attendue. Si $2^a=5^b$ avec $a⩾1$, le nombre premier $2$ divise $5^b=5\times \dots \times 5$ ; d’après le lemme d’Euclide, il divise l’un des facteurs, donc $2$ divise $5$ : c’est faux. Autre argument : l’unicité de la décomposition, puisque $2^a$ et $5^b$ n’ont pas les mêmes facteurs premiers. Il n’y a aucun couple.

Un entier $N⩾1$ est dit parfait lorsque la somme $\sigma (N)$ de ses diviseurs positifs vaut $2N$.

1. Pour $N=2^3\times 15=120$, $\sigma (120)$ =
   $120=2^3\times 3\times 5$, donc $\sigma (120)=(1+2+4+8)(1+3)(1+5)$ $=15\times 4\times 6=360$. Comme $360\ne 240$, $120$ n’est pas parfait : ici $2^4-1=15$ n’est pas premier.
2. Soit $p⩾2$ tel que $q=2^p-1$ soit premier. Démontrer que $N=2^{p-1}q$ est parfait. Pour $p=7$, valeur de $\sigma (2^6)$ :
   Rédaction attendue. Comme $p⩾2$, $q⩾3$ est un nombre premier impair, différent de $2$ : la décomposition de $N$ est $2^{p-1}\times q$. Donc $\sigma (N)=(1+2+\dots +2^{p-1})(1+q)$. La somme géométrique vaut $2^p-1=q$, et $1+q=2^p$, d’où $\sigma (N)=q\times 2^p=2\times 2^{p-1}q=2N$ : $N$ est parfait. Pour $p=7$ : $\sigma (2^6)=1+2+\dots +64$ $=2^7-1=127$.
3. On admet que $2^{13}-1=8191$ est premier. Nombre parfait obtenu avec $p=13$ :
   $N=2^{12}\times 8191$, soit $4096\times 8191=33550336$.

Autour du nombre de diviseurs.

1. Nombre d’entiers de la forme $2^a\times 5^b$ ($a$ et $b$ entiers naturels) ayant exactement $15$ diviseurs positifs :
   Il faut $(a+1)(b+1)=15$. Les factorisations $1\times 15$, $3\times 5$, $5\times 3$ et $15\times 1$ donnent $(a;b)\in \{(0;14),(2;4),(4;2),(14;0)\}$, soit $4$ entiers : $5^{14}$, $2^2\times 5^4$, $2^4\times 5^2$ et $2^{14}$.
2. Le plus petit de ces entiers :
   $2^4\times 5^2=400$, $2^2\times 5^4=2500$ et $2^{14}=16384$, et $5^{14}>2^{14}$ car $5>2$ : le plus petit est $400$.
3. Nombre de diviseurs positifs de $7^6\times {13}^4$ :
   $7$ et $13$ sont premiers distincts : $(6+1)(4+1)=35$.
4. Démontrer qu’un entier $n⩾2$ a un nombre impair de diviseurs positifs si et seulement si c’est un carré parfait. Nombre de diviseurs positifs de $3600$ :
   Rédaction attendue. Si $n=p_1^{a_1}\cdots p_r^{a_r}$, le nombre de diviseurs est $(a_1+1)\cdots (a_r+1)$. Un produit d’entiers est impair si et seulement si chaque facteur est impair, c’est-à-dire si et seulement si chaque $a_i$ est pair, ce qui caractérise les carrés parfaits. Pour $3600=2^4\times 3^2\times 5^2={60}^2$ : $5\times 3\times 3=45$ diviseurs, nombre impair.

On pose $a=2376$ et $b=3168$.

1. Exposant de $2$ dans la décomposition de $3168$ :
   $3168=2\times 1584=2^2\times 792$ $=2^3\times 396=2^4\times 198=2^5\times 99$ et $99=3^2\times 11$ : $b=2^5\times 3^2\times 11$. De même $2376=2^3\times 297=2^3\times 3^3\times 11$.
2. $\text{pgcd}(2376;3168)$ =
   Exposants minimaux : $2^3\times 3^2\times 11$, soit $8\times 9\times 11=792$.
3. $\text{ppcm}(2376;3168)$ =
   Exposants maximaux : $2^5\times 3^3\times 11$, soit $32\times 27\times 11=9504$.
4. Produit $2376\times 3168$, qui doit être égal à $\text{pgcd}\times \text{ppcm}$ :
   $2376\times 3168$ $=2376\times 3000+2376\times 168$ $=7128000+399168$ $=7527168$, et $792\times 9504=7527168$ : la relation est vérifiée.

Utiliser les exposants.

1. Démontrer que $\text{pgcd}(a;b)\times \text{ppcm}(a;b)=ab$ pour $a,b⩾2$. Si $\text{pgcd}(a;b)=12$ et $ab=11088$, alors $\text{ppcm}(a;b)$ =
   Rédaction attendue. On écrit $a=\prod p_i^{a_i}$ et $b=\prod p_i^{b_i}$ sur la même liste. Alors $\text{pgcd}\times \text{ppcm}$ $=\prod p_i^{min(a_i,b_i)+max(a_i,b_i)}$. Pour chaque $i$, l’un des deux exposants est le minimum et l’autre le maximum, donc $min(a_i,b_i)+max(a_i,b_i)=a_i+b_i$, et le produit vaut $\prod p_i^{a_i+b_i}=ab$. Ici $\text{ppcm}=11088÷12=924$.
2. $\text{pgcd}(2^5\times 7;3^4\times 11)$ =
   Les deux entiers n’ont aucun facteur premier commun : leur PGCD vaut $1$, ils sont premiers entre eux.
3. Plus petit entier strictement positif divisible par $12$, par $18$ et par $30$ :
   $12=2^2\times 3$, $18=2\times 3^2$, $30=2\times 3\times 5$. On prend chaque facteur premier avec son plus grand exposant : $2^2\times 3^2\times 5=180$.

On cherche tous les couples $(a;b)$ d’entiers naturels non nuls, avec $a⩽b$, tels que $\text{pgcd}(a;b)=18$ et $\text{ppcm}(a;b)=1512$.

1. Démontrer que $a=18a\prime$ et $b=18b\prime$ avec $a\prime$ et $b\prime$ premiers entre eux, puis calculer le produit $a\prime b\prime$ :
   Rédaction attendue. $18$ divise $a$ et $b$ : $a=18a\prime$ et $b=18b\prime$ avec $a\prime$, $b\prime$ entiers. Si $a\prime$ et $b\prime$ avaient un diviseur commun $k⩾2$, $18k$ diviserait $a$ et $b$, ce qui contredirait $\text{pgcd}(a;b)=18$ : donc $\text{pgcd}(a\prime ;b\prime )=1$. La relation $\text{pgcd}\times \text{ppcm}=ab$ donne $18\times 1512=18a\prime \times 18b\prime$, d’où $a\prime b\prime ={\displaystyle \frac{1512}{18}}=84$.
2. Nombre de couples $(a;b)$ solutions :
   $84=2^2\times 3\times 7$. Comme $a\prime$ et $b\prime$ sont premiers entre eux, chaque facteur premier va entièrement dans l’un des deux : $a\prime \in \{1;3;4;7\}$ avec $a\prime ⩽b\prime$, d’où $(1;84)$, $(3;28)$, $(4;21)$, $(7;12)$, puis $(18;1512)$, $(54;504)$, $(72;378)$ et $(126;216)$.
3. Plus petite valeur de la somme $a+b$ parmi ces couples :
   Les sommes valent $1530$, $558$, $450$ et $342$. La plus petite est $126+216=342$. Contrôle : $126=2\times 3^2\times 7$ et $216=2^3\times 3^3$ donnent bien PGCD $2\times 3^2=18$ et PPCM $2^3\times 3^3\times 7=1512$.
4. Nombre de couples dans lesquels $a$ et $b$ ont le même nombre de diviseurs positifs :
   $18$ : $6$ diviseurs et $1512=2^3\times 3^3\times 7$ : $32$ ; $54$ : $8$ et $504$ : $24$ ; $72$ : $12$ et $378$ : $16$ ; $126$ : $12$ et $216$ : $16$. Aucun couple ne convient.

Utiliser le petit théorème de Fermat pour trouver des restes.

1. Reste de la division de $5^{1000}$ par $7$ :
   $7$ est premier et ne divise pas $5$ : $5^6\equiv 1[7]$. Or $1000=6\times 166+4$, donc $5^{1000}\equiv 5^4=625[7]$, et $625=89\times 7+2$. Le reste est $2$.
2. Reste de la division de ${10}^{50}$ par $17$ :
   $17$ est premier et ne divise pas $10$ : ${10}^{16}\equiv 1[17]$. Or $50=16\times 3+2$, donc ${10}^{50}\equiv {10}^2=100[17]$, et $100=5\times 17+15$. Le reste est $15$.
3. Reste de la division de $6^{2026}$ par $11$ :
   $11$ est premier et ne divise pas $6$ : $6^{10}\equiv 1[11]$. Or $2026=10\times 202+6$, donc $6^{2026}\equiv 6^6[11]$. Puis $6^2=36\equiv 3$, $6^6\equiv 3^3=27\equiv 5[11]$. Le reste est $5$.

Les hypothèses du théorème.

1. Reste de la division de $4^8$ par $9$ :
   $9$ n’est pas premier : on ne peut pas affirmer $4^8\equiv 1[9]$. Calcul direct : $4^3=64=7\times 9+1$, donc $4^3\equiv 1[9]$ et $4^8=(4^3{)}^2\times 4^2\equiv 16\equiv 7[9]$.
2. Reste de la division de ${26}^{12}$ par $13$ :
   $13$ est premier mais il divise $26$ : la première forme ne s’applique pas. Ici ${26}^{12}$ est un multiple de $13$, et le reste est $0$, pas $1$.
3. Reste de la division de $3^{13}$ par $13$ :
   Seconde forme du théorème : $13$ est premier, donc $3^{13}\equiv 3[13]$. Le reste est $3$.

Dans cet exercice, $n$ désigne un entier relatif.

1. Justifier que $7$ divise $n^7-n$. Pour $n=2$, quotient de $2^7-2$ par $7$ :
   $7$ est premier : d’après la seconde forme du petit théorème de Fermat, $n^7\equiv n[7]$ pour tout entier $n$, donc $7$ divise $n^7-n$. Pour $n=2$ : $128-2=126=7\times 18$.
2. Démontrer que $42$ divise $n^7-n$ pour tout entier $n$. Quotient de $3^7-3$ par $42$ :
   Rédaction attendue. Modulo $2$ : $n^2\equiv n[2]$ (Fermat avec $p=2$), donc $n^7\equiv n[2]$. Modulo $3$ : $n^3\equiv n[3]$, donc $n^7=n^3\times n^3\times n\equiv n^3\equiv n[3]$. Modulo $7$ : $n^7\equiv n[7]$. Ainsi $2$, $3$ et $7$ divisent $N=n^7-n$. Si $N\ne 0$, les nombres premiers distincts $2$, $3$ et $7$ figurent dans la décomposition de $|N|$, donc $2\times 3\times 7=42$ divise $N$ ; si $N=0$, c’est évident. Pour $n=3$ : $2187-3=2184=42\times 52$.
3. Démontrer que $42$ est le plus grand entier qui divise $n^7-n$ pour tout entier $n$. Plus grand facteur premier de $3^7-3$ :
   Rédaction attendue. Un entier $d$ qui divise $n^7-n$ pour tout entier $n$ divise en particulier $2^7-2=126=2\times 3^2\times 7$ et $3^7-3=2184=2^3\times 3\times 7\times 13$, donc leur PGCD $2\times 3\times 7=42$ : ainsi $d⩽42$. Comme $42$ convient (question précédente), c’est le plus grand. Le plus grand facteur premier de $2184$ est $13$.

Une autre démonstration du théorème. Soit $p$ un nombre premier et $a$ un entier non divisible par $p$. Pour $k=1,2,\dots ,p-1$, on note $r_k$ le reste de la division de $ka$ par $p$. On illustre avec $p=7$ et $a=5$.

1. Les restes de $5$, $10$, $15$, $20$ et $25$ modulo $7$ sont $5$, $3$, $1$, $6$ et $4$. Reste de $30$ modulo $7$ :
   $30=4\times 7+2$. Les six restes $5$, $3$, $1$, $6$, $4$, $2$ sont exactement les entiers de $1$ à $6$, dans un autre ordre.
2. Démontrer que les $r_k$ sont non nuls et deux à deux distincts. Pour $p=7$ et $a=5$, somme $r_1+r_2+\dots +r_6$ :
   Rédaction attendue. Si $r_k=0$, $p$ divise $ka$ ; par le lemme d’Euclide, $p$ divise $k$ ou $a$, impossible car $1⩽k⩽p-1$ et $p$ ne divise pas $a$. Si $r_k=r_j$ avec $1⩽j<k⩽p-1$, $p$ divise $ka-ja=(k-j)a$, donc $p$ divise $k-j$ ou $a$ : impossible car $1⩽k-j⩽p-2$. Les $p-1$ restes sont donc les entiers $1,2,\dots ,p-1$ dans un certain ordre. Pour $p=7$ : $1+2+\dots +6=21$.
3. En déduire que $(p-1)!a^{p-1}\equiv (p-1)![p]$, puis le petit théorème de Fermat. Reste de $6!=720$ dans la division par $7$ :
   Rédaction attendue. Le produit des $ka$ pour $k$ de $1$ à $p-1$ vaut $(p-1)!a^{p-1}$ ; il est congru au produit des restes $r_k$, qui vaut $(p-1)!$ d’après la question précédente. Or $p$ ne divise pas $(p-1)!=1\times 2\times \dots \times (p-1)$ : sinon, par le lemme d’Euclide, il diviserait un entier compris entre $1$ et $p-1$. Donc $p$ est premier avec $(p-1)!$ et divise $(p-1)!(a^{p-1}-1)$ : par le théorème de Gauss, $p$ divise $a^{p-1}-1$. Pour $p=7$ : $720=102\times 7+6$, le reste est $6$, non nul comme prévu.