\chapter{Multiples, diviseurs et nombres premiers}

\newpage

Dans ce chapitre, nous allons nous intéresser principalement aux nombres entiers.

\section{Multiples et diviseurs}

\subsection{Définitions}

\begin{defin}
Soit $n$ un nombre entier (naturel ou relatif).
\begin{itemize}
\item On appelle \textbf{diviseurs} de $n$ tous les nombres entiers $q$ tels que le quotient de $n$ par $q$ est entier.

\item On appelle \textbf{multiples} de $n$ tous les nombres de la forme $k \times n$, où $k$ est entier.
\end{itemize}
\end{defin}

\begin{exemple}
\begin{enumerate}
\item 2 est un diviseur de 12 car $\dfrac{12}{2}=6$ et 6 est un nombre entier.
\item 45 est un multiple de 9 car $45=5 \times 9$.
\end{enumerate}
\end{exemple}

\begin{rem}
Si $q$ est un diviseur de $n$ alors on dit que $n$ est \textit{divisible} par $q$.
\end{rem}

\subsection{Critères de divisibilité}

\begin{defin}
Un \textbf{critère de divisibilité} est une règle permettant de savoir si un entier est divisible par un autre entier.
\end{defin}

\subsubsection{Critère de divisibilité par 2}

\begin{prop}
Un entier est divisible par 2 si son chiffre des unités est 0, 2, 4, 6 ou 8.
\end{prop}
\enlargethispage*{2em}

\begin{exemple}
\begin{enumerate}
\item 78 est divisible par 2 car son chiffre des unités est 8.
\item 106 est divisible par 2 car son chiffre des unité est 6.
\end{enumerate}\end{exemple}

\begin{rem}
Quand un entier est divisible par 2, on dit qu'il est pair.

Sinon, on dit qu'il est impair.
\end{rem}

\newpage
\begin{prop}
Si $n$ est pair alors il existe un entier $k$ tel que $n=2k$.

Si $n$ est impair alors il existe un entier $k$ tel que $n=2k+1$.
\end{prop}

\subsubsection{Critère de divisibilité par 3}

\begin{prop}
Un entier est divisible par 3 si la somme de ses chiffres est elle-même divisible par 3.
\end{prop}

\begin{exemple}\begin{enumerate}
\item 123 est divisible par 3 car la somme de ses chiffres est $1+2+3=6$, et 6 est divisible par 3.
\item \numprint{10101} est divisible par 3 car la somme de ses chiffres $1+0+1+0+1=3$ est divisible par~3.
\end{enumerate}\end{exemple}

\subsubsection{Critère de divisibilité par 5}

\begin{prop}
Un entier est divisible par 5 si son chiffre des unités est 0 ou 5.
\end{prop}

\begin{exemple}\begin{enumerate}
\item 125 est divisible par 5 car son chiffre des unités est 5.
\item \numprint{10100} est divisible par 5 son chiffre des unités est 0.
\end{enumerate}\end{exemple}


\subsubsection{Un propriété importante}

\begin{prop}
Soient $p$ et $q$ deux entiers premiers entre eux. Un entier $n$ est divisible par $p \times q$ si et seulement si il est divisible par $p$ et par $q$.
\end{prop}

\begin{exemple}\begin{enumerate}
\item 312 est divisible par 2 et par 3 donc il est divisible par 6.
\item 455 est divisible par 35 donc il est divisible par 7 et par 5.
\end{enumerate}\end{exemple}

\subsection{Somme de deux multiples}

\begin{prop}
Soient $a$ un entier relatif.

Soient $m$ et $n$ deux entiers multiples de $a$.

\medskip

Alors $m+n$ est un multiple de $a$.
\end{prop}

\begin{demo}
$m$ est un multiple de $a$ donc il existe un entier $k$ tel que $m=ka$.

De même, $n$ est un multiple de $a$ donc il existe un entier $k'$ tel que $n=k'a$.

Ainsi,
\[
m+n=ka+k'a=(k+k')a.
\]
Or, $k$ et $k'$ sont entiers, donc $k+k'$ aussi. Ainsi, $(k+k')a$ est un multiple de $a$. 

Donc $m+n$ est un multiple de $a$.
\end{demo}

\subsection{Carré d'un nombre impair}

\begin{prop}
Soit $a$ un nombre impair.

Alors, $a^2$ est impair.
\end{prop}

\begin{demo}
Si $a$ est impair alors il existe un entier $k$ tel que:
\[
a = 2k+1.
\]
Ainsi,
\[
a^2=(2k+1)^2=(2k)^2+2\times2k\times1 + 1^2=4k^2+4k+1=2(2k^2+2k) + 1.
\]
Donc $a^2$ est de la forme $2N+1$, avec $N=2k^2+2k$. $a$ est donc impair.
\end{demo}

\newpage
\section{ppcm et pgcd}

\subsection{ppcm}

\begin{defin}
Soient $a$ et $b$ deux entiers.

On appelle \textbf{ppcm} (plus petit commun multiple) de $a$ et $b$ le plus petit nombre $m$ qui est à la fois multiple de $a$ et de $b$.

\medskip

On le note $\ppcm{a}{b}$.
\end{defin}

\begin{exemple}
Si $a=6$ et $b=15$ alors $\ppcm{6}{15}=30$ car:
\begin{itemize}
\item les multiples de 6 sont : 6, 12, 18, 24, 30, 36, etc.
\item les multiples de 15 sont : 15, 30, 45, etc.
\end{itemize}
Le plus petit multiple commun est donc 30.
\end{exemple}

\subsection{pgcd}

\begin{defin}
Soient $a$ et $b$ deux entiers.

On appelle \textbf{pgcd} (plus grand commun diviseur) de $a$ et $b$ le plus grand nombre $d$ qui divise à la fois $a$ et $b$.

\medskip

On le note $\pgcd{a}{b}$.
\end{defin}

\begin{exemple}
Si $a=210$ et $b=49$ alors $\pgcd{201}{49}=7$ car:
\begin{itemize}
\item $210=2\times3\times5\times7$. Les diviseurs de 210 sont donc :

\begin{multicols}{5}
1

2

3

5

$2\times3=6$

7

$2\times5=10$

$7\times2=14$

$5\times3=15$

$7\times3=21$

$2\times3\times5=30$

$5\times7=35$

$2\times3\times7=42$

$3\times5\times7=105$

210.
\end{multicols}

\item $49=7\times7$
\end{itemize}
Ainsi, le plus grand diviseur commun est 7.
\end{exemple}

\begin{rem}
Dans la pratique, on n'énumère pas les diviseurs car la liste peut être très longue. On préfèrera utiliser la propriété suivante.
\end{rem}

\newpage
\begin{prop}
Soient $a$ et $b$ deux entiers naturels tels que $a=bq+r$, $0 \leqslant r < b$ et $q$ entier.

Alors, $\pgcd{a}{b}=\pgcd{b}{r}$.
\end{prop}

Pour calculer le pgcd de deux nombres, on utilisera la propriété précédente autant que nécessaire.

Par exemple, pour calculer $\pgcd{126}{24}$:
\begin{itemize}
\item on écrit d'abord que $126=5\times24+6$, donc $\pgcd{126}{24}=\pgcd{24}{6}$;
\item on écrit ensuite que $24 = 4 \times 6 + 0$, donc $\pgcd{24}{6}=\pgcd{6}{0}=6$.
\end{itemize}

L'écriture $a=bq+r$ est appelée la \textit{division euclidienne} de $a$ par $b$.

Le fait d'écrire les divisions euclidiennes successives tel que nous l'avons fait constitue ce que l'on nomme l'\textit{algorithme d'Euclide}.

\begin{prop}
Soient $a$ et $b$ deux entiers naturels. Alors, $\pgcd{a}{b}$ est le dernier reste non nul dans l'algorithme d'Euclide.
\end{prop}

\begin{exemple}
$a=775$ et $b=372$.

L'algorithme d'Euclide donne :
\begin{align*}
775 & = 2 \times \textcolor{blue}{372} + \boxed{\color{red}31}\\
\textcolor{blue}{372} & = 12 \times \textcolor{red}{31} + 0.
\end{align*}

Le dernier reste non nul est 31 donc $\pgcd{775}{372}=31$.
\end{exemple}

\begin{prop}
\[
\pgcd{a}{b}=1 \iff \dfrac{a}{b} \text{ est irréductible}.
\]
\end{prop}

Si $\frac{a}{b}$ n'est pas irréductible alors on divise $a$ et $b$ par $\pgcd{a}{b}$ pour simplifier au maximum la fraction.

\begin{exemple}
$\pgcd{775}{372}=31$ (voir exemple précédent) donc $\dfrac{775}{372}=\dfrac{775\div31}{372\div31}=\dfrac{25}{12}$.
\end{exemple}

\begin{prop}
Pour tous entiers naturels $a$ et $b$,
\[
\ppcm{a}{b}\times\pgcd{a}{b}=ab.
\]
\end{prop}

\newpage

\section{Nombres premiers}

\subsection{Définition}

\begin{defin}
Un entier naturel est \textbf{premier} s'il admet deux uniques diviseurs : 1 et lui-même.
\end{defin}

\begin{rem}
Le nombre \og 1 \fg{} n'est pas premier car il n'admet qu'un seul diviseur (et non~2).
\end{rem}

La liste des nombres premiers commence ainsi :
\[
2~;3~;5~;7~;11~;13~;17~;19~;23~;\ldots
\]

\begin{rem}
Cette liste ne s'arrête pas; on dit que l'ensemble des nombres premiers est infini (mais ce n'est pas au programme...).
\end{rem}

\subsection{Décomposition en produit de facteurs premiers}

\begin{prop}
Tout entier naturel $a$ s'écrit de manière unique sous la forme:
\[
a=p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_n^{\alpha_n}
\]
où $p_1$, $p_2$, ..., $p_n$ sont des nombres premiers et où $\alpha_1$, $\alpha_2$, ..., $\alpha_n$ sont des entiers naturels.
\end{prop}

\begin{exemple}
$360=2^3 \times 3^2 \times 5$.

Pour trouver cette décomposition, on peut diviser autant que nécessaire par 2, puis par 3, puis par 5, etc.
\begin{center}
\begin{tabular}{SrSc|ScSl}
& 360 & 2 & $\leftarrow$ on divise par 2 car 360 est pair\\
résultat de $360\div2 \rightarrow$ & 180 & 2 & $\leftarrow$ on divise par 2 car 180 est pair\\
résultat de $180\div2 \rightarrow$ & 90 & 2 & $\leftarrow$ on divise par 2 car 90 est pair\\
résultat de $90\div2 \rightarrow$ & 45 & 3 & $\leftarrow$ on divise par 3 car 45 n'est plus divisible par 2,\\
& & & \phantom{$\leftarrow$ }donc on passe au nombre premier suivant\\
résultat de $45\div3$ & 15 & 3 & $\leftarrow$ on continue à diviser par 3\\
résultat de $15\div3$ & 5 & 5 & $\leftarrow$ on passe à 5, qui vient après 3\\
résultat de $5\div5$ & 1 & 1 & $\leftarrow$ on s'arrête quand on obtient 1.
\end{tabular}
\end{center}
On a ainsi obtenu que $360=2\times2\times2\times3\times3\times5$ (on regarde les nombres de droite).
\end{exemple}

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

\exercices

\subsection*{Multiples et diviseurs}

\begin{exocor}{multiples et diviseurs}[1]
Compléter les propositions suivantes à l'aide de l'un des mots : \og multiple \fg{} ou \og diviseur \fg.
\begin{enumerate}
\begin{multicols}{2}
\item 45 est un \ldots de 180.
\item 3 est un \ldots de 18.
\item 50 est un \ldots de 5.
\item 121 est un \ldots de 11.
\item 2 est un \ldots de 78.
\item 9 est un \ldots de 3.
\end{multicols}
\end{enumerate}

\tcblower

\begin{enumerate}
\begin{multicols}{2}
\item 45 est un \textcolor{red}{diviseur} de 180.
\item 3 est un \textcolor{red}{diviseur} de 18.
\item 50 est un \textcolor{red}{multiple} de 5.
\item 121 est un \textcolor{red}{multiple} de 11.
\item 2 est un \textcolor{red}{diviseur} de 78.
\item 9 est un \textcolor{red}{multiple} de 3.
\end{multicols}
\end{enumerate}
\end{exocor}

%%% 

\begin{exocor}{nombre parfait}[1]
Un nombre parfait est un nombre égal à la somme de tous ses diviseurs, excepté lui-même.
\begin{enumerate}
\item Vérifier que 6 est un nombre parfait.
\item 18 est-il parfait ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Les diviseurs de 6 sont : 1, 2, 3 et 6. 

De plus, $1+2+3=6$ donc 6 est un nombre parfait.

\item Les diviseurs de 18 sont : 1, 2, 3, 6, 9 et 18.

Or, $1+2+3+6+9=21$ donc 18 n'est pas parfait.
\end{enumerate}
\end{exocor}

%%% 

\begin{exocor}{programme Python mystère}[1]
Qu'affiche le programme Python suivant ?
\begin{python}
for i in range(1,501):
	if 500%i == 0:
		print(i)
\end{python}
Je rappelle que :
\begin{itemize}
\item \texttt{range(a,b)} désigne tous les nombres entiers de $a$ et $b-1$;
\item \texttt{a\%b} désigne le reste de la division euclidienne de $a$ par $b$.
\end{itemize}

\tcblower

Ce programme parcourt tous les nombres entiers de 1 à 500 et pour chacun d'eux, teste si le reste de la division euclidienne de 500 par le nombre est nul, auquel cas cela signifie que 500 est divisible par le nombre et ce dernier est affiché.

Ainsi, le programme affiche tous les diviseurs de 500.
\end{exocor}


%%% 

\begin{exocor}{fraction mystère}[2]
Soit la fraction $A=\dfrac{45\boxed{?}}{357}$.

Déterminer toutes les valeurs que peut prendre le chiffre manquant afin que la fraction $A$ soit irréductible.

\tcblower


$357=3\times7\times17$; ainsi, le numérateur ne doit pas être divisible par 3, 7 et 17. 

Notons $x$ le chiffre manquant.

\begin{itemize}
\item pas divisible par 3, donc la somme de ses chiffres ne doit pas être divisible par 3. 
\[
4+5+x=9+x
\]
donc $x$ ne doit pas être égal à 0, 3, 6 ou 9. Donc $x$ peut être égal à :
\[
1,\ 2\, 4\, 5,\ 7,\ 8.
\]
\item 451 n'est divisible ni par 7, ni par 17 donc $x=1$ est possible;

452 n'est divisible ni par 7, ni par 17 donc $x=2$ est possible;

454 n'est divisible ni par 7, ni par 17 donc $x=4$ est possible;

455 est divisible par 7 donc $x\neq0$;

457 n'est divisible ni par 7, ni par 17 donc $x=7$ est possible;

458 n'est divisible ni par 7, ni par 17 donc $x=8$ est possible.
\end{itemize}
\end{exocor}

%%% 

\begin{exocor}{trouver deux multiples de 11}[2]
Déterminer deux nombres $x$ et $y$ multiples de 11, avec $x<y$, tels que $x+y=132$.

\tcblower

Il existe deux entiers $k$ et $k'$ tels que $x=11k$ et $y=11k'$ car $x$ et $y$ sont multiples de 11.
\[ x+y=132\iff 11(k+k')=132 \iff k+k'=\dfrac{132}{11}=12.\]
De plus, $x < y$ donc $k < k'$. Les différentes valeurs pour $k$ et $k'$ sont :
\begin{center}
$k=0$ et $k'=12$;

$k=1$ et $k'=11$;

$k=2$ et $k'=10$;

$k=3$ et $k'=9$;

$k=4$ et $k'=8$;

$k=5$ et $k'=7$.
\end{center}
\end{exocor}

%%% 

\begin{exocor}{divisibilité}[2]
Démontrer que la somme de trois entiers consécutifs est toujours divisible par 3.

\tcblower

Notons $n-1$, $n$ et $n+1$ trois entiers consécutifs quelconques. Leur somme est donc :
\[
n-1+n+n+1=3n.
\]
Ainsi, la somme est un multiple de 3 (car $n$ est un entier). Elle est donc toujours divisible par~3.
\end{exocor}

%%% 

\begin{exocor}{divisibilité}[3]
On considère un entier naturel $n$ s'écrivant avec 5 chiffres : $n=abcde$.
\begin{enumerate}
\item Vérifier que $\numprint{10000}=11k+1$ et $100=11k'+1$, où $k$ et $k'$ sont deux entiers naturels.
\item Vérifier que $\numprint{1000}=11q-1$, où $q$ est un entier naturel.
\newpage
\item En déduire l'équivalence suivante:
\begin{center}
$n$ est divisible par 1 $\iff$ $(e+c+a)-(d+b)$ est divisible par 11.
\end{center}
\item \numprint{71632} est-il divisible par 11 ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item $\numprint{10000}=909\times11+1$ et $100=9\times11+1$.
\item $\numprint{1000}=91\times11-1$.
\item $\begin{aligned}[t]
n & =10^4a+10^3b+10^2c+10d+e\\
  & = (909\times11+1)a + (91\times11-1)b + (9\times11+1)c+(11-1)d+e\\
  & = 909\times11a+a+91\times11b-b+9\times11c+c+11d-d+e\\
  & = 11(909a+91b+9c+d)+a-b+c-d+e\\
  & = 11(909a+91b+9c+d) + (a+c+e)-(b+d)
\end{aligned}$

Ainsi, $n$ est divisible par 11 uniquement si $(a+c+e)-(b+d)$ l'est aussi, ce qui justifie l'équivalence.

\item $2+6+7=15$ et $3+1=4$; de plus, $15-4=11$, résultat divisible par 11, donc \underline{\numprint{71632} est divisible par 11}.
\end{enumerate}
\end{exocor}

%%% 

\begin{exocor}{programme Python mystère}[2]
Que fait la fonction \texttt{mystere} Python suivante ?
\begin{python}
def mystere(n):
    for i in range(2,n):
        if n % i == 0:
            return False
    return True
\end{python}

Je rappelle que :
\begin{itemize}
\item \texttt{range(a,b)} désigne tous les nombres entiers de $a$ et $b-1$;
\item \texttt{a\%b} désigne le reste de la division euclidienne de $a$ par $b$.
\end{itemize}

\tcblower

Expliquons pas à pas chaque ligne du programme:
\begin{itemize}
\item \texttt{def mystere(n):}

Une fonction est ici définie: elle admet pour \og variable \fg{} \texttt{n} (on dit que c'est un \textit{argument} de la fonction Python).

\item \texttt{for i in range(2,n):}

\og \texttt{for} \fg{} désigne une \textit{boucle itérative} (\og Pour \fg). Ici, la variable \texttt{i} va prendre ses valeurs dans \texttt{range(2,n)}, c'est-à-dire dans la liste \texttt{[2,3,4,...,n-1]}. Donc \texttt{i} vaudra successivement 2, 3, 4, etc. jusqu'à \texttt{n-1}.

\item \texttt{if a \% i == 0:}

À chaque itération, c'est-à-dire à chaque fois que \texttt{i} prendra une nouvelle valeur, on teste si le reste de la division euclidienne de \texttt{n} par \texttt{i} vaut \og 0 \fg, c'est-à-dire si \texttt{n} est divisible par \texttt{i}. Si c'est le cas, on exécute l'instruction suivante (à savoir : \og \texttt{return False} \fg. La fonction renvoie donc ici \og \texttt{False} \fg{} si \texttt{n} est divisible par \texttt{i}.  

\item \texttt{return True}

Cette instruction est en dehors de la boucle itérative \og \texttt{for i in range(2,0)} \fg{} : elle s'exécute donc si on sort de la boucle, c'est-à-dire si la fonction n'a pas renvoyé \og \texttt{False} \fg.
\end{itemize}

À la vue de tout ceci, on peut alors dire que la fonction renvoie \og \texttt{False} \fg{} s'il existe un diviseur de l'argument \texttt{n}, et renvoie \og \texttt{True} \fg{}  dans le cas contraire.

Ce programme teste donc si \texttt{n} est un nombre premier: elle renvoie \og \texttt{True} \fg{} si c'est le cas, et \og \texttt{False} \fg{} dans le cas contraire.
\end{exocor}

\newpage

\subsection*{PGCD}

%%% 

\begin{exocor}{PGCD}[1]
Calculer le PGCD des nombres $a$ et $b$ pour chacune des questions suivantes.
\begin{enumerate}
\begin{multicols}{3}
\item $a=\numprint{1756}$ et $b=\numprint{1317}$.
\item $a=\numprint{1025}$ et $b=\numprint{719}$.
\item $a=\numprint{825}$ et $b=\numprint{305}$.
\item $a=\numprint{742}$ et $b=\numprint{72}$.
\item $a=\numprint{1002}$ et $b=\numprint{2001}$.
\item $a=\numprint{945}$ et $b=\numprint{123}$.
\end{multicols}
\end{enumerate}

\tcblower

\begin{enumerate}
\item \algoeuclide{1756}{1317}
\item \algoeuclide{1025}{719}
\item \algoeuclide{825}{305}
\item \algoeuclide{742}{72}
\item \algoeuclide{1002}{2001}
\item \algoeuclide{945}{123}
\end{enumerate}
\end{exocor}

%%% 

\begin{exocor}{PGCD et simplification de fractions}[1]
En utilisant la notion de PGCD, simplifier au maximum les fractions suivantes.
\begin{enumerate}
\begin{multicols}{4}
\item $\dfrac{756}{441}$
\item $\dfrac{\numprint{1152}}{\numprint{1656}}$
\item $\dfrac{\numprint{3852}}{\numprint{1498}}$
\item $\dfrac{\numprint{20755}}{\numprint{9488}}$
\end{multicols}
\end{enumerate}

\tcblower

\begin{enumerate}
\item \algoeuclide{756}{441}

Donc $\dfrac{756}{441}=\dfrac{756\div63}{441\div63}=\dfrac{12}{7}.$

\item \algoeuclide{1152}{1656}

Donc $\dfrac{\numprint{1152}}{\numprint{1656}}=\dfrac{\numprint{1152}\div72}{\numprint{1656}\div72}=\dfrac{16}{23}$.

\item \algoeuclide{3852}{1498}

Donc $\dfrac{\numprint{3852}}{\numprint{1498}}=\dfrac{\numprint{3852}\div214}{\numprint{1498}\div214}=\dfrac{18}{7}$.

\newpage

\item \algoeuclide{20755}{9488}

Donc $\dfrac{\numprint{20755}}{\numprint{9488}}=\dfrac{\numprint{20755}\div593}{\numprint{9488}\div593}=\dfrac{35}{16}$.
\end{enumerate}
\end{exocor}

%%% 

\begin{exocor}{PGCD et musique}[2]
Un chef d'orchestre fait répéter 372 choristes hommes et 775 choristes femmes pour un concert. Il veut faire des groupes de répétition de sorte que:
\begin{itemize}
\item le nombre de choristes femmes est le même dans chaque groupe;
\item le nombre de choristes hommes est le même dans chaque groupe;
\item chaque choriste appartient à un unique groupe.
\end{itemize}
\begin{enumerate}
\item Quel nombre maximal de groupes pourra-t-il faire ?
\item Combien y aura-t-il alors de choristes hommes et femmes dans chaque groupe ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le nombre de groupes créés est nécessairement un diviseur de 775 et 372 (afin de pouvoir partager les groupes des hommes et des femmes). De plus, il faut que ce nombre soit maximal; il s'agit donc du PGCD de 372 et 775.

\algoeuclide{775}{372}

\medskip

\underline{Ainsi, il peut faire au maximum 31 groupes de répétition.}
\newpage
\item $775\div31=25$ et $372\div31=12$.

\underline{Ainsi, il y aura 25 femmes et 12 hommes dans chaque groupe.}
\end{enumerate}
\end{exocor}

%%% 

\begin{exocor}{PGCD et chocolat}[2]
Un chocolatier désire préparer un assortiment de chocolats blancs et chocolats noirs, qu'il mettra dans des boîtes.

Pour cela, il dispose en tout de \numprint{3036} chocolats noirs et \numprint{1056} chocolats blancs et il souhaite tous les utiliser.
\begin{enumerate}
\item Combien de boîtes pourra-t-il constituer ?
\item Calculer le nombre de chocolats noirs et de chocolats blancs qu'il y aura dans chacune des boîtes.
\end{enumerate}

\tcblower

\begin{enumerate}
\item \algoeuclide{3036}{1056}

\medskip

\underline{Le chocolatier pourra donc constituer 132 bo\^ites au maximum.}

\item $\dfrac{\numprint{3036}}{132}=23$ et $\dfrac{\numprint{1056}}{132}=8$.

\medskip

\underline{Ainsi, il y aura 23 chocolats noirs et 8 chocolats blancs dans chacune des boîtes.}
\end{enumerate}
\end{exocor}

%%% 
\newpage
\begin{exocor}{PGCD et pâtisserie}[2]
Un pâtissier dispose de 411 framboises et de 685 fraises. Afin de préparer des tartelettes, il désire répartir ces fruits en les utilisant tous et en obtenant le maximum de tartelettes identiques.
\begin{enumerate}
\item Calculer le nombre de tartelettes.
\item Calculer le nombre de framboises et de fraises sur chaque tartelette.
\end{enumerate}

\tcblower

\begin{enumerate}
\item \algoeuclide{411}{685}

\medskip

\underline{Il pourra donc faire au maximum 137 tartelettes.}


\medskip

\item $411\div1373$ et $685\div137=5$; il y aura donc 3 framboises et 5 fraises sur chaque tartelette.
\end{enumerate}
\end{exocor}

%%% 

\begin{exocor}{PGCD et salle de bain}[2]
Dans une salle de bain, on veut recouvrir le mur situé au-dessus de la baignoire avec un nombre entier de carreaux de faïence de forme carrée dont le côté est un nombre entier de centimètres le plus grand possible.
\begin{enumerate}
\item Déterminer la longueur du côté d'un carreau sachant que le mur mesure 210 cm de hauteur et 135 cm de largeur.
\item Combien faudra-t-il alors de carreaux ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item La longueur d'un carreau doit diviser à la fois 210 cm (la hauteur du mur) et 135 cm (la largeur). De plus, il faut qu'elle soit la plus grande possible. Elle est donc égale à \pgcd{210}{135}.

\algoeuclide{210}{135}

\medskip

\underline{Un carreau doit donc mesurer 15 cm de côté.}

\item $210\div15=14$ et $135\div15=9$ donc il doit y avoir 14 carreau en hauteur et 9 carreaux en largeur, soit $14\times9126$ carreaux en tout.
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{programme Python mystère}[2]
On considère le programme Python suivant:
\begin{python}
def euclide(a,b):
    if a < 0 or b < 0:
        return False
    if a < b:
        a , b = b , a # on intervertit les valeurs de a et b
        
    while b != 0:
        a , b = b , a % b
    
    return a
\end{python}

\begin{enumerate}
\item Exécutez pas à pas la fonction \texttt{euclide(12,21)}.
\item Que représente le nombre renvoyé par \texttt{euclide(a,b)}?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Exécutons pas à pas la fonction \texttt{euclide(12,21)}: il y a avant tout un test pour savoir si $a$ ou $b$ est strictement négatif. Ici, ce n'est pas le cas car $a=12$ et $b=21$.

Ensuite, il y a un test pour savoir si $a<b$: c'est en effet le cas, on on exécute l'instruction suivante. $a$ et $b$ sont alors intervertis. Ainsi, $a=21$ et $b=12$.

S'en suit une boucle conditionnelle \og \texttt{while} \fg{} : tant que $b$ est différent de 0, on exécute les instructions suivantes. On peut présenter les résultats successifs dans un tableau:
\begin{center}
\arrayrulecolor{numpagecorrige}
\begin{tabular}{|>{\ttfamily}Sc|*5{Sc|}}
\hline
b != 0 & -  & Vrai              & Vrai             & Vrai & Faux\\\hline
a      & 21 & 12                & 9                & 3    & -\\\hline
b      & 21 & \texttt{21\%12}=9 & \texttt{12\%9}=3 & \texttt{9\%3}=0 & -\\\hline
\end{tabular}
\end{center}

La fonction renvoie la dernière valeur de $a$, c'est-à-dire \og 3 \fg.

\item Sur l'exemple précédent, on reconnaît l'algorithme d'Euclide (d'où le nom de la fonction). Cet algorithme renvoie le \pgcd{a}{b}; c'est la valeur renvoyée par la fonction \texttt{euclide(a,b)}.
\end{enumerate}

\end{exocor}


\newpage
\subsection*{Nombres premiers}


%%% 

\begin{exocor}{reconnaître un nombre premier}[1]
Les nombres suivants sont-ils premiers ?
\begin{enumerate}
\begin{multicols}{4}
\item 97
\item 101
\item 113
\item 73
\end{multicols}
\end{enumerate}

\tcblower

\begin{enumerate}
\item 97 n'admet pas de diviseurs autre que 1 et 97; il est donc premier.
\item 101 n'admet pas de diviseurs autre que 1 et 101; il est donc premier.
\item 113 n'admet pas de diviseurs autre que 1 et 113; il est donc premier.
\item 73 n'admet pas de diviseurs autre que 1 et 73; il est donc premier.
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{décomposition en produit de facteurs premiers}[1]
Décomposez en produit de facteurs premiers les nombres suivants:
\begin{enumerate}
\begin{multicols}{4}
\item 75
\item 102
\item \numprint{17640}
\item \numprint{11375}
\end{multicols}
\end{enumerate}

\tcblower
\begin{enumerate}
\begin{multicols}{2}
\item \begin{tabular}[t]{r|l}
75&3\\25&5\\5&5\\1&
\end{tabular}\\
Donc $75 = 3 \times 5^2$.
\columnbreak
\item \begin{tabular}[t]{r|l}
102&2\\51&3\\17&17\\1&
\end{tabular}\\
Donc $102=2 \times 3 \times 17$. 
\end{multicols}
\end{enumerate}

\begin{enumerate}[resume]
\begin{multicols}{2}
\item \begin{tabular}[t]{r|l}
\numprint{17640}&2\\\numprint{8820}&2\\\numprint{4410}&2\\\numprint{2205}&3\\735&3\\245&5\\49&7\\7&7\\1&\end{tabular}\\
Donc $\numprint{17640}=2^3 \times 3^2 \times 5 \times 7^2$.
\columnbreak
\item \begin{tabular}[t]{r|l}
\numprint{11375}&5\\\numprint{2275}&5\\455&5\\91&7\\13&13\\1&\end{tabular}\\
Donc $\numprint{11375}=5^3\times7\times13^2$.
\end{multicols}
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{programme Python mystère}[2]
On considère le programme Python suivant:

\begin{python}
def is_prime(n , L):  
	# n est un nombre, L est une liste    
    for p in L:
        if n % p == 0:
            return False
        
    return True

def liste(n):
    L = [] # liste vide
    for k in range(2,n+1):
        if is_prime(k , L) == True:
            L.append(k)
            
    return L
\end{python}

\medskip

Rappelons que l'instruction \og \texttt{L.append(k)} \fg{} insère la valeur de \texttt{k} dans la liste \texttt{L}.

\medskip

Qu'affiche l'instruction suivante dans une console Python ?

\begin{console}
>>> liste(100)
\end{console}

\tcblower

Dans ce programme il y a deux fonctions:

\begin{python*}
def is_prime(n , L):  
	# n est un nombre, L est une liste      
    for p in L:
        if n % p == 0:
            return False
        
    return True
\end{python*}

On définit ici une fonction prenant deux arguments : un nombre \texttt{n} et une liste \texttt{L}.

Dans la boucle itérative \og \texttt{for p in L:} \fg, qui parcourt toute la liste \texttt{L} élément par élément, on teste si \og \texttt{n \% p == 0} \fg{} c'est-à-dire si le reste de la division euclidienne de \texttt{n} par \texttt{p} est nul, donc si \texttt{n} est divisible par \texttt{p}. Cela sous-entend donc que \texttt{L} est une liste de nombres.

Si tel est le cas, c'est-à-dire si \texttt{n} est divisible par \texttt{p}, la fonction retourne \og \texttt{False} \fg.

Une fois la liste \texttt{L} parcourue, si on sort du test \og \texttt{if n \% p == 0} \fg, c'est que \texttt{n} n'est divisible par aucun nombre de la liste \texttt{L}, et la fonction renvoie \og \texttt{True} \fg. 

\begin{python*}
def liste(n):
    L = [] # liste vide
    for k in range(2,n+1):
        if is_prime(k , L) == True:
            L.append(k)
            
    return L
\end{python*}


\medskip

On initialise une liste vide \texttt{L}. 

\medskip

Ensuite, il y a une boucle itérative \texttt{for k in range(2,n+1):} qui signifie que l'on parcourt tous les nombres entiers de 2 à \texttt{n}. Pour chacun d'eux, on fait appel à la fonction \texttt{is}\_\texttt{prime} et on teste si elle renvoie \og \texttt{True} \fg; si tel est le cas, on ajoute à la liste \texttt{L} le nombre \texttt{k} courant à l'aide de l'instruction \texttt{L.append(k)}.

\medskip

On construit ainsi une liste de nombres qui ne sont pas divisibles par les éléments de cette même liste : ce sont les nombres premiers inférieurs ou égaux à \texttt{n}.
\end{exocor}

%%%

\begin{exocor}{un test de primalité}[3]
On souhaite démontrer la propriété suivante:
\begin{quote}
Soit $n$ un entier naturel non nul.\\
Si, pour tout entier $k$ inférieur ou égal à $\sqrt{n}$, $n$ n'est pas divisible par $k$ alors $n$ est un nombre premier.
\end{quote}
Nous allons faire un raisonnement par l'absurde, c'est-à-dire que l'on suppose qu'aucun entier $k$ inférieur à $\sqrt{n}$ divise $n$ tout en ayant $n$ non premier.

Cela suppose qu'il existe un entier $q$ tel que $n = k \times q$, avec $k > \sqrt{n}$.

\begin{enumerate}
\item Montrer alors que $q$ est nécessairement inférieur ou égal à $\sqrt{n}$.
\item Conclure.
\item En utilisant cette propriété, montrer que \numprint{1973} est un nombre premier.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Si $n$ n'est pas premier et si $n$ n'admet aucun diviseur inférieur ou égal à $\sqrt{n}$, cela signifie que:
\[n = k \times q \]
avec $k \geqslant \sqrt{n}$.

En multipliant cette inégalité par $q$, on a :
\[
\underbrace{k \times q}_{=\ n} \geqslant \sqrt{n} \times q
\]
et donc:
\[
n \geqslant \sqrt{n} \times q\;,
\]
qui donne, en divisant les deux membres par $\sqrt{n}$:
\[
\dfrac{n}{\sqrt{n}} \geqslant q.
\]
Or, $\dfrac{n}{\sqrt{n}}=\dfrac{\sqrt{n} \times \sqrt{n}}{\sqrt{n}}=\sqrt{n}$ et donc:
\[
\sqrt{n} \geqslant q.
\]
$q$ doit donc nécessairement être inférieur ou égal à $\sqrt{n}$.

\item Or, par hypothèse de départ, on a supposé qu'il n'existait pas de diviseurs de $n$ qui soient inférieurs ou égaux à $\sqrt{n}$. Cela signifie donc l'affirmation de départ est fausse : s'il n'existe pas de diviseurs de $n$ inférieurs ou égaux à $\sqrt{n}$, $n$ est nécessairement un nombre premier (car si tel n'est pas le cas, on vient de démontrer que cela mène à une absurdité, à savoir que $q$ est un diviseur de $n$ inférieur ou égal à $\sqrt{n}$).

\begin{rem}
Ce raisonnement tire son nom justement du fait que l'on arrive à une absurdité en supposant le contraire de ce que l'on veut démontrer. Si vous ne comprenez pas cette logique; ce n'est pas étonnant car c'est assez difficile à concevoir à notre niveau, en classe de Seconde).
\end{rem}

\item En appliquant cette propriété, pour voir si \numprint{1973} est premier, on peut d'abord calculer sa racine carrée: 
\[
\sqrt{\numprint{1973}} \approx 44,4.
\]
On va donc tester tous les nombres premiers inférieurs à 44 : s'il y en a un qui divise \numprint{1973}, cela signifie que \numprint{1973} n'est pas un nombre premier.

Mais la liste des nombres premiers inférieurs à 44 se réduit à : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43.

En testant un à un, on voit qu'aucun divise \numprint{1973}. Donc \numprint{1973} est bien un nombre premier.
\end{enumerate}
\end{exocor}

%%% 

\begin{exocor}{infinitude des nombres premiers}[3]
On note $\mathbb{P}$ l'ensemble des nombres premiers. Nous souhaitons démontrer que cet ensemble est infini, c'est-à-dire qu'il existe une infinité de nombres premiers. Nous allons faire un \textit{raisonnement par l'absurde}... Laissez-vous guider par les questions.

\medskip

On suppose que $\mathbb{P}=\{p_1~;p_2~;\ldots~;p_n\}$, donc que cet ensemble n'est pas infini. Nous allons démontrer que ce n'est pas possible.

\medskip

On note $x=p_1\times p_2\times p_3 \times\cdots\times p_n+1$.

\begin{enumerate}
\item Justifier que le reste de la division euclidienne de $x$ par $p_1$ est égal à 1.
\item Que dire du reste de la division euclidienne de $x$ par $p_2$, $p_3$, ..., $p_n$ ?
\item Que peut-on en déduire alors sur $x$ ? Est-ce possible ? Conclure.
\end{enumerate}

\tcblower

\begin{enumerate}
\item On peut écrire $x=q \times p_1 + 1$ donc le reste de la division euclidienne de $x$ par $p_1$ est égal à 1.

\item Dans un cas général, pour tout entier naturel $k\leqslant n$, on peut écrire : $x = q \times p_k + 1$ donc le reste de la division euclidienne de $x$ par $p_k$ est égal à 1.

\item On a supposé que tous les nombres premiers étaient $p_1$, ..., $p_n$ et aucun d'eux ne divise $x$... \'Etrange ! Cela nous dit donc que $x$ est lui-même un nombre premier (car il n'admet aucun diviseur premier autre que 1 et lui-même). 

Mais $x>p_n$ par définition, ce qui contredit alors l'hypothèse que nous avons faite, à savoir que $\mathbb{P}$ était un ensemble fini.

Ainsi, cette hypothèse est fausse : donc $\mathbb{P}$ est infini.
\end{enumerate}
\end{exocor}

%%%

\begin{exocor}{nombres de Mersenne}[3]
On considère un nombre premier $n$.

On pose alors le nombre $M_n = 2^n-1$.

$M_n$ est-il un nombre premier ?

\tcblower

Si on teste les valeurs de $M_n$ pour les premières valeurs de $n$ possibles, on a:

\begin{itemize}
\item $n=2$ : $M_2=2^2-1=4-1=3$ est premier;
\item $n=3$ : $M_3=2^3-1=8-1=7$ est premier;
\item $n=5$ : $M_5=2^5-1=32-1=31$ est premier;
\item $n=7$ : $M_7=2^5-1=128-1=127$ est premier.
\end{itemize}

Mais ce n'est pas parce que les premiers résultats donnent un nombre premier que les autres aussi... Il suffit d'ailleurs de calculer le suivant:
\begin{itemize}
\item $n=11$ : $M_{11}=2^{11}-1=\numprint{2048}-1=\numprint{2047}=23\times89$ n'est pas premier.
\end{itemize}
Ainsi, en général, $M_n$ n'est pas premier si $n$ est premier.
\end{exocor}

%%%%%%%% LOGIQUE
\newpage

\subsection*{Logique mathématique}

%%%

\begin{exocor}{}[1]
Soit $n$ un nombre premier. Le nombre $n^2$ est-il premier ? 

\tcblower

$n^2 = n \times n$ donc les diviseurs de $n^2$ sont 1, $n$ et $n^2$.

Ainsi, $n^2$ n'est pas premier. 
\end{exocor}



\begin{exocor}{démonstration par contraposée}[3]
Démontrer l'assertion suivante:
\[
\forall (x,y)\in\N\times\N,\ x\neq2\text{ et }y\neq2 \Longrightarrow xy-2 \neq x + y.
\]

\tcblower

Démontrons la contraposée de l'assertion, à savoir :
\[
xy-2 = x + y \Longrightarrow \exists (x,y)\in\N\times\N,\ x=2\text{ ou }y=2.
\]
\begin{align*}
xy-2 = x+y & \Longrightarrow xy - x - y = 2\\
& \Longrightarrow xy - x - y \textcolor{red}{+ 1} = 2 \textcolor{red}{+ 1}\\
& \Longrightarrow (x-1)(y-1) = 3\\
& \Longrightarrow \exists(x,y)\in\N^2,\ \begin{cases}x-1=1\\y-1=3
\end{cases}\quad\text{ou}\quad \begin{cases}x-1=3\\y-1=1
\end{cases}\\
& \Longrightarrow \exists(x,y)\in\N^2,\ (x=2,y=4) \text{ ou } (x=4,y=2).
\end{align*}
\end{exocor}

%%%%%%%%%%%

\begin{exocor}{démonstration par contraposée}[3]
Démontrer l'implication suivante:
\[
\forall(a,b)\in\N\times\N,\ \pgcd{a}{b}=1 \Longrightarrow \forall n\in\N, n\geqslant2, n \nmid a\text{ et }n \nmid b.
\]

\tcblower

Démontrons la contraposée de l'implication, à savoir:
\[
\exists n\in\N, n\geqslant2, \ n\vert a \text{ et } n\vert b \Longrightarrow \pgcd{a}{b}\neq1.
\]
\begin{align*}
\exists n\in\N, n\geqslant2, \ n\vert a \text{ et } n\vert b 
& \Longrightarrow \exists(p,q)\in\N^2, (p,q)\neq(1,1),\ \begin{cases}a=np\\b=nq\end{cases}\\
& \Longrightarrow \pgcd{a}{b} \geqslant n \geqslant 2\\
& \Longrightarrow \pgcd{a}{b} \neq 1.
\end{align*}
\end{exocor}


\corriges
