\documentclass[a4paper,11pt,french]{article}
\linespread{1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Définitions de la feuille d'exercices

\newcommand{\typedoc}{Correction du Devoir Maison 3}          %%%%%%%%%%%%%%% 1ere ligne du titre de la feuille
\newcommand{\Ch}{Divisibilit\'e et division euclidienne}		   %%%%%%%%%%%%%%%% 2eme ligne et en haut à droite après	
\newcommand{\ch}{R\'evisions}               %%%%%%%%%%%%%%% En haut à gauche (numero chapitre)
\newcommand{\Cl}{T$^\text{ale}$S}
\newcommand{\Annee}{2013-2014}

\newcommand{\serie}{Scientifique}
\newcommand{\num}{0}	
\newcommand{\tps}{2h}	



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%		Packages
%\usepackage[french,lined,boxed,commentsnumbered]{algorithm2e}

\input macrodwicky.tex
\geometry{verbose,letterpaper,tmargin=1.8cm,bmargin=1.8cm,lmargin=1.5cm,rmargin=1.5cm}
\renewcommand{\arraystretch}{1.2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	Début
\begin{document}


\Cr{\decofourleft~ \typedoc ~\decofourright \\ \Ch}

\vspace{1cm}

\textbf{\textbf{Vous traiterez au moins un exercice parmi les trois suivants.}
}



\Exoi{\hfill $\spadesuit\spadesuit $\\ 
  \begin{enumerate}
  \item \begin{footnotesize}
  Le reste de la division euclidienne de l'entier naturel $a$ par $18$ est $13$.
  \\
  Quel est le reste de la division euclidienne de $a$ par $9$ ? Par $6$ ? Par $3$ ?
  \end{footnotesize}\\
  Il existe un entier relatif $q$ tel que :
  $$ a=18q+13=18q+9+4=9(2q+1)+4$$
  On vient de trouver deux entiers relatifs $q'=2q+1$ et $r'=4$  tels que :
  $$ a=9q'+r'\qquad \text{ où } 0\leq r'<9$$
  Ce couple d'entier est unique donc le reste de la division euclidienne de $a$ par $9$ est $4$.\\
  En procédant à l'identique on obtient :
  $$ a=18q+13=18q+12+1=6(3q+2)+1$$
  Le reste de la division euclidienne de $18$ par $6$ est $1$.\\
  Enfin :
  $$ a=18q+13=18q+12+1=3(6q+4)+1$$
  De nouveau le reste de la division euclidienne de $18$ par $3$ est $1$.
  \item \begin{enumerate}
  \item {\footnotesize Montrer que tout entier naturel $n$ s'écrit nécessairement sous l'une des trois formes $3k$, $3k+1$ ou $3k+2$ avec $k\in\N$.}\\
  Effectuons la division euclidienne de $n$ par $3$, d'après le cours il existe un unique couple d'entier $(k,r)$ tel que :
  $$ n=3k+r\qquad \text{ où } 0\leq r<3$$
  On a donc peu de choix pour le reste, 
  \begin{itemize}
  \item soit $r=0$ dans ce cas $n=3k$ ;
 \item  soit $r=1$ dans ce cas $n=3k+1$ ;
 \item soit $r=2$ dans ce cas $n=3k+2$.
  \end{itemize}
  \item {\footnotesize Montrer que dans la division euclidienne de $(n^2+n)$ par $3$ (où $n$ désigne un entier quelconque), le reste n'est jamais égal à $1$.}\\
  Distinguons les trois cas observés dans la question précédente :
  \begin{itemize}
  \item Si $n=3k$, alors :
  $$ n^2+n=9k^2+3k=3(3k^2+k)$$
  Dans ce cas $3$ divise $n^2+n$ et le reste de la division euclidienne de $n^2+n$ par $3$ vaut $0$.
  \item Si $n=3k+1$, alors :
  $$ n^2+n=(3k+1)^2+3k+1=9k^2+6k+1+3k+1=9k^2+9k+2=3(3k^2+3k)+2$$
  De l'unicité du couple $(quotient, reste)$ on tire de l'écriture précédente que le reste de $n^2+n$ vaut $2$.
  \item Enfin si $n=3k+2$, alors :
  $$ n^2+n=(3k+2)^2+3k+2=9k^2+12k+4+3k+2=9k^2+15k+6=3(3k^2+5k+2)$$
  $2$ divise $n^2+n$, par conséquent le reste de la division euclidienne de $n^2+n$ par $3$ vaut $0$.
  \end{itemize}
  Ayant énuméré tous les cas possibles, aucun ne donnant un reste égal à $1$ on peut conclure que le reste de la division euclidienne de $n^2+n$ par $3$ n'est jamais égal à $1$.
  \end{enumerate}
  \end{enumerate}
  }
  
  

\Exoi{\hfill $\spadesuit\spadesuit \spadesuit$\\ }
\begin{footnotesize}
Pour $n$ entier naturel non nul, on note $M_n$ l'entier :
$$ M_n=2^n-1$$
\end{footnotesize}
\begin{enumerate}
\item {\footnotesize Pour $1\leq n\leq 15$, quels sont les nombres $M_n$ premiers ?}\\
Le programme en python suivant :
\begin{center}
\includegraphics[scale=1]{merseneprog.eps}
\end{center}
donne les résultats que voici :
\begin{center}
\includegraphics[scale=1]{mersenresult.eps}
\end{center}
\item \begin{enumerate}
\item \begin{footnotesize}
Soit $k$ un entier naturel non nul et $a$ un entier quelconque. Montrer que $a-1$ divise $a^k-1$ pour $a\neq 1$.\\
\textit{Indication} : On utilisera un résultat sur les suites géométriques.
\end{footnotesize}\\
Considérons la suite géométrique $u$ définie pour tout entier naturel $n$ par :
$$ u_0=1\qquad \text{et}\qquad u_{n+1}=a\times u_n$$
On a alors $\forall n\in\N, u_n=a^n$ et la somme des $k$ premiers termes vaut (dans le cas où $a\neq 1$) :
$$ 1+a+a^2+\dots+a^{k-1}=\dfrac{1-a^k}{1-a}=\dfrac{a^k-1}{a-1}$$
Le nombre $\dfrac{a^k-1}{a-1}$ est donc entier dès que $a\neq 1$ ce qui prouve que :
$$\forall k\in\N^*, \forall a\in\N\text{ avec } a\neq 1\text{ on a } a-1|a^k-1$$
\item {\footnotesize En déduire que, si $d$ divise $n$, alors $2^d-1$ divise $M_n$.}\\
On applique le résultat précédent avec $a=2^d$. Si $d$ divise $n$, il existe un entier relatif $k$ tel que $n=dk$, on a alors d'après la question précédente $a-1$ divise $a^k-1$, ce qui revient à dire que :
$$ 2^d-1| {2^d}^k-1\Longleftrightarrow 2^d-1|2^{dk}-1\Longleftrightarrow 2^d-1|2^n-1\Longleftrightarrow 2^d-1|M_n$$
\end{enumerate}
\item {\footnotesize Déduire de la question $2.$ que, si $M_n$ est premier, alors $n$ est premier. La réciproque est-elle vraie ?}
\\
Raisonnons par l'absurde et supposons que $M_n$ soit premier tandis $n$ non. Puisque $n$ n'est pas premier, il existe deux  entiers relatifs $d\neq \pm 1$ et $k\neq \pm 1$ tels que $n=dk$. D'après la question précédente :
$$ 2^d-1|M_n$$
Comme $2^d-1\neq \pm 1$ cela signifie que $M_n$ n'est pas premier, ce qui absurde.\\
Ainsi si $M_n$ est premier alors $n$ est premier.\\
Enfin dans le cas $n=11$ (cas où $n$ est premier) on a montré dans la question $1$ que $M_{11}$ n'était pas premier, on peut donc en conclure que :
$$ n\text{ premier n'implique pas }M_n \text{ premier} $$
La réciproque est donc fausse. 
\end{enumerate}
%}

\Exoi{\hfill $\spadesuit\spadesuit \spadesuit$\\ 
{\footnotesize Ecrire un algorithme qui pour deux entiers données $a$ et $b$ affiche le reste de la division euclidienne de $a$ par $b$.}\\
Cette question sous-entends qu'il ne faut pas utiliser l'instruction reste déjà existante dans la plupart des langages informatiques.
\begin{center}
\includegraphics[scale=1]{reste.eps}
\end{center}
}

  
\end{document}