\thumb

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex1

\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 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^3 \times 5^2 \times 13$. Le nombre de diviseurs de \numprint{8775} est donc\linebreak[4] $N = 4 \times 3 \times 2=24$.

Voir corrigé de l'exercice \ref{exNbDiv} pour une justification de ce calcul.

Sinon il \og suffit \fg{} d'écrire tous les diviseurs ... en faisant attention à ne pas en oublier !


\item 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
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 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,\linebreak $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}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex2

\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
Faux. 12 est divisible par 6 et 20 est divisible par 10, mais le PGCD de 12 et 20 est 4.

\item
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
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
 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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex3

\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
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
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
Faux. Si $a$ est multiple de $b$, par exemple $a=3b$, alors :\\
PGCD$(a,b)=b$.

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

 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex4

\begin{exo}{Divisibilité}{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}
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex5

\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}$.
    \par Ainsi $4$ divise $n$ si et seulement si $4$ divise $m$.

\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex6 [nouveau 2014]

\begin{exo}{Un algorithme}{Lycée  Jean-de-La-Fontaine, Paris}{1}{15}
On considère l'algorithme suivant :

\begin{algorithme}
Variables 
\qquad n, u entiers
Entrée
\qquad Saisir la valeur de n
Traitement
\qquad u prend la valeur abs(n)
\qquad Tant que u $\geqslant$ 11
\qquad\qquad u prend la valeur u - 11
\qquad Fin de Tant que
Sortie
\qquad Afficher u
Fin
\end{algorithme}

\begin{questions}
\item Qu'obtient-on si on exécute l'algorithme avec $n = 37$ ?
\item Que fait, de façon générale, cet algorithme ?
\item On exécute cet algorithme avec un entier naturel $a$ et on obtient 3.

On l'exécute ensuite avec un entier naturel $b$ et on obtient 5.

Qu'obtiendra-t-on si on l'exécute avec $3a + b$ ?
\item A-t-on le même résultat si $a$ et $b$ sont des entiers relatifs de signes contraires ?
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item 
\begin{itemize}
\item $u = 37$ ; $u\geqslant 11$, donc $u$ prend comme nouvelle valeur $37-11 = 26$ ;
\item $u\geqslant 11$, donc $u$ prend comme nouvelle valeur $26-11 = 15$ ;
\item $u\geqslant11$, donc $u$ prend comme nouvelle valeur $15-11 = 4$ ;
\item $u < 11$, donc on l'affiche. On obtient en sortie 4.
\end{itemize}

\item Cet algorithme donne le reste de la division euclidienne de la valeur absolue de $n$ par 11.

\item $a$ et $b$ sont égaux à leur valeur absolue puisque ce sont des entiers naturels.

Le reste de la division euclidienne de $a$ par 11 étant 3, on a : $a\equiv3 \pod{11}$.

On a de même $b\equiv5\pod{11}$.

Par conséquent, en utilisant les propriétés de la congruence, on a :
\[
3a + b\equiv  3\times 3 + 5 \pod{11}\;,\]
donc : 
\[
3a + b \equiv 14 \pod{11}
\] 
Le reste est par conséquent 3, qui est la valeur obtenue en sortie.

\item On n'aura pas le même résultat car, si $a$ et $b$ sont de signes différents, $3a + b\neq |3a|+|b|$.

Par exemple : supposons $a = 36$. Le reste de la division par 11 est bien 3.

Prenons $b = -16$ ; $u$ prend alors la valeur 16, et le reste de la division par 11 est bien 5.

On a $3a + b = 92$, et le reste de la division de 92 par 11 est 4.
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex7 (anc. 6)

\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 \label{chap16ex6_2}
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)$.

\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.
\end{align*}

\begin{align*}
\text{$x$ solution de  }(S) &\iff
\left\{\begin{aligned}&x=10+23u\quad (u\in\Z)\\ 
&u=18+7m\quad (m\in\Z) \quad\text{d'après \refitem{chap16ex6_2}}\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}

 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex8 (anc. 7)

\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$.
\Break
\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}
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex9

\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 :
\begin{align*}
    u &= p_{1}^{c_{1}} \times \cdots \times p_{k}^{c_{k}} \\
    v &= p_{1}^{d_{1}} \times \cdots \times p_{k}^{d_{k}}
\end{align*}
o\`u $c_{i}=0$ dans le cas o\`u le facteur premier $p_{i}$ ne figure 
pas dans la d\'ecomposition 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex10 (anc. 8)

\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\geq 5$, l'entier $p^2-1$ est divisible par $24$.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item\label{ch16ex10q1} 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\label{ch16ex10q2} 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 \geq 5$.

Les restes possibles dans la division de $p$ par $4$ sont sont $1$ ou $3$ (question \refitem{ch16ex10q1}) et ceux de la division de $p$ par $6$ sont $1$ ou $5$ (question \refitem{ch16ex10q2}).


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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex11 (anc. 10)


\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}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex12 (anc. 11)

\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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex13

\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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex14

\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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex15 [nouveau 2014]

\begin{exo}{\fontsize{12}{14}\selectfont Équations diophantiennes et algorithme}{Lycée Hoche, Versailles}{2}{20}
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}.
\]

\item Pour obtenir $a$, on a écrit l'algorithme suivant :

\Par

\begin{algorithme}
Initialisation
\qquad Affecter à p la valeur 0
Traitement 
\qquad Tant que ...
\qquad\qquad Affecter à p la valeur p + 1
\qquad Fin Tant que
Sortie
\qquad Afficher p
\end{algorithme}

\Par

Que doit-on écrire à la place des pointillés pour que l'algorithme affiche la valeur de l'entier $a$ ?
\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$.

\item La ligne incomplète est : \og Tant que $7p-1$ n'est pas divisible par 26 \fg.
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex16 [nouveau 2014]

\begin{exo}{Cryptographie et algorithme}{Lycée Charlemagne, Paris}{2}{25}

\subsubsectionnn{Partie A}

On considère l'algorithme suivant :

\begin{algorithme}
Variables
\qquad a est un entier naturel
\qquad b est un entier naturel
\qquad c est un entier naturel
Initialisation
\qquad c prend la valeur 0
\qquad Saisir la valeur de a
\qquad Saisir la valeur de b
Traitement
\qquad Tant que a $>$ b
\qquad\qquad Affecter à c la valeur c + 1
\qquad\qquad Affecter à a la valeur a - b
\qquad Fin de Tant que
Sortie
\qquad Afficher c 
\qquad Afficher a
\end{algorithme}

\begin{questions}
\item Faire fonctionner cet algorithme avec $a = 13$ et $b = 4$ en indiquant les valeurs des variables à chaque étape.

\item Que permet de calculer cet algorithme ?
\end{questions}

\subsubsectionnn{Partie B}

\`A chaque lettre de l'alphabet, on associe, grâce au tableau ci-dessous, un nombre entier compris entre 0 et 25.

\Par

\begin{tabularx}{\linewidth}{|*{13}{>{\centering\arraybackslash}X|}}
\hline\tabulartitle
A&B&C&D&E&F&G&H&I&J&K&L&M\\
\hline
0&1&2&3&4&5&6&7&8&9&10&11&12\\
\hline
\end{tabularx}

\begin{tabularx}{\linewidth}{|*{13}{>{\centering\arraybackslash}X|}}
\hline\tabulartitle
N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\
\hline
13&14&15&16&17&18&19&20&21&22&23&24&25\\
\hline
\end{tabularx}

\Par

On définit un procédé de codage de la façon suivante :

\begin{itemize}
\item Étape 1 : \`A la lettre qu'on veut coder, on associe le nombre $m$ correspondant dans le tableau.
\item Étape 2 : on calcule le reste de la division euclidienne de $9m + 5$ par 26 et on le note $p$.
\item Étape 3 : au nombre $p$ on associe la lettre correspondant dans le tableau.
\end{itemize}

\begin{questions}
\item Coder la lettre $U$.
\item Modifier l'algorithme de la partie A pour qu'à une valeur $m$ entrée par l'utilisateur, il affiche la valeur de $p$, calculée à l'aide du procédé de codage précédent.
\end{questions}

\subsubsectionnn{Partie C}

\begin{questions}
\item Trouver un nombre entier $x$ tel que $9x\equiv1\pod{26}$.
\item Démontrer alors l'équivalence : 
\[
9m+p\equiv p\pod{26}\Leftrightarrow m\equiv3p-15\pod{26}.\]
\item Décoder alors la lettre B.
\end{questions}
\end{exo}

\begin{corrige}
\subsubsectionnn{Partie A}

\begin{questions}
\item 
\begin{itemize}
\item $a > b$ donc $c$ prend la valeur 1 et $a$ prend la valeur $a-b = 9$ ;
\item $a > b$ donc $c$ prend la valeur 2 et $a$ prend la valeur $9-4 = 5$ ;
\item $a > b$ donc $c$ prend la valeur 3 et $a$ prend la valeur $5-4 = 1$ ;
\item $a < b$ donc on sort de la boucle ;
\item On affiche $c = 3$ et $a = 1$.
\end{itemize}

\item Cet algorithme donne le quotient ($c$) et le reste ($a$) dans la division euclidienne de $a$ par $b$ (la valeur initiale de $a$ est perdue).
\end{questions}

\subsubsectionnn{Partie B}

\begin{questions}
\item \`A \og U \fg{} correspond $m = 20$. Alors, 
\begin{align*}
9m+5 & = 185\\
& =27\times6+3\;,
\end{align*}
donc $p = 3$, et la lettre correspondante est \og D \fg.

\newpage

\item Voici un algorithme qui convient :

\begin{algorithme}
Variables
	m est un entier naturel
	a est un entier naturel
	b est un entier naturel
Initialisation
	c prend la valeur 0
	Saisir la valeur de m
Traitement
	Tant que 3m + 5 $>$ 26
		Affecter à c la valeur c + 1
		Affecter à m la valeur m - 26
	Fin de Tant que
Sortie
		Afficher m
\end{algorithme}
\end{questions}

\subsubsectionnn{Partie C}

\begin{questions}
\item \og 3 \fg{} convient car $9\times3=27$ et $27\equiv1\pod{26}$.
\item $\begin{aligned}[t]
9\times3\equiv1\pod{26} & \Leftrightarrow 9\times3\times m\equiv  m\pod{26}\\
 & \Leftrightarrow 3(9m)\equiv  m\pod{26}\\
 & \Leftrightarrow 3(p-5)\equiv  m\pod{26}\quad\text{ car }9m + 5\equiv  p\pod{26}\\
 & \Leftrightarrow 3p-15\equiv  m\pod{26}      
\end{aligned}$

\item \og B \fg{} correspond au nombre 1, donc $p=1$. Alors, $3p-15=-12$, et $-12\equiv14\pod{26}$.

Donc la valeur de $m$ est 14 et la lettre qui avait été encodée est O.
\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ex17 (anc. 18)

\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
