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

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

\newcommand{\typedoc}{Devoir Maison 9}          %%%%%%%%%%%%%%% 1ere ligne du titre de la feuille
\newcommand{\Ch}{Congruence - conjecture de SP}		   %%%%%%%%%%%%%%%% 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{Tout élève traitera  au moins un exercice. A noter que l'exercice 2 a été écarté du DS1 au dernier moment.}


  
  \begin{exoi}\hfill $ \spadesuit\spadesuit$\\
  \begin{footnotesize}
  Lors du DS1, l'un d'entre vous (en fait plusieurs) a utilisé un résultat qui n'est pas présent dans le cours dont on va analyser la pertinence. 
  J'ai nommé ce résultat conjecture de SP.
  
  Dans tous l'exercice $a\in \Z$, $b\in \Z$, $c\in \Z$ , $n\in \N$ 
  
 \textit{Conjecture de SP} : $$ ac\equiv bc [n]\Longleftrightarrow a \equiv b [n]$$
 
  \end{footnotesize}
 \begin{enumerate}
 \item {\footnotesize L'une des deux implications de la conjecture de SP est vraie. Laquelle ? Redémontrer la.}\\
 Si $a\equiv b [n]$ alors $ac\equiv bc [n]$ est vraie.
 \\
 \textit{Preuve } : Si $a\equiv b [n]$ alors il existe un entier relatif $k$ tel que :
 $$ a-b=nk\Longrightarrow c(a-b)=nck\Longrightarrow ac-bc=nk'$$
 où $k'=ck$ est encore un entier relatif, par conséquent $n|ac-bc$ et donc :
 $$ ac\equiv bc [n]$$
 \item {\footnotesize Si on suppose que $c$ est premier et que $n$ n'est pas un multiple de $c$, montrer que la conjecture de SP est vraie.}\\
 On suppose que $ac\equiv bc [n]$ et on souhaite démontrer que $a\equiv b [n]$.\\
 Puisque $ac\equiv bc [n]$ alors il existe un entier naturel $k$ tel que :
 $$ ac-bc=nk\Longrightarrow c(a-b)=nk$$
 Ainsi $c|nk$ et $c$ est un nombre premier, d'après le lemme d'Euclide $c$ divise $n$ ou $c$ divise $k$. Par hypothèse $c$ ne divise pas $n$ donc $c$ divise $k$, par conséquent il existe un entier relatif $k'$ tel que $\dfrac{k}{c}=k'$ et on a donc :
 $$ a-b=n\dfrac{k}{c}=nk'$$
 Par conséquent $n|a-b$ et donc :
 $$ a\equiv b [n]$$
 \item {\footnotesize Donner des exemples pour lesquelles la conjecture de SP n'est pas vérifiée.}\\
 Pour répondre à cette question il faut trouve au moins deux exemples.\\
 \begin{itemize}
 \item Exemple 1 : $a=5$, $b=1$, $c=4$ et $n=16$ alors $20\equiv 4 [16]$ et pourtant il n'est pas vraie que $5\equiv 1[16]$.
 \item Exemple 2 : $a=4$, $b=1$, $c=2$ et $n=6$ alors $8\equiv 2 [6]$ et pourtant on a pas $4\equiv 1 [6]$...  
 \end{itemize}
 \item {\footnotesize Donner un exemple où $c$ n'est pas premier mais pour lequel la conjecture de SP est vraie. Expliquer.}\\
 Dans un premier temps on remarque que :
 $$ 20\equiv 8 [3] $$
 Et " après division par 4" on obtient :
 $$ 5\equiv 2 [3]$$
 La conjecture de SP semble s'appliquer de nouveau car effectivement $5\equiv 2 [3]$. \\
 On verra beaucoup plus tard dans l'année que cela provient du théorème de Gauss, en quelque d'une généralisation du lemme d'Euclide.
 \end{enumerate}
 
 \end{exoi}
 
 \begin{exoi}\hfill $\spadesuit\spadesuit\spadesuit$\\
\begin{footnotesize}
On souhaite déterminer le chiffre des unités de $2^n+3^n$ selon les valeurs de $n$.
\end{footnotesize}\begin{enumerate}
\item Compléter le tableau suivant :
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline $n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline 
Reste de $2^n$ modulo $5$ & 1 & 2 &4  &3  &1  &2  &4  &3 \\ \hline 
Reste de $3^n$ modulo $5$ & 1& 3 &4  &2  &1  &3  &4  &2\\ \hline 
Reste de $2^n+3^n$ modulo $5$ &2 &0  &3  &0  &2  &0  &3  &0 \\ \hline 
\end{tabular}
\end{center}
\item {\footnotesize Conjecturer les valeurs des restes de $2^n+3^n$ en fonction des valeurs de $n$.}
On conjecture que, pour tout nombre entier $k$ :
\begin{enumerate}
\item si $n$ est impair alors $2^n+3^n\equiv 0[5]$ ;
\item si $n=4k$ alors $2^n+3^n\equiv 2[5]$ ;
\item si $n=4k+2$ alors $2^n+3^n\equiv 3[5]$ ;
\end{enumerate}
\item \begin{footnotesize}
Pour tout $k$ et $n$ entiers naturels, montrer que $2^n+3^n$ et 
$2^{n+4k}+3^{n+4k}$ ont même reste dans la division par $5$.
\end{footnotesize}
$$2^4=16=5\times 3+1\Longrightarrow 2^4\equiv 1[5]\Longrightarrow 2^{4k}\equiv 1^k[5]\Longrightarrow 2^{4k}\times 2^n\equiv 2^n [5]\Longrightarrow 2^{4k+n}\equiv 2^n [5]$$
De même :
$$3^4=81=5\times 16+1\Longrightarrow 3^4\equiv 1[5]\Longrightarrow 3^{4k}\equiv 1^k[5]\Longrightarrow 3^{4k}\times 3^n\equiv 3^n [5]\Longrightarrow 3^{4k+n}\equiv 3^n [5]$$
Et par somme on obtient :
$$2^{4k+n}+3^{4k+n}\equiv 2^n+3^n[5] $$
\item {\footnotesize En déduire l'ensemble des restes possibles de $2^n+3^n$ en fonction de $n$.}\\
$2^0+3^0\equiv 0[5]$, $2^1+3^1=5\equiv 0[5]$, $2^2+3^2\equiv 3[5]$, $2^3+3^3\equiv 0[5]$. \\
Soit $r$ le reste de la division euclidienne de $n$ par $4$ alors il existe un entier relatif $q$ tel que $n=4q+r\Longrightarrow r=n-4q$ où $r$ vaut $0$, $1$, $2$ ou $3$. D'après la question précédente :
$$ 2^n+3^n\equiv 2^r+3^r[5]\Longrightarrow$$
Il suffit alors de se référer au quatre cas précédentes. Les restes possibles sont donc $0$, $2$ ou $3$.
\item {\footnotesize Montrer que $2^n+3^n$ est impair. En déduire son chiffre des unités en fonction de $n$.}
\\
$2\equiv 0[2]\Longrightarrow 2^n\equiv 0[2]$, de même $3\equiv 1[2]\Longrightarrow 3^n\equiv 1[2]$, par addition :
$$ 2^n+3^n\equiv 1[2]$$
Effectivement $2^n+3^n$ est impair.
\\
si $n$ est impair d'après notre conjecture démontrée par la suite le reste de $2^n+3^n$ dans la division euclidienne par $5$ est $0$. Son chiffre des unités est donc $0$ ou $5$, comme $2^n+3^n$ est impair son chiffre des unités est dans ce cas $5$.\\
si $n$ est un multiple de $4$ alors $2^n+3^n\equiv 2[5]$, son chiffre des unités est alors $2$ ou $7$, $2^n+3^n$ étant impair on conclut que son chiffre des unités est $7$.\\
Enfin si $n$ est un multiple de $2$ mais pas de $4$ alors $2^n+3^n\equiv 3[5]$ ce qui implique que son chiffre des unités est $3$ (et pas $8$).
\item {\footnotesize En déduire le chiffre des unités de $2^{2013}+3^{2013}$.}\\
$2013=4\times 503+1$ donc le chiffre des unités de $2^{2013}+3^{2013}$ est $5$ en appliquant la question précédente
\end{enumerate}
\end{exoi}
% \begin{exoi}
% On admet le résultat suivant, connu sous le nom de (petit) th\'eor\`eme de Fermat :\\
%si $p$ est un nombre premier qui ne divise pas l'entier naturel $a$, alors on a la congruence
%\[a^{p-1} \equiv  1\quad  \mod p\]
%
%\noindent \textbf{Partie A}
%
%\begin{enumerate}
%\item Prouver que $29$ est un nombre premier.
%\item  Soit $x \in  \N$ et $n$ un entier naturel tel que $n \equiv  1 \quad \text{mod}~ 28$.\\
%            En utilisant le th\'eor\`eme de Fermat, prouver que $x^n \equiv  x \quad  \mod~ 29$. 
%\end{enumerate}
%
% \noindent \textbf{Partie B}\\
%Soit A $= \{x \in  \N,~ x < 29\} = \{0~;~1~;~2~;~...~;~28\}$\\
%Pour $x \in  \text{A}$, on note $f(x)$ le reste de la division euclidienne de $x^{17}$ par $29$ et $g(x)$ le reste de la division euclidienne de $x^5$ par $29$.\\
%\begin{enumerate}
%\item \begin{enumerate}
%\item Prouver que $f(x) \in  \text{A}$ et $x^{17} \equiv  f(x)\quad  \text{mod}~ 29$.\\
%On admettra (la d\'emonstration est analogue) que $g(x) \in  \text{A}$ et $x^5 \equiv  g(x) \quad  \text{mod}~ 29$.
%\item Pour $x \in  \text{A}$, prouver que $g[f(x)] = x$.
%\end{enumerate}
%\item \textbf{Applications} :\\
%On attribue \`a chaque lettre de l'aphabet et aux deux signes \og + \fg{} et \og $-$ \fg, l'entier donn\'e par le tableau ci-dessous :
%\noindent \begin{tabularx}{\textwidth}{|*{14}{>{\centering \arraybackslash}X|}}\hline
%a& 	b& 	c &	d &	e &	f& 	g& 	h& 	i& 	j &	k &	l& 	m &	n\\ \hline
%1& 	2& 	3& 	4& 	5& 	6& 	7& 	8& 	9& 	10& 	11& 	12& 	13 &	14\\ \hline \hline
%o& 	p& 	q& 	r& 	s& 	t& 	u& 	v& 	w& 	x &	y& 	z& 	$+$& 	$-$\\ \hline
%15& 	16& 	17& 	18& 	19& 	20 &	21& 	22& 	23& 	24& 	25& 	26& 	27& 	28\\ \hline \hline
%\end{tabularx}
%\item Bob code le mot \og GAUSS \fg{} \`a l'aide de la fonction $f$ et envoie le message cod\'e \`a Alice.\\
%Voici le codage des deux premi\`eres lettres \og G \fg{} et \og A \fg{} :
%
%\medskip
%
%\begin{center}
% \begin{tabularx}{0.7\textwidth}{|*{3}{>{\centering \arraybackslash}X|}}\hline
%Message initial	& 	G 				&A\\  \hline
%Entier associ\'e 	&	7				& 1\\ \hline
%Utilisation de $f$	&$7^{17} \equiv 24\quad  \text{mod}~ 29$& 	$1^{17} \equiv 1\quad  \text{mod}~ 29$\\ \hline
%Message cod\'e 	&	X				& A\\ \hline
%\end{tabularx}
%\end{center}
%Compl\'eter son message.\\
%\item Alice reçoit le message suivant, cod\'e par Bob, \`a l'aide de la fonction $f$ :
%
%\begin{center}
% \begin{tabularx}{0.6\textwidth}{|*{5}{>{\centering \arraybackslash}X|}}\hline
%J &	I& 	L& 	L& 	R\\ \hline
%\end{tabularx} 
%\end{center}
%\end{enumerate}
% \end{exoi}   
%     





  
\end{document}