\documentclass[12pt] {article} \usepackage[T1]{fontenc} 
\usepackage[latin1]{inputenc}%applemac->latin1 sur pc! 
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx}
\usepackage[dvips]{color}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage{bclogo}
\usepackage{colortbl}
\usepackage[francais]{babel} 
\everymath{\displaystyle}
\textwidth 19cm \textheight 25cm \hoffset 
-1,4cm \voffset -3.7cm \oddsidemargin 0pt 
\renewcommand{\thesection}{\textcolor{blue}{\Roman{section}}} 
\title{\textcolor{red}{Divisibilit\'e et nombres premiers}}
\date{}
\author{}
\pagestyle{fancy}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}
\maketitle
\tableofcontents

\newpage
\section*{\textcolor{blue}{Activit\'e d'initiation (nombres crois\'es)( livre sp\'ecialit\'e (Didier)}}

Remplir la grille de nombres croisés ci-dessous sachant que tous les nombres y figurant sont des entiers naturels non nuls.
\begin{center}
\psset{unit=0.8}
\begin{pspicture}(-1,0)(6,6)
\psgrid[subgriddiv=1,gridlabels=0,gridwidth=0.3pt](0,0)(5,5)%grille
\uput[l](0,4.5){1}\uput[l](0,3.5){2}\uput[l](0,2.5){3}\uput[l](0,1.5){4}\uput[l](0,0.5){5}
\uput[u](0.5,5){A}\uput[u](1.5,5){B}\uput[u](2.5,5){C}\uput[u](3.5,5){D}\uput[u](4.5,5){E}
\psframe[fillstyle=solid,fillcolor=gray](1,0)(2,1)
\psframe[fillstyle=solid,fillcolor=gray](3,2)(4,3)
\psframe[fillstyle=solid,fillcolor=gray](4,3)(5,4)
\end{pspicture}
\end{center}
\paragraph{Horizontalement}
\begin{enumerate}
\item Carr\'e parfait dont le produit des chiffres est 756.
\item Le nombre form\'e de ses deux premiers chiffres est le m\^eme que celui form\'e de ses deux derniers chiffres.
\item Multiple de 139.\\
Reste de la division euclidienne de 2001 par 9.
\item Permutation de 23444.
\item Carr\'e parfait.\\
Le produit de ses chiffres est 392.
\end{enumerate}

\paragraph{Verticalement}
\begin{enumerate}[A]
\item La somme de ses chiffres est 35.
\item Entier divisible par 11.
\item Nombre palindrome (qui se lit aussi bien à l'endroit qu'\`a l'envers).
\item Nombre premier. Cube parfait.
\item Entier naturel admettant un seul diviseur positif.
Le produit de ses chiffres est 72 et seul son dernier chiffe est pair.
\end{enumerate}

\newpage
\section{\textcolor{blue}{Divisibilit\'e dans $\mathbb{Z}$ :}}
\textbf{\textcolor{blue}{Rappel :}} On note $\mathbb{N}=\{0~;~1~;~2~;~3~;~\cdots\}$ l'ensemble des entiers naturels et $\mathbb{Z}=\{\cdots~;~-3~;~-3~;~-1~;~0~;~1~;~2~;~3~;~\cdots\}$ l'ensemble des entiers relatifs.\\

\begin{bclogo}[couleur=cyan!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Définition}}}
Soient $a$ et $b$ deux entiers ($a\neq 0$). On dit que $a$ divise $b$ si, et seulement s'il existe un entier $k$ tel que $b=ka$. On dit aussi que $a$ est un diviseur de $b$.
On dit encore que $b$ est un multiple de $a$. 
\end{bclogo}

\textbf{\textcolor{blue}{Exemples :}}\\
7 divise 56 car $56=7\times 8$ avec 8 entier\\
7 est un diviseur de 56 et 56 est un multiple de 7. On peut écrire $7 | 56$\\

\textbf{\textcolor{blue}{Remarques :}}
\begin{enumerate}[$\bullet$]
\item 0 est multiple de tout entier.

\item Tout entier non nul $n$ a (au moins) pour diviseurs $1$, $n$, $-1$ et $-n$.

\item $1$ a seulement deux diviseurs dans $\mathbb{Z}$, -1 et lui-même (donc 1 a pour seul diviseur 1 dans $\mathbb{N}$).

\end{enumerate}

\textbf{\textcolor{blue}{Remarque :}}\\
Comme $a$ et $-a$ ont les m\^emes diviseurs dans $\mathbb{Z}$, on se restreint \`a l'\'etude de la divisibilit\'e dans $\mathbb{N}$.\\

\begin{minipage}{14cm}
\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Propriétés}}}
\begin{enumerate}
\item Tout diviseur positif d'un naturel non nul $n$ v\'erifie : $1\leq d\leq n$.

\item Tout naturel non nul a un nombre fini de diviseurs.
\end{enumerate}
\end{bclogo}
\end{minipage}

\textbf{\textcolor{blue}{D\'emonstrations :}}\\
Soit $n$ un naturel non nul. L'entier $d$ divise $n$ s'il existe un entier $k$ tel que $n=kd$. Si $d>0$, alors $k>0$ (car $n$ est positif) et ainsi $k\geq 1$.\\
Par cons\'equent : $kd\geqslant d\Leftrightarrow n\geq d$.\\
L'entier $n$ a au plus $n$ diviseurs dans $\mathbb{N}$.\\
Le nombre maximum de diviseurs dans $\mathbb{Z}$ est donc $2n$.\\
$n$ admet un nombre fini de diviseurs.\\

\textbf{\textcolor{red}{Remarque :}} 0 a une infinit\'e de diviseurs.\\

\textbf{\textcolor{blue}{Exemple :}} Les diviseurs de 24 dans $\mathbb{N}$ sont : $\mathcal{D}(24)={1;2;3;4;6;12;24}$\\
Les diviseurs de 24 dans $\mathbb{Z}$ sont : ${-24;-12;6;-4;-3;-2;-1;1;2;3;4;6;12;24}$\\


\begin{bclogo}[couleur=cyan!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Définition :}}}
Deux entiers relatifs sont premiers entre eux si, et seulement, leurs seuls diviseurs communs sont -1 et 1.
\end{bclogo}


\textbf{\textcolor{red}{Exemple :}}\\
15 et 14 sont premiers entre eux : $\mathscr{D}(15)=\{-15~;~-5~;~-3~;~-1~;~1~;~3~;~5~;~15\}$ et $\mathscr{D}(14)=\{-14~;~-7~;~-2~;~-1~;~1~;~2~;~7~;~14\}$.\\

\newpage

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Propriétés}}}
\begin{enumerate}
\item 1 divise $a$ pour tout entier relatif $a$.
\item $a$ divise $a$ pour tout entier relatif $a$.
\item Si $a$ divise $bn$ et si $b$ divise $c$, alors, $a$ divise $c$ : on dit que la relation de divisibilit\'e est \textbf{\textcolor{red}{transitive}}.\\
\'Enonc\'e \'equivalent : Si $b$ est un multiple de $a$ et si $c$ est un multiple de $b$, alors $c$ est un multiple de $a$.
\item Si $a$ divise $b$ et si $m$ est un entier, alors $a$ divise $mb$.
\item Si $a$ divise $b$ et si $a$ divise $c$, alors $a$ divise $b+c$ et plus g\'en\'eralement, $a$ divise $mb+nc$ où $m$ et $n$ sont des entiers quelconques. ($mb+nc$ est une combinaison lin\'eaire de $b$ et $c$).
\end{enumerate}
\end{bclogo}

\vspace{1cm}
\textbf{\textcolor{blue}{D\'emonstrations :}}
\begin{enumerate}
\item $a=a\times 1$, donc 1 divise $a$.
\item $a=a\times 1$, donc $a$ divise $a$.
\item Si $a$ divise $b$, alors il existe $k$ entier tel que $b=ka$.\\
Si $b$ divise $c$, alors il existe $k'$ entier tel que $c=k'b$.\\
Alors $c=k'b=k'(ka)=(k'k)a$. $k'k$ est un entier, donc $a$ divise $c$.
\item d\'emonstration analogue.
\end{enumerate}

\vspace{1cm}
\noindent \textbf{\textcolor{red}{Exercices d'application :}}\\
\textbf{\textcolor{blue}{Exemple 1 :}} Déterminer les entiers $n$ tels que 7 divise $n+3$.\\
\textcolor{red}{Solution} : 7 divise $n+3$ si, et seulement si, il existe un entier $k$ tel que $n+3=7k$, soit $n=7k+3$.\\
L'ensemble des solutions est : $\mathcal{S}=\{7k-3\text{, }k\in\mathbb{Z}\}$\\

\noindent\textbf{\textcolor{blue}{Exemple 2 :}} Déterminer les entiers $n$ tels que $2n-5$ divise 6.\\
\textcolor{red}{Solution} : Les diviseurs de 6 sont -6, -3, -2, -1, 1, 2, 3 et 6.\\
On résout les diff\'erentes \'equations et on trouve comme solutions : $\mathscr{S}=\{1~;~2~;~3~;~4\}$.\\

\noindent\textbf{\textcolor{blue}{Exemple 3 :}} Trouver les entiers $n$ pour lesquels $\dfrac{n+15}{n+2}$ est entier.\\
\textcolor{red}{Solution :} $n+15=n+2+13$ donc $\dfrac{n+15}{n+2}=\dfrac{(n+2)+13}{n+2}=1+\dfrac{13}{n+2}$.\\
C'est un nombre entier si, et seulement si, $\dfrac{13}{n+2}$ est un entier, c'est-à-dire si, et seulement si $n+2$ est un diviseur de 13.\\
Les diviseurs de 13 sont -13, -1, 1 et 13.\\
On résout les quare équations : $\mathscr{S}=\{-15~;~-3~;~-1~;~11\}$\\

\noindent\textbf{\textcolor{blue}{Exemple 4 :}} D\'eterminer les entiers $n$ tels que 2n-3 divise n+5.\\
\textbf{\textcolor{red}{M\'ethode :}} Pour r\'esoudre un probl\`eme du type $f(n)|g(n)$, on se ram\`ene \` a $ h(n)|A$.\\
Soit $n$ un entier tel que $2n-3$ divise $n+5$. Alors $(2n-3)$ divise $2n+10$. Comme $2n-3$ divise $2n-3$, $2n-3$ divise $(2n+10)-(2n-3)$, c'est-\`a dire 13. Les diviseurs de 13 sont -13, -1, 1 et 13. On en d\'eduit que $n$ vaut -5, 1, 2 ou 8.\\

\textbf{\textcolor{blue}{R\'eciproquement}}, ces nombres sont solutions.\\
Les solutions sont -5, 1, 2 ou 8.\\

\noindent\textbf{\textcolor{blue}{Exemple 5 :}} (\'Equations diophantiennes : (Diophante : mathématicien, III\ieme{} siècle après J.C.))\\
D\'eterminer les entiers $x$ et $y$ tels que $x^2-y^2=9$.\\
\textbf{M\'ethode : } On essaye de se ramener \`a une \'equation du type $A\times B=C$, o\`u on connaît les diviseurs de $C$.\\
\textcolor{red}{Solution} : \\
Remarque : si $(x~;~y)$ est solutions, alors $(x~;~-y)$, $(-x~;~y)$ et $(-x~;~-y)$ sont aussi solutions. On peut alors se restreindre \`a $x$ et $y$ naturels.\\
$x^2-y^2=(x-y)(x+y)$.\\
Ainsi, $x-y $ et $x+y$ sont des diviseurs de 9.\\
L'ensemble des diviseurs de 9 sont -9, -3, -1, 1, 3, 9.\\
Comme $x^2-y^2$ est positif, avec $x$ et $y$ positifs, alors $x>y$, donc $x-y$ et $x+y$ sont positifs, et $x-y\leq x+y$.\\
Premier cas : $x-y=1$. Alors $x+y=9$, d'o\`u $x=5$ et $y=4$.\\
Deuxi\`eme cas : $x-y=3$. Alors $x=y=3$ d'o\`u $x=3$ et $y=0$.\\
Finalement, il y a six couples solutions : $(5;4)$, $(5;-4)$, $(-5;4)$, $(-5;-4)$, $(3;0)$ et $(-3;0)$.\\

\section{\textcolor{blue}{Division euclidienne des entiers dans $\mathbb{N}$ :}}
On \'etudie de fa\c con approfondie la division des nombres entiers vue dans les petites classes.\\\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Th\'eor\`eme de la division euclidienne dans $\mathbb{N}$ :}}}
Soit $a$ un entier et soit $b$ un entier naturel non nul. Il existe un \textbf{unique} entier $q$ et un unique entier $r$ tels que $a=bq=r$, avec $0\leqslant  r<b$.
\end{bclogo}\\

\textbf{\textcolor{red}{D\'emonstration}}\\
On admet d'abord la propriété suivante : toute partie non vide de $\mathbb{N}$ admet un plus petit élément.\\

Il y a deux paties à démontrer dans ce théorème : \textbf{l'existence} du couple $(q~;~r)$, puis son \textbf{unicité}.
\begin{enumerate}
\item \textbf{\textcolor{blue}{Existence de $q$ et $r$}} :\\
\begin{enumerate}[$\bullet$]
\item Premier cas : Si $0\leqslant a<b$, le couple $(q~;~r)=(0~;~a)$ convient.

\item Second cas : on suppose que $a=b$ ; le couple $(1~;~a)$  convient.

\item Troisième cas : on suppose a>b ($a$ et $b$ sont donc tous deux strictement positifs)\\
On note $M$ l'ensemble des multiples de $b$ strictement supérieurs à $a$ : $M=\{kb, kb>a\}$.\\
$2ba\in M$ car $2b\geqslant 1$ donc $M$ est non vide.\\
$M$ admet donc un plus petit élément que l'on note $q+1$.\\
Par définition de $q$, on a donc $qb\leqslant a<(q+1)b$.\\

Comme $b\leqslant a$, $b\leqslant a<q+1)b$ donc $1<q+1$.\\
On en déduit que $q>0$ et que $q$ est un entier naturel.\\
Posons alors $r=a-bq$. $r$ est un entier puisque $a$, $b$ et $q$ le sont.\\
$qb\leqslant a\Rightarrow r\geqslant 0$ donc $r$ est un entier naturel.\\
Comme $a<(q+1)b$, on a $0\leqslant r<b$.
\end{enumerate}
\textbf{\textcolor{red}{Conclusion :}} dans tous les cas, il existe un couple  $(q~;~r)$ vérifiant $a=bq+r$.

\item \textbf{\textcolor{blue}{Unicité de $q$ et $r$}}:\\
Supposons qu'il existe deux couples $(q~;~r)$ et $(q'~;~r')$ tels que $a=bq+r$ et $a=bq'+r'$, avec $0<r<b$ et $0<r'<b$.
\begin{enumerate}[$\bullet$]
\item $a=bq+r=bq'+r'$ donc $b(q-q')=r-r'$ avec $q-q'$ entier : $r-r'$ est alors un multiple de $b$.

\item $0\leqslant r<b$ donne $-b<-r\leqslant 0$.\\
Or, $0\leqslant r'<b$ d'où, en additionnant : $-b<r'-r<b$.\\
Or $r'-r$ est un multiple de $b$, strictment compris entre $-b$ et $b$ : le seul possible est 0.\\
Par conséquent : $r'-r=0$ donc $r=r'$.\\
En reportant dans $a=bq+r=bq'+r'$, on obtient $bq+r=bq'+r$, donc $bq=bq'$, d'où $q=q'$ car $b\neq 0$.\\
Le couple $(q~;~r)$ est donc unique.
\end{enumerate}
\end{enumerate}

\begin{minipage}{15cm}
\begin{bclogo}[couleur=cyan!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Définition}}}
On dit qu'on a effectu\'e la division euclidienne de $a$ par $b$ ; $q$ est le quotient et $r$ le reste.
\end{bclogo}
\end{minipage}

\textbf{\textcolor{red}{Exemples :}}\\
$123=37\times 3+12$ ; 12 est le reste de la division euclidienne de 123 par 3\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Propriétés}}}
\begin{enumerate}
\item $b$ divise $a$ si, et seulement si, le reste de la division de $a$ par $b$ est nul.
\item On peut \'etendre le th\'eor\`eme au cas o\`u $a$ est entier (relatif) et $b$ entier non nul : $a=bq+r$, avec $0\leq r<|b|$.\\\\
\end{enumerate}
\end{bclogo}

\textbf{\textcolor{red}{Exercice :}} Montrer que tout entier $n$ non divisible par 5 a un carré de la forme $5p+1$ ou $5p-1$ (raisonner par disjonction des cas)\\

\textbf{\textcolor{red}{Exercices page 23}}

\section{\textcolor{blue}{Congruences dans $\mathbb{Z}$ :}}
\begin{bclogo}[couleur=cyan!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Définition}}}
Soit $n$ un entier naturel non nul. on dit que $a$ et $b$ sont congrus modulo $n$ si, et seulement si, $a$ et $b$ ont même reste dans la division euclidienne par $n$.\\
On dit aussi que $a$ est congru  $b$ modulo $n$.\\
\textbf{Notation :} $a\equiv b(n)$ ou $a\equiv b$ (modulo $n$) ou $a\equiv b[n]$.
\end{bclogo}

\textbf{\textcolor{blue}{Remarque :}} $a\equiv r[n]$ avec $0\leq r<n$ si, et seulement si $r$ est le reste de la division euclidienne de $a$ par $n$.\\

\textbf{\textcolor{red}{Exemples :}} $25\equiv 14[11]$ ; $25\equiv 3[11]$.\\\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Théorème :}}}
Soient $a$ et $b$ deux entiers relatifs et $n$ un entier naturel. $a$ et $b$ ont même reste dans la division euclidienne par $n$ si, et seulement si $a-b$ est divisible par $n$.
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :}} \\
$\bullet$ Supposons que $a$ et $b$ aient même reste dans la division par $n$. il existe $q$ et $q'$ tels que : $a=nq+r$ et $b=nq'=r$ avec $q$ et $q'$ entiers et $0\leq r<n$.\\
Alors : $a-b=n(q-q')$ avec $q-q'$ entier, donc $a-b$ est divisible par $n$.\\\\
$\bullet$ \textbf{\textcolor{blue}{Réciproque :}} Supposons que $a-b$ soit divisible par $n$. Alors $a-b=kn$ avec $k$ entier.\\
Soit $r$ le reste de la division euclidienne de $b$ par $n$. On a : $b=nq=r$, avec $q$ entier et $0\leq r<n$.\\
Alors : $a=b+kn=nq+r+kn=(k+q)n+r$ avec $0\leq r<n$ d'où le résultat.\\\\


\noindent \begin{minipage}{15cm}
\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{ \textbf{\textcolor{red}{Corollaire :}}}
$a$ et $b$ sont congrus modulo $n$ si, et seulement si $a-b$ est divisible par $n$.
\end{bclogo}
\end{minipage}

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Propriétés}}}
\begin{enumerate}
\item $a$ est divisible par $n \Leftrightarrow a\equiv 0[n]$.

\item $n\equiv 0[n]$

\item $a\equiv a[n]$ (la relation de congruence est réflexive)

\item Si $a\equiv b[n]$ et si $b\equiv c[n]$, alors $a\equiv c[n]$ (on dit que la relation de congruence est transitive).

\item Si $a\equiv b~[b]$, alors $b\equiv a~[n]$ (la relation de congruence est symétrique)

\item Si $a\equiv a'[n]$ et si $b\equiv b'[n]$, alors $a+a'\equiv b+b'[n]$.

\item Si $a\equiv a'[n]$ et si $b\equiv b'[n]$, alors $aa'\equiv bb'[n]$.

\item Si $a\equiv b[n]$ et si p appartient  $\mathbb{N}$, alors $a^p\equiv b^p[n]$.
\end{enumerate}
\end{bclogo}


\textbf{\textcolor{red}{Démonstration :}}
\begin{enumerate}
\item évident d'après le corollaire précédent.
\item $n$ a pour reste 0 dans la division par $n$, donc $n\equiv 0[n]$.
\item $n | (a-a)$ donc $a\equiv a~[n]$

\item Si $a$ et $b$ ont même reste dans la division euclidienne par $n$ et si $b$ et $c$ aussi, alors $a$ et $c$ ont même reste ans la division euclidienne par $n$.

\item Si $a\equiv b~[n]$, alors $n|(a-b)$ ; on déduit que $n|(b-a)$ (dans $\mathbb{Z}$) et donc $b\equiv a~[n]$

\item $a-b=qn$ et $a'-b'=q'n$. Alors $a+a'-(b+b')=(q+q')n$ donc $a+a'-(b+b')$ est divisible par $n$, d'où le résultat.
\item On a les mêmes hypothèses, donc $a-b=qn$ et $a'-b'=q'n$ ; on peut écrire $ab-a'b'=ab-ab'+ab'-a'b'=a(b-b')+b'(a-a')=aq'n+b'qn=n(aq'+b'q)$.\\
Il est clair que $aq'+b'q\in\mathbb{Z}$ (somme et produit d'entiers).\\
Par conséquent : $n | (ab-a'b')$ donc $ab\equiv a'b'~[n]$
\item se montre par récurrence.
\end{enumerate}
\vspace{1cm}

\textbf{\textcolor{blue}{Exercice :}} Déterminer l'ensemble des entiers $x$ tels que : $x+4\equiv 2[8]$\\
$x+4\equiv 2[8]\Leftrightarrow x\equiv  -2[8]\Leftrightarrow x\equiv 6[8]$ car -2 est congru  6 modulo 8.\\\\

\textbf{\textcolor{blue}{Exercice :}} Déterminer l'ensemble des $x$ entiers tels que $5x\equiv 3[7]$\\
On remplit un tableau des valeurs prises modulo [7] par $5x$ lorsque $x$ prend les 8 valeurs des restes possibles modulo 7.\\
$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
x&0&1&2&3&4&5&6\\
\hline
5x&0&5&3&1&6&4&2\\
\hline
\end{array}$\\

On en déduit que les solutions sont les nombres $x$ congrus à 2 modulo 7.\\
$\boxed{\textcolor{red}{\mathscr{S}=\{2+7k,~k\in\mathbb{Z}\}}}$

\vspace{1cm}
\textbf{\textcolor{blue}{Exercice :}}
Déterminer le reste de la division par 7 de $2^n$.\\
En déduire le reste de la division euclidienne de $2^{134589}$ par 3.\\\\
Solution :\\
On a : $2^0=1[7]$ ; $2^1=2[7]$ ; $2^2=4[7]$ ; $2^3=8\equiv 1[7]$. On remarque que l'on va avoir un cycle modulo 3.\\
$\bullet$ Si $n\equiv 0[3]$, alors $n=3p$ d'où $2^n=2^{3p}=(2^3)^p\equiv 1^p[7]\equiv 1[7]$.\\
$\bullet$ Si $n\equiv 1[7]$, alors $n=3p+1$ d'où $2^n=2^{3p+1}=2^{3p}\times 2\equiv 2[7]$\\
$\bullet$ Si $n\equiv 2[7]$, alors $n=3p+2$ d'où $2^n=2^{3p+2}=2^{3p}\times 4\equiv 4[7]$\\
$\bullet$ on a : $13459\equiv 1[3]$ ; par conséquent : $2^{13458}\equiv 2[7]$

\section{\textcolor{blue}{Critères de divisiblilité}}
Un critère de divisibilité par $n$ où $n\in\mathbb{N}$ ($n\geqslant 2$) est un moyen de savoir \og rapidement\fg~si un nombre est divisible par $n$.\\
Un certain nombre de critères de divisibilité ont été vus dans les petites classes, souvent sans justification.\\
Donnons-les et justifions-les !\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Divisibilité par 2 :}}}
 Un nombre est divisible par 2 si, et seulement si, son chiffre des unités est lui-même divisible par 2.
\end{bclogo}
\textbf{\textcolor{red}{Démonstration}}\\
Si $n<10$, c'est évident.\\
Soit $n\geqslant 10$. il existe un couple unique $(q~;~r)$ tel que $n=10q+r$ avec $0\leqslant r<10$.\\
Si 2 divise $n$, comme 2 divise 10, 2 divise $n-10q=r$ donc $d$ divise $r$.\\
\textbf{\textcolor{blue}{Réciproquement :}} si 2 divise $r$, comme 2 divise 10, 2 divise $n$\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Divisibilité par 5 :}}}
Un nombre est divisible par 5 si, et seulement si, son chiffre des unités est lui-même divisible par 5.
\end{bclogo}\\

Même type de démonstration.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Divisibilité par 4 :}}}
Un nombre $A$ est divisible par 4 si, et seulement si, le nombre formé par le chiffre des dizaines et celui des unités est lui-même divisible par 4.
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :}} on effectue la division euclidienne de $A$ par 100 : $A=100q+r$ et on procède comme pour la divisibilité par 2 ou 5.\\


\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Divisibilité par 3 :}}}
Un nombre $A$ est divisible par 3 si son chiffre des unités est lui-même divisible par 3.
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :}}
Supposons $A\geqslant 10$ (sinon, c'est évident !).\\
$A=\overline{a_{n}a_{n-1}\cdots a_{k}\cdots a_{1}a_{0}}$ en écriture décimale ; par conséquent : \\
$A=a_{n}\times 10^n+a_{n-1}\times 10^{n-1}+\cdots+a_{k}\times 10^k+\cdots+a_{1}\times 10+a_{0}=\sum_{i=0}^{i=n}a_{i}\times 10^{i}$.\\
Raisonnons modulo 3 : on a : $10\equiv 1~[3]$.\\
Pour tout $n$, $10^n\equiv 1^n~[3]\equiv 1~[3]$.\\
Alors : $A\equiv a_{n}+a_{n-1}+\cdots+a_{0}=\sum_{i=0}^na_{i}~[3]$ d'où le résultat.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Divisibilité par 9 :}}}
Un nombre $A$ est divisible par 9 si son chiffre des unités est lui-même divisible par 9.
\end{bclogo}

Même démonstration, car $10\equiv 1~[9]$\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Divisibilité par 11:}}}
Un nombre $A$ est divisible par 11 si la somme alternée de ses chiffres est elle-même divisible par 11.\\
Si $A=\overline{a_{n}a_{n-1}\cdots a_{k}\cdots a_{1}a_{0}}$ en notation décimale, la somme alternée des chiffres est \\
$a_{0}-a_{1}+a_{2}+\cdots+(-1)^k10^k+\cdots+\cdots+(-1)^n10^n$.
\end{bclogo}

\textbf{\textcolor{red}{Démonstration :}} \\
Pour tout $k\in\mathbb{N}$, $10\equiv -1~ [11]$.\\
On en déduit : $A\equiv a_{0}\times (-1)^0+a_{1}\times (-1)^1+a_{k}\times \cdots+(-1)^k+a_{n}\times \cdots+(-1)^n~[11]\equiv a_{0}-a_{1}\cdots$\\

Nous avons vu les principaux critères (les plus faciles). Rien n'empêche d'en trouver d'autres.\\

\textbf{\textcolor{blue}{Exemple :}} divisibilité par 7.\\
Regardons les restes successifs dans la division euclidienne par 7 des puissances successives de 10.\\
$\begin{array}{|>{\columncolor{yellow!40}}c|*{9}{c|}}
\hline
10^k&1&10&10^2&10^3&10^4&10^5&10^6&10^7&10^8\\
\hline
\text{Reste de la division de }10^k\text{par }7&1&3&2&6&4&5&1&3&2\\
\hline
\end{array}$\\
On remarque un cycle (\textbf{\textcolor{blue}{à justifier}}), donc il est facile de déterminer tous les restes de $10^n$ modulo 7.\\
Dans l'écriture décimale avec les puissances de 10, on remplace chaque puissance de 10 par son reste modulo 7.\\
\textbf{\textcolor{red}{Exemple :}}
$\nombre{689243157}=6\times 10^8+8\times 10^7+9\times 10^6+2\times 10^5+4\times 10^4+3\times 10^3+1\times 10^2+5\times 10+7\equiv (6\times 2)+(9\times 3)+(8\times 1)+(2\times 5)+(4\times 4)+(3\times 6)+(1\times 2)+(5\times 3)+7~[7]\equiv 115~[7]\equiv 3~[7]$.\\
Ce nombre n'est  donc pas divisible par 7.\\

\textbf{\textcolor{red}{Autre critère de divisibilité par 7 :}}
Soit $n$ un nombre d'au moins trois chiffres et dont l'écriture décimale est $\overline{a_{n}a_{n-1}\cdots a_{k}\cdotsa_{1}a_{0}}$ .\\
On note $d$ le nombre dont l'écriture décimale est $=\overline{a_{n}a_{n-1}\cdots a_{k}\cdots a_{1}}$ (nombre formé à partir de $N$ en supprimant son chiffre des unités).\\
On pose $n_{1}=d-2a_{0}$.

\begin{enumerate}
\item Que vaut $n-10n_{1}$ ?

\item Montrons que $n$ est divisible par 7 si, et seulement si $n_{1}$ est divisible par 7.

\item Montrer que $n_{1}<n$.

\item Si $n_{1}$ a au moins trois chiffres, on itère le procédé ; on définit ainsi une suite de nombres $n_{k}$.\\
À quelle condition sur $n_{k}$ $n$ est-il divisible par 7 ?

\item Le nombre $\nombre{881909}$ est-il divisible par 7 ?
\end{enumerate}

\textbf{\textcolor{blue}{Démonstration :}}
On a $n=10d+a_{0}$ donc $n-10n_{1}=10d+a_{0}-10(d-2a_{0})=21a_{0}$.\\
Supposons que $n\equiv 0~[7]$ ; on a $n-10n_{1}\equiv 21a_{0}~[7]\equiv 0~[7]$ donc $10n_{1}\equiv 0~ [7]$.\\
Résolvons l'équation $10x\equiv 0~[7]$. Pour cela, on renseigne un tableau.\\
$10\equiv 3~[7]$ et soit $r$ le reste de la division euclidienne de $x$ par 7. Alors $10x\equiv 3r~[7]$.
\begin{center}
$\begin{array}{|>{\columncolor{yellow!40}}c|*{7}{c|}}
\hline
r&0&1&2&3&4&5&6\\
\hline
10x~[7]&0&3&6&2&5&1&4\\
\hline
\end{array}$
\end{center}
On en déduit que $10x\equiv 0~[7]\Leftrightarrow x\equiv 0~[7]$.\\
Par conséquent: $n\equiv 0~[7]\Rightarrow n_{1}\equiv 0~[7]$.\\
Réciproquement : si $n_{1}\equiv 0~[7]$, alors $n\equiv 0~[7]$.\\

$n-n_{1}=10d+a_{0}-\left(d-2a_{0}\right)=9d+3a_{0}>0$ donc $n>n_{1}$\\

$n$ est divisible par 7 si, et seulement si, $n_{k}$ l'est.\\

Pour $n=\nombre{881909}$, on trouve $n_{1}=88172$, $n_{2}=8813$, $n_{3}=875$ qui est divisible par 7, donc $n=\nombre{881909}$ est divisible par 7.



\label{fin}
\end{document} 