\thumb

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{vf}{Divisibilité dans \N} {10}

Parmi les propositions suivantes, quelles sont celles qui sont exactes ?
\begin{questions}
\item
Le nombre \numprint{8775} possède 12 diviseurs.

\item
Pour tout entier naturel $n$, l'entier $N=n^5-n$ est divisible par 30.

 \item
 L'équation $65x-20y=1$ n'a pas de solutions dans $\Z^2$.
 
\item
L'entier $80 \times 5^{469} -1$ est multiple de 7.
\end{questions}
\end{vf}


\begin{corrige}
\begin{questions}
\item \textit{Faux}. L'entier \numprint{8775} possède 24 diviseurs. Pour calculer le nombre de diviseurs de \numprint{8775}, on le décompose en produit de facteurs premiers : $\numprint{8775}=3^{\color{DR}3} \times 5^{\color{DB}2} \times 13^{\color{DG}1}$. Le nombre de diviseurs de \numprint{8775} est donc\linebreak[4] $N = ({\color{DR}3}+1)\times({\color{DB}2}+1)\times({\color{DG}1}+1) =4 \times 3 \times 2=24$.


\item \textit{Vrai}. Si $n=0$ ou $n=1$, alors $N=0$ donc $N$ est bien divisible par 5. Si $n>1$, on écrit $N$ sous forme factorisée : $N=n(n-1)(n+1)(n^2+1)$. On remarque que le nombre $n(n-1)(n+1)$ est le produit de trois entiers consécutifs donc il est toujours pair et multiple de 3 donc divisible par 6. Il ne reste plus qu'à prouver que $N$ est toujours multiple de 5 pour pouvoir conclure.

\begin{itemize}
\item Si $n = 5k$, $n$ est évidemment divisible par 5 ;
\item Si $n=5k+1$ avec $k\in \N$, alors $n-1$ est multiple de 5 donc $N$ aussi ;
\item Si $n=5k+4$ avec $k\in \N$, alors $n+1$ est multiple de 5 donc $N$ aussi ;
\item Si $n=5k+2$ avec $k\in \N$, alors $n^2+1$ est multiple de 5 donc $N$ aussi ;
\item Si $n=5k+3$ avec $k\in \N$, alors $n^2+1$ est multiple de 5 donc $N$ aussi.
\end{itemize}

On peut donc conclure que, pour tout entier naturel $n$, $N$ est à la fois divisible par 6 et par 5. Comme 5 et 6 sont premiers entre eux, il en résulte que $N$ est divisible par leur produit 30.


\item \textit{Vrai}. En effet, 5 divise 65 et 20 donc il divise $65x-20y$. Or 5 ne divise par 1 donc il n'existe pas d'entiers relatifs $x$ et $y$ tels que  $65x-20y=1$.
 
\item \textit{Vrai}. On a $5^6=\numprint{15625}$, donc $5^6\equiv  1 \pod{7}$. Or, $469 = 6\times78 + 1$. Donc $5^{469} = \left(5^6\right)^{78}\times5$. Par conséquent,$5^{469}\times5\equiv 5 \pod{7}$.

Or, $80\equiv 3 \pod{7}$ donc $80 \times 5^{469} \equiv 1 \pod{7}$. 

L'entier $80 \times 5^{469}-1$ est donc un multiple de 7.
\end{questions}
\end{corrige}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{vf}{PGCD} {10}

Parmi les propositions suivantes, quelles sont celles qui sont exactes ?
\begin{questions}
\item
Si deux entiers naturels sont divisibles respectivement par 6 et 10, alors leur PGCD est 2.

\item
Soit $a$ et $b$ deux entiers naturels non nuls, s'il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=2$, alors le PGCD de $a$ et de $b$ est 2.

\item
Si $n \equiv 1 \pod {7} $ alors PGCD$(3n+4,4n+3)=7$.

 \item Le PGCD de $a$ et $b$ est le plus grand diviseur de $a+b$ qui ne soit pas égal à $a+b$.

\end{questions}
\end{vf}


\begin{corrige}
\begin{questions}
\item \textit{Faux}. 12 est divisible par 6 et 20 est divisible par 10, mais le PGCD de 12 et 20 est 4.

\item \textit{Faux}. On considère les entiers $a=3$ et $b=4$. On prend $u=6$ et $v=-4$. On a alors $au+bv=2$, alors que le PGCD de $a$ et de $b$ est 1.


\item \textit{Vrai}. Comme $n \equiv 1 \pod {7} $ alors il existe un entier $k$ tel que $n=7k+1$. On a alors $3n+4=21k+7=7(3k+1)$ et $4n+3=28k+7=7(4k+1)$ donc les entiers $3n+4$ et $4n+3$ sont tous les deux divisibles par 7. Il reste à prouver que $3k+1$ et $4k+1$ n'ont aucun diviseur commun. 

On remarque que $4(3k+1)-3(4k+1)=1$ donc, d'après le théorème de Bézout, les entiers $3k+1$ et $4k+1$ sont premiers entre eux. Par suite, on a bien PGCD$(3n+4,4n+3)=7$.

\item \textit{Faux}. Le PGCD de $a$ et $b$ est bien un diviseur de $a+b$, mais ce n'est pas toujours le plus grand diviseur propre. Pour $a=6$ et $b=4$, le PGCD de $a$ et $b$ est 2, mais la somme $a+b=10$ est divisible par 5.
\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{vf}{Nombres premiers} {10}

Parmi les propositions suivantes, quelles sont celles qui sont exactes ?
\begin{questions}
\item
Si $p$ est premier, alors $p^3+2$ aussi.

\item
Si les entiers $a$ et $b$ sont premiers entre eux, alors $a+b$ et $a-b$ le sont aussi.

 \item
 Si $b$ est premier, alors pour tout entier naturel $a$ non nul,\\ 
 PGCD$(a,b)=1$.
 
\item
Si $p$ est premier, alors l'entier $N=3^p-p$ est divisible par $p$.
\end{questions}
\end{vf}


\begin{corrige}
\begin{questions}
\item \textit{Faux}. Il suffit de choisir $p=2$. On a alors $p^3+2=10$. L'entier $p$ est bien premier mais $p^3+2$ ne l'est pas.

\item \textit{Faux}. Choisissons $a=17$ et $b=15$, les entiers $a$ et $b$ sont premiers entre eux. Cependant, comme $a+b=32$ et $a-b=2$, les entiers $a+b$ et $a-b$ ne sont pas premiers entre eux.

\item \textit{Faux}. Si $a$ est multiple de $b$, par exemple $a=3b$, alors :\\
PGCD$(a,b)=b$.

 
\item \textit{Faux}. Contre-exemple pour $p=2$: le nombre $N=7$, n'est pas divisible par 2.
\end{questions}
\end{corrige}

\sectionnn{Divisibilité et congruences} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Divisibilité par 9}{Lycée Marie Curie, Sceaux}{1}{15}

\begin{questions}
    \item Montrer que pour tout $n$ entier positif, on a : 
    $10^n\equiv 1 \pod{9}$.
    \item En déduire que si $n$ s'écrit $10\times u+v$, alors $n$ est divisible par $9$ si et seulement si $u+v$ est divisible par $9$.
    \item En déduire un critère de divisibilité par $9$.
\end{questions}

\end{exo}

\begin{corrige}
\begin{questions}
   \item D'après la compatibilité de la multiplication avec la 
   congruence et comme $10 \equiv 1 \pod{9}$, on a :
   \[
   10^n \equiv 10\times 10\times \cdots \times 10 \equiv 1\times 
   1\times \cdots \times 1 \equiv 1 \pod{9}.
   \]
   
    \item Il suffit de voir que l'on a :
   \[
   10u+v \equiv u+v \pod {9}.
   \]
   Donc l'un des membres est congru à {0} modulo 9 si et seulement si l'autre 
   membre est congru à $0$ modulo 9.
   
  \item Comme la relation de congruence est compatible avec la 
   multiplication, nous avons, pour tout entier $n$ positif, la 
   relation suivante :
   \[
   10^n \equiv 1 \pod{9}.
   \]
   Écrivons $n=a_0\times10^0+a_1\times10^1+a_2\times10^2+ \cdots + 
   a_n\times10^n$ en base $10$, comme la relation de congruence est 
   compatible avec l'addition, nous obtenons
   \[
   n \equiv a_0+a_1+a_2+ \cdots +a_n 
   \pod{9}.
   \]
   Ainsi $9$ divise $n$ si et seulement si $9$ divise la somme des  chiffres qui composent $n$ en base 10.
\end{questions}
\newpage
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Critère de divisibilité par 4}{Lycée Arago, Perpignan}{1}{10}

   Montrer qu'un entier est divisible par $4$ si et seulement si le 
   nombre constitué de ses deux derniers chiffres en base $10$ est 
   divisible par $4$.
\end{exo}

\begin{corrige}
Écrivons un entier $n=a_na_{n-1}a_{n-2} \ldots a_0$ en base 10. Posons en base $10$, $m=a_1a_0$ et $p=a_na_{n-1}\ldots a_2$. Nous  avons l'égalité $n=100p+m$. Comme $100 \equiv 0 \pod {4}$, nous pouvons affirmer que $n \equiv m \pod {4}$.

Ainsi $4$ divise $n$ si et seulement si $4$ divise $m$.
\end{corrige}

%%% 2026

\begin{exo}{Inverse modulo 19}{Lycée François Rabelais, Saint-Brieux\newexo}{1}{10}
\begin{questions}
\item Justifier que 8 est un inverse de 12 modulo 19.
\item En déduire l'ensemble des solutions entières de l'équation $8x \equiv 7 \pod{19}$.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Petit rappel: $a$ est un inverse de $b$ modulo $p$ signifie que $ab \equiv 1 \pod{p}$.

On a: $8 \times 12 = 96 = 5 \times 19 + 1$ donc $8 \times 12 \equiv 1 \pod{19}$.

Ainsi, 8 est bien un inverse de 12 modulo 19.

\item $\begin{aligned}[t]
8x \equiv 7 \pod{19} & \iff 12 \times 8x \equiv 12\times7 \pod{19}\\
& \iff 96x \equiv 84 \pod{19}\\
& \iff x \equiv 8 \pod{19}.
\end{aligned}$
\Par
L'ensemble solution de l'équation $8x \equiv 7 \pod{19}$ est donc:
\[
\mathcal{S} = \{ 8 + 19k,\ k\in\Z \}
\]
\end{questions}
\end{corrige}

%%% 2026

\begin{exo}{Divisibilité de polynômes}{Lycée François Rabelais, Saint-Brieuc\newexo}{2}{10}
Déterminer les entiers relatifs $n$ tels que
$3n-2$ divise $n-4$
\end{exo}

\begin{corrige}

\begin{methode}
Pour trouver toutes les valeurs de $n$ telles que $an+b$ divise $n+p$, on \og fabrique \fg{} à partir de $n+p$ une expression ui ressemble à $an+b$.
\end{methode}

Supposons que $3n-2$ divise $n-4$.

Alors, $3n-2$ divise tout multiple de $n-4$, en particulier $3(n-4)=3n-12$.

$3n-2|3n-2$ et $3n-2|3n-12$ donc $3n-2$ divise $(3n-2)-(3n-12)$, soit $10$. 

Or, les diviseurs de 10 sont $-10$, $-5$, $-2$, $-1$, 1, 2, 5 et 10. Faisons alors une disjonction de cas:
\begin{itemize}
\item $3n-2=-10 \iff n = -\dfrac{8}{3} \not\in\Z \to$ ne convient pas.
\item $3n-2=-5 \iff n = -1 \in\Z \to$ convient.
\item $3n-2=-2 \iff n = 0 \in\Z \to$  convient.
\item $3n-2=-1 \iff n = \dfrac{1}{3} \not\in\Z \to$ ne convient pas.
\item $3n-2=1 \iff n = 1 \in\Z \to$ convient.
\item $3n-2=2 \iff n = \dfrac{4}{3} \not\in\Z \to$ ne convient pas.
\item $3n-2=5 \iff n = \dfrac{7}{3} \not\in\Z \to$ ne convient pas.
\item $3n-2=10 \iff n = 4  \in\Z \to$ convient.
\end{itemize}

Nous trouvons donc que les seules valeurs de $n$ qui conviennent sont: 
\[
n \in \{ -1;0;1;4\}.
\]

\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Divisibilité par 24}{Lycée Jean-Baptiste Say, Paris}{2}{20}

\begin{questions}
  \item Quels sont les restes possibles de la division d'un nombre premier $p$ par~$4$?
  \item Quels sont les restes possibles de la division d'un nombre premier $p$ par~$6$?
  \item En déduire que pour tout nombre premier $p\geqslant 5$, l'entier $p^2-1$ est divisible par $24$.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Le reste ne peut être  $0$, $p$ serait divisible par $4$ (ce qui n'est pas possible puisque $p$ est premier), le reste peut être $1$. 

Si le reste est 2, $p=4k+2=2(2k+1)$. Ce nombre n'est premier que si $2k+1=1$, soit $k=0$ ; alors $p = 2$. 

Enfin le reste peut être $3$.

\item Le reste ne peut être 0, car alors $p$ serait divisible par 6, il peut être 1. Si le reste est 2, 
$p = 6k + 2 = 2(3k +1)$. Ce nombre n'est premier que si $3k + 1 = 1$, soit si $k = 0$, et alors $p = 2$.

Si le reste est 3, $p = 6k + 3 = 3(2k + 1)$ ; ce nombre n'est premier que si $2k + 1 = 1$, soit si $k = 0$, et alors $p = 3$. Le reste 4 n'est pas possible : en effet si $p = 6k + 4$, $p = 2(3k + 2)$ ; ce nombre ne peut être premier car il n'existe pas de valeur de $k$ telle que $3k + 2 = 1$. 5 est un reste possible.


\item  Soit $p$ un nombre premier tel que $p \geqslant 5$.

Les restes possibles dans la division de $p$ par $4$ sont sont $1$ ou $3$ (question 1) et ceux de la division de $p$ par $6$ sont $1$ ou $5$ (question 2).


On doit donc \'etudier quatre cas.

\begin{itemize}
    \item  Cas 1.
    \[
    p \equiv 1\pod{4} \quad \text{et} \quad p \equiv 1\pod{6}.
    \]
    Il existe alors deux entiers naturels $n_{1}$ et $n_{2}$ tels que :
    \[
    p = 4 n_{1} + 1 \quad \text{et}\quad p=6n_{2}+1.
    \]
    On a donc :
    \[ 4n_{1}+1 = 6n_{2}+1\;, \]
    d'o\`u :
    \[ 2n_{1} = 3n_{2}. \]
    Comme $2$ divise $3n_{2}$ et est premier avec $3$, il r\'esulte du th\'eor\`eme de Gauss que $n_{2}$ est pair.
    
    Il existe donc un entier naturel $k$ tel que $n_{2}=2k$.
    
    On a alors :
    \[ 
    p = 12 k + 1 \quad\text{et}\quad p^{2} - 1 = 24 (6k^2+k)\;,
    \]
    ce qui montre que $p^{2}-1$ est divisible par $24$.

    \item  Cas 2.
    \[ 
    p \equiv 3\pod{4} \quad\text{et}\quad p \equiv 5\pod{6}.
    \]
    Il existe alors deux entiers naturels $n_{1}$ et $n_{2}$ tels que :
    \[
    p = 4 n_{1} + 3 \quad \text{et}\quad p=6n_{2}+5.
    \]
    On a donc :
    \[ 4n_{1}+3 = 6n_{2}+5\;, \]
    d'o\`u :
    \[ 2n_{1} = 3n_{2}+1.\]
    Par cons\'equent, $3n_{2}+1$ est pair, donc $3n_{2}$ est impair.
    
    L'entier $n_{2}$ \'etant alors impair, il existe un entier $k$ tel que $n_{2}=2k+1$.
    
    On en d\'eduit que :
    \[
    p^{2} - 1 = (12k+11)^{2} - 1 = 24 (k+1)(6k+5)\;,
    \]
    ce qui montre que $p^{2}-1$ est divisible par $24$.
    

    \item  On \'etudierait de m\^eme le cas 3 :
    \[
    p \equiv 1\pod{4} \quad\text{et}\quad p \equiv 5\pod{6}
    \]
    et le cas 4 :
    \[
    p \equiv 3\pod{4} \quad\text{et}\quad p \equiv 1\pod{6}.
    \]
\end{itemize}
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Critère de divisibilité par 7}{Lycée Buffon, Paris}{2}{20}

 Soit $a<\numprint{10000}$. On peut l'écrire en base $10$ :
 \[a=a_3a_2a_1a_0\qquad\text{ avec }\qquad a_i \in [\![0~;9]\!].\]
 Posons $u=2a_3+a_1$ et $v=2a_2+a_0$.
 \par 
Montrer que $a$ est divisible par $7$ si et seulement si $3u+v$ est divisible par $7$.
\end{exo}

\begin{corrige}
    Remarquons que :
    \begin{equation*}
        10 \equiv 3 \pod{7}\,,\quad
        100 \equiv 2 \pod{7}\quad\text{et}\quad
        1000 \equiv 6 \pod{7}.
        \end{equation*}
    Donc $a_3a_2a_1a_0 \equiv a_0+3a_1+2a_2+6a_3 \pod {7}$, le membre de gauche est congru à $0$ si et seulement si le membre de droite l'est.
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Chiffres des unités d'une puissance}{Lycée Montesquieu, Herblay}{2}{15}
\begin{questions}
\item Déterminer le plus petit entier naturel $p$ non nul tel que \ $7^p\equiv 1\pod{10}$.
\item Trouver le chiffre des unités dans l'écriture décimale de :
\[
A=\numprint{1997}^{\numprint{1999}^{\numprint{2001}}}.
\]
\end{questions}
\end{exo}
 
\begin{corrige}
 \begin{questions}
\item On a successivement :
\begin{align*}
7&\equiv 7\pod{10} &7^2&\equiv49\equiv 9\pod{10}\\
 7^3&\equiv 7\times 9\equiv 3\pod{10} &7^4&\equiv 7\times 3\equiv 1\pod{10}
\end{align*}
donc $p=4$. 
\item Bien sûr :
\[ A\equiv 7^{\numprint{1999}^{\numprint{2001}}}\pod{10}.\]
Notons $r$ le reste de la division euclidienne de $\numprint{1999}^{\numprint{2001}}$ par 4, on a :
\[A\equiv 7^r\pod{10}.\]
Or, $\numprint{1999}\equiv 3\pod{4}$ donc il faut simplifier $3^{\numprint{2001}}\pod{4}$. 
\par 
Comme $3^2=9\equiv 1\pod{4}$, il vient $3^{\numprint{2001}}\equiv 3^1\pod{4}$. Alors :
\[A\equiv 7^3\pod{10}\qquad\text{donc}\qquad A\equiv 3 \pod{10}.\]
Le chiffre des unit\'es dans l'\'ecriture d\'ecimale de $A$ est $3$.
\end{questions}
 \end{corrige}


\sectionnn{PGCD}

\begin{exo}{Calcul de PGCD}{Lycée Charlemagne, Paris}{1}{10}
En utilisant l'algorithme d'Euclide, calculer le PGCD des nombres suivants.
\begin{questions}
\begin{multicols}{2}
\item \numprint{2070} et 432
\item \numprint{1065} et 235
\item 363 et 792
\item 858 et 910
\end{multicols}
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\begin{multicols}{2}
\item $\begin{aligned}[t]
\numprint{2070} & = 4 \times 432 + 342\\
 432 & = 1 \times 342 + 90\\
 342 & = 3 \times  90 + 72\\
  90 & = 1 \times  72 + 18\\
  72 & = 4 \times  18 + 0.
\end{aligned}$

\Par

Ainsi, $\PGCD(\numprint{2070},432)=18$.

\item $\begin{aligned}[t]
\numprint{1065} & = 4 \times 235 + 125\\
 235 & = 1 \times 125 + 110\\
 125 & = 1 \times 110 + 15\\
 110 & = 7 \times  15 + 5\\
  15 & = 3 \times   5 + 0.
\end{aligned}$

\Par

Ainsi, $\PGCD(\numprint{1065},235)=5$.
\end{multicols}
\end{questions}


\begin{questions}
\setcounter{enumi}{2}
\begin{multicols}{2}
\item $\begin{aligned}[t]
792& = 2 \times 363 + 66\\
 363 &= 5 \times  66 + 33\\
  66 &= 2 \times  33 + 0.
\end{aligned}$

\Par

Ainsi, $\PGCD(792,363)=33$.

\item $\begin{aligned}[t]
910 &= 1 \times 858 + 52\\
 858 &= 16 \times  52 + 26\\
  52 &= 2 \times  26 + 0.
\end{aligned}$

\Par

Ainsi, $\PGCD(910,858)=26$.
\end{multicols}
\end{questions}
\end{corrige}

%%%% 2026

\begin{exo}{Équation diophantienne}{Lycée François Rabelais, Saint-Brieuc\newexo}{1}{10}
Justifier que l'équation $322u + 238v = 266$ admet des solutions $(u ; v)$\linebreak d'entiers relatifs.
\end{exo}

\begin{corrige}
Calculons donc dans un premier temps $\PGCD(322,238)$:

\begin{align*}
322 & = 1 \times 238 + 84\\
238 & = 2 \times 84 + 70\\
84 & = 1 \times 70 + 14\\
70 & = 4 \times 14 + 0.
\end{align*}

Ainsi, $\PGCD(322,238)=14$.

Or, 14 divise 266 donc, d'après une propriété du cours sur les équations diophantiennes, l'équation $322u + 238v = 266$ admet des solutions entières car $\PGCD(322,238)$ divise 266.
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Entiers premiers entre eux}{Lycée Masséna, Nice}{1}{15}

 Soit $n$ un entier positif, montrer que $2n+3$ et  
 $n^2+3n+2$ sont premiers entre eux.
 \end{exo}
 
\begin{corrige}
 Remarquons tout d'abord que :
 \[
 n^2+3n+2=(n+1)(n+2)\]
 et \[ 2n+3=(n+1)+(n+2). \]
Or, si un entier $d$ divise deux entiers $a$ et $b$ alors il divise toute combinaison linéaire à coefficients entiers de ces deux entiers.\par
Posons $a=2n+3$ et $b=n^2+3n+2$. \par
Soit $d$ un diviseur commun à $a$ et $b$.\par
Alors $d$ divise $2b-(n+1)a$ soit $d$ divise $n+1$.\par
Mais alors $d$ divise aussi $(2n+3)-2(n+1)$ soit $d$ divise 1. On en déduit que $d=1$.
On peut alors conclure que le seul diviseur commun à $n^2+3n+2$ et $2n+3$ est 1, ce qui prouve que ces deux nombres sont premiers entre eux.

\begin{methode}
Pour montrer que deux entiers sont premiers entre eux, on dispose de quatre méthodes :
\begin{itemize}
\item
On utilise le théorème de Bezout : deux entiers $a$ et $b$ sont premiers entre eux si et seulement si il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=1$.
\item
On désigne par $d$ un diviseur commun aux deux entiers, puis, en utilisant des combinaisons linéaires judicieusement choisies de ces deux entiers, on montre que $d=1$.
\item
On montre, en le calculant (par exemple par l'algorithme d'Euclide), que le PGCD de ces deux entiers  est égal à 1.
\item
On utilise un raisonnement par l'absurde (on suppose que les deux entiers ne sont pas premiers entre eux et on montre que ceci conduit à une contradiction).
\end{itemize}
\end{methode}
\end{corrige}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{\'Equations diophantiennes}{Lycée Jean Monod, Clamart}{1}{20}
Il s'agit de résoudre le système
$(S)\;:\; \left\{\begin{aligned} x&\equiv 10\pod{23}\\ x&\equiv 4\pod{7}\end{aligned}\right.$

\begin{questions}
\item Déterminer un couple d'entiers $(\alpha~;\beta)$ solution de : $23\alpha+7\beta=1$.
\item En déduire un couple $(u_0~;v_0)$ solution de l'équation ci-dessous, puis résoudre complètement cette équation :
\[23u-7v=-6.\]
\item Démontrer que $x$ est solution de $(S)$  si et seulement s'il existe $(u~;v)$ couple d'entiers vérifiant : 
$\left\{\begin{aligned}&23u-7v=-6\\&x=10+23u \end{aligned} \right.$.

En déduire l'ensemble des solutions de $(S)$.
\item Déterminer la plus petite solution entier naturel $x_0$ divisible par $16$.
\end{questions} 
\end{exo}
 
\begin{corrige}
\begin{questions}
\item Appliquons l'algorithme d'Euclide : 
\begin{align*}
23 & = 7\times 3+2\\
7 & = 2\times 3+1.
\end{align*}
Alors, $2\times 3=7-1$. Multiplions par $3$ la première \'egalit\'e : 
\begin{align*}
23\times 3 & =7\times 9+2\times 3\\
& =7\times 9+7-1\\
& =7\times 10-1.
\end{align*}
Donc:
\[23\times 3-7\times 10=-1\;,\]
d'où :
\[23\times (-3)+7\times 10=1.\]

\begin{methode}
Comme 23 et 7 sont premiers entre eux, le théorème de Bézout assure l'existence d'un couple d'entiers $(\alpha,\beta)$ tels que $23\alpha+7\beta=1$.\par
L'algorithme d'Euclide permet ensuite de trouver un couple d'entiers répondant à la question.
\end{methode}

\item Alors en multipliant par $(-6)$ : \ $23\times 18 -7\times 60= -6$. Soit un couple d'entiers $(u~;v)$ vérifiant $23u-7v=-6$ :
\begin{align*}
23u-7v=-6 &\iff 23(u-18)-7(v-60)=0\\
&\iff 23(u-18)=7(v-60).
\intertext{Or, 23 et 7 sont premiers entre eux, d'où :}
23u-7v=-6 &\iff 23\mid (v-60)\quad\text{et}\quad 7\mid (u-18)\\
& \qquad\quad\text{et}\quad 
\frac{v-60}{23}=\frac{u-18}{7}\\
&\iff v=60+23m\quad\text{et}\quad u=18+7m\quad\text{avec $m\in\Z$.}
\end{align*}

Donc un couple vérifiant l'égalité est, par exemple, celui obtenu pour $m = 0$, soit $(60~; 18)$.

\enlargethispage*{2\baselineskip}

\item Soit un entier $x$ :
\begin{align*}
\text{$x$ solution de  }(S) & 
\iff \left\{
\begin{aligned}
& x=10+23u\quad (u\in\Z)\\ 
&10+23u\equiv 4\pod{7} 
\end{aligned}\right.
\\
&\iff \left\{
\begin{aligned}
& x=10+23u\quad (u\in\Z)\\ 
& 23u\equiv -6\pod{7} 
\end{aligned}\right.
\\
&\iff\left\{
\begin{aligned}
& x=10+23u\quad (u\in\Z)\\ 
& 23u=-6+7v\quad (v\in\Z) 
\end{aligned}\right.
\\
&\iff
\left\{\begin{aligned}&x=10+23u\quad (u\in\Z)\\ 
&u=18+7m\quad (m\in\Z)\end{aligned}\right.\\
&\iff x=10+23(18+7m)=424+161m\\
&\hphantom{\iff}\quad\text{pour un certain $m\in\Z$.}
\end{align*}
\item \hbox{}
{\small
 \bigskip
\[
\hspace*{-1cm}\begin{array}{c|c|c|c|c|c|c|c|c}
m&1&2&3&4&5&6&7&8\\
\hline
\begin{gathered}
  x\\=424+161m
\end{gathered}
&585&746&907&1068&1229&1390&1551&\begin{gathered}1712\\=16\times
107\end{gathered}
\end{array}
\]
}

La plus petite solution $x_{0}$ divisible par $16$ est $\numprint{1712}$.
\end{questions} 
\end{corrige}

%%% 2026

\begin{exo}{\'Equation diophantienne}{Lycée François Rabelais, Saint-Brieuc\newexo}{2}{15}
Résoudre dans $\Z^2$ l'équation $5x-17y=3$.
\end{exo}

\begin{corrige}
On nous demande ici de résoudre une équation diophantienne classique:
\[
5x-17y=3.
\]
\begin{itemize}
\item \'Etape 1: calcul de $\PGCD(5,17)$.
\Par
$\PGCD(5,17)=1$ car 5 et 17 sont premiers entre eux.

La propriété sur les équations diophantiennes nous assure donc l'existence de solutions à cette équation car $\PGCD(17,5)$ divise 3.

\item \'Etape 2: exploitation de l'algorithme d'Euclide.
\begin{align*}
17 & = 3 \times 5 + 2\\
5 & = 2 \times 2 + 1
\end{align*}
On en déduit, en remontant l'algorithme:
\begin{align*}
1 & = 5 - 2 \times 2\\
  & = 5 - (17 - 3\times5)\times2\\
  & = 7 \times 5 - 2\times 17.
\end{align*}
D'où:
\[
3 = 21 \times 5 - 6 \times 17.
\]
Ainsi, le couple $(x=21;y=6)$ est une solution particulière de l'équation $5x-17y=3$.

\begin{Remarque}on aurait aussi pu remarquer, sans faire appel à l'algorithme d'Euclide, que $5\times4 - 1\times17=3$ et ainsi obtenir un autre couple solution: $(4;1)$.
\end{Remarque}

\item \'Etape 3: utilisation de la solution particulière.
\Par
On a:
\begin{align*}
5x - 17y & = 3\\
5\times21 - 17\times2 & = 3
\end{align*}
Par différence, on déduit:
\[
5(x-21) - 17(y-2) = 0 \qquad \text{soit}\qquad 5(x-21)=17(y-2).
\]
Le fait que $\PGCD(17,5)=1$ nous assure, d'après le théorème de Gauss, que:
\[
5|(y-2)\qquad\text{et}\qquad 17|(x-21)
\]
soit:
\[
\forall k\in\Z,\quad 
\begin{cases}
y-2 &= 5k\\
x-21 &= 17k
\end{cases}
\iff
\begin{cases}
x=21+17k\\
y=2+5k
\end{cases}
\]
L'ensemble solution de l'équation $5x-17y=3$ est donc:
\[
\mathcal{S} = \{ 21+17k ; 2+5k)\quad,\quad k\in\Z\}.
\]
\end{itemize}

\end{corrige}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Équations diophantiennes}{Lycée Hoche, Versailles}{2}{15}
On considère l'équation :
\[ (E)\quad :\quad 7x-26 y = 1,\]
où $x$ et $y$ désignent deux entiers relatifs.

\begin{questions}
\item Vérifier que $(15~;4)$ est une solution de $(E)$, puis résoudre l'équation $(E)$.

\item En déduire l'unique entier $a$ tel que :
\[ 
0\leqslant a\leqslant25\qquad\text{et}\qquad7a\equiv 1 \pod{26}.
\]
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item $7\times15-26\times4=1$ donc le couple $(15~;4)$ est solution.

On a donc :
\[
\begin{cases}
7x-26y & =1\\
7\times15-26\times4 & =1
\end{cases}
\]
En soustrayant membre à membre, on obtient :
\[
7(x-15)-26(y-4)=0\;,\]
ou encore :
\[ 7(x-15) = 26(y-4).\]
26 divise le produit $7(x-15)$, et est premier avec 7, donc 26 divise $x-15$, et il existe $k$ tel que $x = 26k + 15$.

En reportant dans l'équation de départ, on a : 
\[ 7(26 k + 15) - 26y = 1\;,\]
soit :
\[ 26y = 182k + 104\;,\]
et donc $y = 7k + 4$.

On vérifie que les couples $(26k + 15~; 7k + 4)$ sont bien solutions en remplaçant dans l'équation de départ :
\[
7(26k + 15) -26(7k + 4) =  105 - 104 = 1.\]
Par conséquent, $S=\big\{(26k+15~;4+7k),\ k\in\Z\big\}$.

\item $a$ est une de valeur possible pour $x$. On veut donc trouver $k$ tel que $0\leqslant26k+16\leqslant25$. La seule valeur possible est $k = 0$, et alors $a = 15$.
\end{questions}
\end{corrige}

%%%%%%%%%%%%% 2026

\begin{exo}{Système et PGCD}{Lycée François Rabelais, Saint-Brieuc\newexo}{2}{15}
$x$ et $y$ désignent deux nombres entiers naturels non nuls tels que:
\[
(S)\,:\,\begin{cases}
x+y&=117\\
\PGCD(x;y)&=13
\end{cases}.
\]
\begin{questions}
\item Justifier que résoudre le système $(S)$ revient à résoudre le système:
\[
(S')\,:\,\begin{cases}
x'+y'&=9\\
\PGCD(x';y')&=1
\end{cases}.
\]
\item Résoudre le système $(S')$ puis déterminer l'ensemble des couples $(x;y)$ solutions de $(S)$.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item On a:
\begin{align*}
     & (x;y) \text{ est solution de }(S) \\
\iff & \exists(x';y')\in(\N^*)^2,\ \begin{cases}x=13x' \text{ et } y=13y' \text{ avec } \PGCD(x';y')=1\\
13x'+13y'=13\times9
\end{cases}\\
\iff & \exists(x';y')\in(\N^*)^2,\  \begin{cases}
x'+y'&=9\\
\PGCD(x';y')&=1
\end{cases}
\end{align*}

\item Recherchons les entiers naturels non nuls $x'$ et $y'$ premiers entre eux dont la somme vaut 9. On trouve:
\[
(1; 8);(2 ; 7);(4 ; 5);(5 ; 4);(7 ; 2);(8 ; 1).
\]
En multipliant chacune de ses valeurs par 13, on obtient les couples $(x;y)$ solutions de $(S)$:
\[
\mathcal{S} = \{ (13 ; 104)	 ; (28 ; 91) ; (52 ; 65) ; (65 ; 52) ; (91 ; 28) ; (104 ; 13) \}.
\]
\end{questions}
\end{corrige}

\sectionnn{Nombres premiers}

%%% 2026

\begin{exo}{Justification}{Lycée Jean Monod, Clamart\newexo}{1}{5}
Justifier que 353 est un nombre premier.
\end{exo}

\begin{corrige}
$\sqrt{353} \approx 17,8$ et les nombres premiers inférieurs à $\sqrt{353}$ (2, 3, 5, 7, 11, 13 et 17) ne divisent pas 353.
\Par
Ainsi, 353 est un nombre premier.
\end{corrige}

%%% 2026

\begin{exo}{PPCM et PGCD}{Lycée François Rabelais, Saint-Brieuc\newexo}{1}{5}
On donne les décompositions en produit de facteurs premiers suivantes:
\[
a=2 \times 5^3 \times 41 \times 43^3\qquad\text{et}\qquad b=2^4 \times 3 \times 5^5 \times 29^3.
\]
Déterminer $\PGCD(a;b)$ et $\PPCM(a;b)$.
\end{exo}

\begin{corrige}
\[
a=2 \times 5^3 \times 41 \times 43^3\qquad\text{et}\qquad b=2^4 \times 3 \times 5^5 \times 29^3.
\]
\begin{itemize}
\item Pour déterminer $\PGCD(a;b)$, on prend les diviseurs communs aux deux décompositions:
\[
\PGCD(a;b)=2 \times 5^3 = 250.
\]

\item Pour déterminer $\PPCM(a;b)$, on prend \textit{tous} les diviseurs des deux décompositions:
\[
\PPCM(a;b)=2^4 \times 3 \times 5^5 \times 29^3 \times 41 \times 43.
\]
\end{itemize}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Décomposition en facteurs premiers}{Lycée Jules Haag, Besançon}{1}{10}

   Soit $u$ et $v$ deux entiers premiers entre eux, avec $uv=n^2$.
   \par Montrer que $u$ et $v$ sont eux-mêmes des carrés.

\end{exo}

\begin{corrige}
Consid\'erons la d\'ecomposition de $n$ en produit de facteurs 
premiers :
\[
n = p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}
\]
o\`u $p_{1}$, \dots, $p_{k}$ sont des nombres premiers deux \`a deux 
distincts et $a_{1}$, \dots, $a_{k}$ sont des entiers naturels non 
nuls. On a alors :
\[
n^{2} =p_{1}^{2a_{1}} \times \cdots \times p_{k}^{2a_{k}}\;,
\]
soit, comme $n^{2}=uv$ :
\[
uv = p_{1}^{2a_{1}} \times \cdots \times p_{k}^{2a_{k}}.
\]
Comme $p_{1}$, \dots, $p_{k}$ sont des nombres premiers, la d\'ecomposition de $u$ et $v$ en produits de facteurs premiers est de la forme :
\[
    u = p_{1}^{c_{1}} \times \cdots \times p_{k}^{c_{k}} \quad\text{et}\quad
    v = p_{1}^{d_{1}} \times \cdots \times p_{k}^{d_{k}}
\]
o\`u $c_{i}=0$ dans le cas o\`u le facteur premier $p_{i}$ ne figure 
pas dans la décomposition de $u$, ou $c_{i} = 2a_{i}$ dans le cas contraire.

En effet, comme $u$ et $v$ sont premiers entre eux, ils ne peuvent avoir aucun facteur premier en commun.

On a de m\^eme $d_{i}=0$ ou $d_{i} = 2a_{i}$.

Dans tous les cas, pour tout entier $i$ compris entre $1$ et $k$, $c_{i}$ et $d_{i}$ sont pairs, donc $u$ et $v$ sont des carr\'es.
\end{corrige}

%%% 2026

\begin{exo}{Montrer une divisibilité}{Lycée François Rabelais, Saint-Brieuc\newexo}{2}{10}
Démontrer que pour tout entier naturel $k$, 7 divise $10^{6k+4}+3$.
\end{exo}

\begin{corrige}
Dès que l'on doit démontrer une divisibilité où il y a une puissance, on peut penser aux congruences.

$\PGCD(10;7)=1$ et 7 est un nombre premier; on peut alors appliquer le petit théorème de Fermat:
\[
10^{7-1} \equiv 1 \pod{7} \iff 10^{6} \equiv 1 \pod{7}
\]
En en déduit:
\[
\forall k\in\N,\quad \big(10^6\big)^k \equiv 1 \pod{7} \iff 10^{6k} \equiv 1 \pod{7} \ (1).
\]
De plus, $10 \equiv 3 \pod{7}$, d'où:
\[
10^4 \equiv 3^4 \pod{7}\qquad\text{soit}\qquad 10^4 \equiv 4 \pod{7}\ (2).
\]
Des congruences $(1)$ et $(2)$, on déduit:
\begin{align*}
10^{6k} \times 10^4 \equiv 1 \times 4 \pod{7} & \iff 
10^{6k+4} \equiv 4 \pod{7}\\
& \iff 10^{6k+4}+3 \equiv 4 + 3 \pod{7}\\
& \iff 10^{6k+4}+3 \equiv 0 \pod{7}.
\end{align*}
Ainsi, $10^{6k+4}+3$ est bien divisible par 7, quelle que soit la valeur de l'entier naturel $k$.
\end{corrige}

%%% 2026

\begin{exo}{Somme et congruence}{Lycée Jean Monod, Clamart\newexo}{2}{15}
Soit $n$ un nombre premier. Montrer que:
\[
1+1^{n-1} + 2^{n-1} + 3^{n-1} + \cdots + (n-1)^{n-1} \equiv 0\pod{n}.
\]
\end{exo}

\begin{corrige}
$n$ est un nombre premier donc, d'après le petit théorème de Fermat,
\[
\forall k\in\N,\ k<n,\ k^{n-1} \equiv 1 \pod{n}.
\]
On en déduit:
\begin{align*}
& \sum_{k=1}^{n-1} k^{n-1} \equiv \sum_{k=1}^{n-1} \pod{n} \\
\iff & 1^{n-1} + \cdots + (n-1)^{n-1} \equiv n-1 \pod{n} \\
\iff & 1^{n-1} + \cdots + (n-1)^{n-1} + 1 \equiv n \pod{n}\\
\iff & 1+ 1^{n-1} + \cdots + (n-1)^{n-1} \equiv 0 \pod{n}.
\end{align*}

\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Nombres premiers}{Lycée Masséna, Nice}{2}{20}
Soit $M_n=1111\ldots 111$, le nombre constitué en base $10$ par $n$ chiffres «$1$».\par 
Montrer que si $M_n$ est premier, $n$ est premier.
\end{exo}

\begin{corrige}
Le nombre $M_n$ est la somme des $n$ premiers termes de la suite géométrique de terme général :
\[
V_n=10^{n}, \quad M_n=\dfrac{10^{n}-1}{9}.
\]
Supposons que $n=pq$ avec $p$ et $q$ deux entiers. Nous pouvons écrire la décomposition en $M_n$ en deux facteurs :
\[
M_n=\left( \dfrac{10^{pq}-1}{10^{q}-1} \right) \left(
\dfrac{10^{q}-1}{10-1}
\right).
\] 
Ces deux termes sont des entiers (sommes des premiers termes de suites géométriques à termes entiers).
\par
Comme $M_n$ est premier, l'un de ces termes vaut $1$, ce qui correspond à $p=1$ ou à $q=1$. Donc $n$ est premier.
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{\'Equation du second degré dans $\Z$}{Lycée Guy de Maupassant, Fécamp}{2}{15 }

Soit $p$ un nombre entier.

Trouver les couples $(x~;y)$ tels que $x^2 - y^2 = p$.
\end{exo}

\begin{corrige}
Factorisons le premier membre de l'équation : $p=(x+y)(x-y)$. 

Comme $p$ est un nombre premier, l'un des deux facteurs est égal à 1 ou à $-1$.

On a donc 4 possibilités :

\begin{itemize}
\item $x + y = 1$, et alors $x-y = p$ ; on a donc $x=\dfrac{1+p}{2}$ et $y=\dfrac{1-p}{2}$, $p$ étant un nombre premier. Les solutions sont les couples $\left(\dfrac{1+p}{2}~;\dfrac{1-p}{2}\right)$, $p$ étant un nombre premier.

\item $x-y = 1$ et alors $x + y = p$ ; les solutions sont alors les couples de la forme $\left(\dfrac{1+p}{2}~;\dfrac{p-1}{2}\right)$, $p$ étant un nombre premier.

\item $x + y = -1$, et alors $x-y = -p$ ; les solutions sont alors les couples de la forme $\left(\dfrac{-p-1}{2}~;\dfrac{p-1}{2}\right)$, $p$ étant un nombre premier.

\item $x-y = -1$, et alors $x + y = -p$ et $y = -x-p$ ; les solutions sont alors les couples de la forme $\left(\dfrac{-p-1}{2}~;\dfrac{1-p}{2}\right)$, $p$ étant un nombre premier.
\end{itemize}
\end{corrige}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% supprimé pour manque de place

%\begin{exo}{Nombre de diviseurs d'un entier}{Lycée Courbet, Belfort}{3}{20 }\label{exNbDiv}
%\begin{questions}
% \item Soit $a$ un entier dont $p_{1}^{a_1}\cdots p_{k}^{a_k}$ est la décomposition en facteurs premiers. 
% \par Montrer que le nombre de diviseurs positifs de $a$ est $(1+a_1)\cdots (1+a_k)$.
% \item Supposons que $a=2^n(2^{n+1}-1)$ avec $2^{n+1}-1$ premier.\par 
% Montrer qu'alors la somme des diviseurs positifs de $a$ vaut $2a$.
%\end{questions}
%\end{exo}
%
%\begin{corrige}
%\begin{questions}
%\item Un diviseur $d$ positif de $a$ s'écrit de façon unique 
%   $p_1^{d_1}\cdots p_k^{d_k}$ avec pour tout $i$, $0\leqslant d_i\leqslant a_i$.
%   \par Il y a donc autant de diviseurs de $a$ que de mots de longueur $k$ que l'on peut écrire avec $a_i+1$ symboles à la place $d_i$, cela fait donc\\
%   $(1+a_i)\cdots(1+a_k)$ mots possibles. Ce qui revient à dire que le nombre de diviseurs positifs de $a$  est : $(1+a_i)\cdots(1+a_k)$.
%\item Notons $P=2^{n+1}-1$. On applique le résultat ci-dessus et l'on trouve qu'il y a exactement $2(n+1)$ diviseurs de $a$ que l'on peut lister naïvement comme suit :
%   \[
%   1,2, \ldots 2^n, P, 2P, \ldots 2^nP.
%   \]
%   La somme des diviseurs vaut donc :
%   \[(1+P)(2^{n+1}-1)=2 \times 2^n(2^{n+1}-1)=2a. \]
%\end{questions}
%\end{corrige}


\thumb
\AfficheCorrige
\endinput
