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

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

\newcommand{\typedoc}{Correction du devoir maison 6}          %%%%%%%%%%%%%%% 1ere ligne du titre de la feuille
\newcommand{\Ch}{Congruence}		   %%%%%%%%%%%%%%%% 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 $\\ 
 \textit{Les questions sont ind\'ependantes.}
\begin{enumerate}
\item {\footnotesize Pour quelles valeurs de l'entier relatif $m$ la fraction $\dfrac{2m-5}{m+8}$ est-elle elle-m\^eme un entier ?}
$$\dfrac{2m-5}{m+8}\in \Z\Longleftrightarrow m+8|2m-5$$
Supposons que $m+8|2m-5$, essayons d'obtenir des informations sur $m$. Or, $m+8|m+8$ donc $m+8$ divise toute combinaison linéaire de $m+8$ et de $2m-5$, en particulier :
$$ m+8|2(m+8)-(2m-5)=21$$
Si la fraction $\dfrac{2m-5}{m+8}\in \Z$ alors $m+8$ est un diviseur de $21$.\\
La liste des diviseurs de $21$ est la suivante :
$$ \mathscr D_{21}=\{-21;-7;-3;-1;1;3;7;21\}$$
Si $m+8=-21\Longleftrightarrow m=-29$.\\
Si $m+8=-7\Longleftrightarrow m=-15$.\\
Si $m+8=-3\Longleftrightarrow m=-11$.\\
Si $m+8=-1\Longleftrightarrow m=-9$.\\
Si $m+8=1\Longleftrightarrow m=-7$.\\
Si $m+8=3\Longleftrightarrow m=-5$.\\
Si $m+8=7\Longleftrightarrow m=-1$.\\
Si $m+8=21\Longleftrightarrow m=13$.\\
Vérifions que chacun de ses candidats à être solution du problème l'est vraiment. (ce n'est pas forcément le cas...) Un algorithme python effectuera cette tâche besogneuse à notre place :
\begin{center}
\includegraphics[scale=0.5]{redcran.eps}
\end{center}
$$ \mathscr S=\{-29;-15;-11;-9;-7;-5;-1;13\}$$
\item \begin{footnotesize}
$k$ \'etant un entier relatif, on pose : $x=2k-1$ et $y=9k+4$. \newline
Montrer que tout diviseur commun \`a $x$ et \`a $y$ divise $17$.
\end{footnotesize}
\\
Si $m$ divise simultanément $x$ et $y$ il divise aussi toute combinaison linéaire de $x$ et de $y$.\\
En particulier $m|2y-9x$, or $2y-9x=2(9k+4)-2(2k-1)=18k+8-18k+9=17$.\\
Par conséquent :
$$ m|17$$
\item {\footnotesize D\'eterminer les entiers naturels $u$ et $v$ v\'erifiant la relation : $u^2-4v^2=12$}\\
$u^2-4v^2=12\Longleftrightarrow (u-2v)(u+2v)=12$.\\
On en conclut que $u+2v|12$ et $u-2v|12$. L'ensemble des diviseurs de $12$ sont :
$$ \mathscr D_{12}=\{-12;-6;-4;-3;-2;-1;1;2;3;4;6;12\}$$
$u+2v>0$ donc $u+2v$ est un diviseur positif de $12$. On est conduit à résoudre les différents systèmes suivants :
$$ \left\{\begin{array}{l}
            u+2v=1\\u-2v=12
            \end{array}\right.\text{ et }\left\{\begin{array}{l}
            u+2v=2\\u-2v=6
            \end{array}\right.\text{ et }\left\{\begin{array}{l}
            u+2v=3\\u-2v=4
            \end{array}\right.\text{ et }\left\{\begin{array}{l}
            u+2v=4\\u-2v=3
            \end{array}\right.\text{ et }\left\{\begin{array}{l}
            u+2v=6\\u-2v=2
            \end{array}\right.\text{ et }\left\{\begin{array}{l}
            u+2v=12\\u-2v=1
            \end{array}\right.$$
            Le premier et le dernier système donne $2u=13$, il n'y a donc pas de solution entière.\\
            Le second système donne $2u=8\Longleftrightarrow u=4$ et $v=-1$, $v$ n'étant pas positif, le second système n'admet pas de solution.
            \\
            Le troisième et le quatrième système donne $2u=7$, il n'y a donc pas de solution entière.\\
            Le cinquième système donne $u=4$ et $v=1$ qui est solution.
        \\
        Le seul couple solution du problème est $u=4$ et $v=1$.
\item \begin{footnotesize}
$n$ est un entier naturel. D\'emontrer que quel que soit $n$, $3n^2+5n+1$ est impair . \newline
En d\'eduire que ce nombre n'est jamais divisible par $n(n+1)$.
\end{footnotesize}\\
Si $n$ est pair alors $$ n\equiv 0[2]\Longrightarrow n^2\equiv 0[2]\Longrightarrow 3n^2\equiv 0[2]\Longrightarrow 3n^2+1\equiv 1[2]$$
De plus si $n$ est pair alors :
$$ n\equiv 0[2]\Longrightarrow 5n\equiv 0[2]$$
Au final, dans le cas où $n$ est pair :
$$ 3n^2+5n+1\equiv 1[2]$$
Si $n$ est impair alors $$ n\equiv 1[2]\Longrightarrow n^2\equiv 1[2]\Longrightarrow 3n^2\equiv 3[2]\Longrightarrow 3n^2\equiv 1[2]\Longrightarrow 3n^2+1\equiv 0[2]$$
De plus si $n$ est impair alors :
$$ n\equiv 1[2]\Longrightarrow 5n\equiv 5[2]\Longrightarrow 5n\equiv 1[2]$$
Au final, dans le cas où $n$ est impair :
$$ 3n^2+5n+1\equiv 1[2]$$
Par conséquent, quelque soit l'entier naturel $n$ on a :
$$ 3n^2+5n+1\equiv 1[2]$$
Enfin si $n$ est pair alors $n\equiv 0[2]$ et $n+1\equiv 1[2]$, alors :
$$ n(n+1)\equiv 0[2]$$
De même si $n$ est impair alors $n\equiv 1[2]$ et $n+1\equiv 0[2]$, alors :
$$ n(n+1)\equiv 0[2]$$
Ainsi, quelque soit l'entier naturel $n$ on a :
$$ n(n+1)\equiv 0[2]$$
\textbf{Conclusion} : L'entier $n(n+1)$ est pair et l'entier $3n^2+5n+1$ est impair, par conséquent $n(n+1)$ ne divise pas $3n^2+5n+1$.
     \end{enumerate}}
     
     
\Exoi{\hfill $\spadesuit\spadesuit $\\ 
  \begin{enumerate}
  \item {\footnotesize Démontrer que pour tout entier naturel $n$, $2^{3n}-1$ est un multiple de $7$.}
  $$2^3\equiv 1[7]\Longrightarrow {2^3}^n\equiv 1^n[7]\Longrightarrow 2^{3n}\equiv 1[7]\Longrightarrow 2^{3n}-1\equiv 0[7]$$
  Pour tout entier naturel $n$, $2^{3n}-1$ est donc un multiple de $7$.
  \item {\footnotesize En déduire que $2^{3n+1}-2$ est un multiple de $7$ et que $2^{3n+2}-4$ est un multiple de $7$.}
  \\
  On a d'après la première question :
  $$ 2^{3n}-1\equiv 0[7] \Longrightarrow 2^{3n}\equiv 1[7]\Longrightarrow 2^{3n+1}\equiv 2[7]\Longrightarrow 2^{3n+1}-2\equiv 0[7]$$
  Pour tout entier naturel $n$, $2^{3n+1}-2$ est un multiple de $7$.\\
  Ainsi :
 $$ 2^{3n+1}\equiv 2[7] \Longrightarrow 2^{3n+2}\equiv 4[7]\Longrightarrow 2^{3n+2}-4\equiv 0[7]$$
 Pour tout entier naturel $n$, $2^{3n+2}-4$ est un multiple de $7$. 
  \item {\footnotesize Déterminer les restes de la division euclidienne par $7$ des puissances de $2$.\\}
  On cherche pour tout entier naturel $p$ le reste de $2^p$ par $7$.\\
  \textbf{Cas 1} : $p$ est divisble par $3$ et il existe un entier naturel $n$ tel que $2^p=2^{3n}$.\\
  Dans ce cas $$2^{3n}-1\equiv 0[7]\Longleftrightarrow 2^{3n}\equiv 1[7]$$
  \textbf{Cas 2} : Le reste de la division euclidienne de $p$ par $3$ est $1$, dans ce cas il existe un entier naturel $n$ tel que $p=3n+1$.\\
  Auquel cas, $$ 2^{3n+1}-2\equiv 0[7]\Longleftrightarrow 2^{3n+1}\equiv 2[7]$$ 
  \textbf{Cas 3} : Le reste de la division euclidienne de $p$ par $3$ est $2$, dans ce cas il existe un entier naturel $n$ tel que $p=3n+2$.\\
  Auquel cas, $$ 2^{3n+2}-4\equiv 0[7]\Longleftrightarrow 2^{3n+2}\equiv 4[7]$$
  \item{\footnotesize  Soit $p\in\N$, on considère $ A_p=2^p+2^{2p}+2^{3p}$}
  \begin{enumerate}
  \item {\footnotesize Si $p=3n$, quel est le reste de la division de $A_p$ par $7$ ?}\\
  $$ 2^{3n}\equiv 1[7]$$
  $2^{2\times 3n}=2^{3\times 2n}$ donc on est dans le cas $1$ de la question précédente et :
  $$ 2^{2p}\equiv 1[7]$$
  $2^{3p}=2^{3\times 3n}$, de nouveau on est dans le cas $1$ de la question précédente, par conséquent :
  $$ 2^{3p}\equiv 1[7]$$
  Par addition on obtient :
  $$ A_p\equiv 3[7]$$
  Le reste de la division euclidienne de $A_p$ par $7$ est $3$.
  \item {\footnotesize Démontrer que si $p=3n+1$, alors $A_p$ est divisible par $7$.}\\
  Si $p=3n+1$ alors $2p=6n+2=3\times 2n+2$ et $3p=9n+3=3\times (3n+1)$.
  \\
  Par conséquent, en exploitant les résultats de la question précédente :
  $$ 2^{p}\equiv 2[7]\qquad \text{et} \qquad 2^{2p}\equiv 4[7]\qquad \text{et} \qquad 2^{3p}\equiv 1[7]$$
  Par addition on obtient :
  $$ A_p\equiv 2+4+1[7]\Longleftrightarrow A_p\equiv 0[7]$$
  $A_p$ est donc, dans ce cas, divisible par $7$.
  \item {\footnotesize Etudier le cas où $p=3n+2$.}\\
  Si $p=3n+2$ alors $2p=6n+4=6n+3+1=3\times (2n+1)+1$ et $3p=9n+6=3\times (3n+2)$.
    Par conséquent, en exploitant les résultats de la question précédente :
  $$ 2^{p}\equiv 4[7]\qquad \text{et} \qquad 2^{2p}\equiv 2[7]\qquad \text{et} \qquad 2^{3p}\equiv 1[7]$$
  Par addition on obtient :
  $$ A_p\equiv 4+2+1[7]\Longleftrightarrow A_p\equiv 0[7]$$
  $A_p$ est donc, dans ce cas aussi, divisible par $7$.
  \end{enumerate}
  \end{enumerate}
  }
  
  
  \Exoi{\hfill $\spadesuit\spadesuit\spadesuit\spadesuit $\\
\begin{footnotesize}
   Dans tout l'exercice, $n$ désigne un entier naturel non nul.
\end{footnotesize}\begin{enumerate}
\item 
	\begin{enumerate}
		\item \begin{footnotesize}
		Pour $1 \leq n \leq 6$, 
%		calculer 
%les restes de la division euclidienne de $3^n$ par 7.
déterminer $r$ tel que $$ 3^n\equiv r [7] \quad \text{et}\quad 0\leq r <7$$
		\end{footnotesize}
		$$ 3^1=3\equiv 3[7]$$
		Si $n=1$ alors $r=3$.
		$$ 3^2=9\equiv 2[7]$$
		Si $n=2$ alors $r=2$.
		$$ 3^2\equiv 2[7]\Longrightarrow 3^3\equiv 6[7]$$
		Si $n=3$ alors $r=6$.
		$$ 3^3\equiv 6[7]\Longrightarrow 3^3\equiv -1[7]\Longrightarrow 3^4\equiv -3[7]\Longrightarrow 3^4\equiv 4[7]$$
		Si $n=4$ alors $r=4$.
		$$ 3^4\equiv 4[7]\Longrightarrow 3^5\equiv 12[7] \Longrightarrow 3^5\equiv 5[7]$$
		Si $n=5$ alors $r=5$.
				$$ 3^5\equiv 5[7]\Longrightarrow 3^6\equiv 15[7]\Longrightarrow 3^6\equiv 1[7]$$
		Si $n=6$ alors $r=1$.
\item \begin{footnotesize}
En déduire que pour tout entier naturel $k$ :
$3^{6k}-1\equiv 0[7]$
\end{footnotesize}
Puisque $3^6\equiv 1[7]$ on a pour tout entier naturel $k$ :
$$ 3^{6k}\equiv 1^k[7]\Longrightarrow 3^{6k}-1\equiv 0[7]$$
		\item \begin{footnotesize}
		Démontrer que, pour tout $n,~ 3^{ n + 6} - 3^n\equiv 0[7]$.
	\\	 
		\end{footnotesize}
	D'après la première question on a :
	$$ 3^{6}\equiv 1[7]\Longrightarrow 3^6\times 3^n\equiv 3^n[7]$$
	Par conséquent, pour tout entier naturel $n$ :
	$$3^{6+n}\equiv 3^n[7]\Longrightarrow 3^{ n + 6} - 3^n\equiv 0[7]$$
{\footnotesize En déduire que $3^n$ et $3^{ n + 6}$ ont le m\^eme reste dans la division par 7. }\\
Puisque, pour tout entier naturel $n$ on a $3^{n+6}\equiv 3^n[7]$, $3^n$ et $3^{n+6}$ ont le même reste dans la division par $7$.
		\item {\footnotesize À l'aide des résultats précédents, calculer le reste de la division euclidienne de $3^{\nombre{1000}}$ par 7.}
		$$ 1000=6\times 166 +4$$
		Puisque pour tout entier naturel $n$ $3^{n+6}$ et $3^n$ ont le même reste dans la divsion euclidienne par $7$, il vient que $3^{1000}$ et $3^{994}$ ont le même reste dans la division euclidienne par $7$ et ainsi de suite $3^{1000}$ a même reste que $3^4$ dans la division euclidienne par $7$.\\
		Donc :
		$$ 3^{1000}\equiv 4[7]$$
		\item {\footnotesize De manière générale, comment peut-on calculer le reste de la division euclidienne de $3^n$ par 7, pour $n$ quelconque ? }\\
		On effectue la division euclidienne de $n$ par $6$, si on note $r$ le reste alors $3^n$ et $3^r$ ont même reste dans la division euclidienne par $7$. On observe ensuite les résultats de la question 1.
		\item {\footnotesize En déduire que, pour tout entier naturel $n$, $7$ ne divise pas $3^n$. }\\
		$n=6q+r$ avec $0\leq r<6$. D'après la question précédente $3^n\equiv 3^r[7]$, enfin d'après la première question, $7$ ne divise pas $3^r$ lorsque $r=0$ (cas équivalent au cas $n=6$), $1$, $2$, $3$, $4$, ou $5$. 
	\end{enumerate} 
\item {\footnotesize Soit $U_n = 1 + 3 + 3^2 + \cdots + 3^{n-1} = \displaystyle\sum_{i=0}^{i=n-1} 3^i$, où $n$ est un entier naturel supérieur ou égal à 2.}
	\begin{enumerate}
	    \item {\footnotesize En utilisant une suite géométrique que l'on précisera, montrer que $ U_n=\dfrac{3^n-1}{2}$}\\
	    Soit $v$ la suite géométrique de premier terme $v_0=1$ et de raison $3$, alors :
	    $$U_n= v_0+v_1+\dots+v_{n-1}=v_0\times \dfrac{1-q^n}{1-q}=\dfrac{1-3^n}{-2}=\dfrac{3^n-1}{2}$$
	    {\footnotesize En déduire que $2$ divise $3^n-1$.}\\
	    Puisque $U_n$ est une somme finie d'entier naturel, $U_n$ est encore un entier naturel i.e $\dfrac{3^n-1}{2}\in\N$, par conséquent $2|3^n-1$.
		\item {\footnotesize Montrer que si $U_{n}$ est divisible par 7, alors $3^n - 1$ est divisible par 7.}\\
		Si $U_n$ est divisible par $7$ alors :
		$$ U_n\equiv 0[7]\Longrightarrow \dfrac{3^n-1}{2}\equiv 0[7]$$
		En multipliant par $2$ on obtient :
		$$ 3^n-1\equiv 0[7]$$
		Ainsi si $U_n$ est divisible par $7$ alors $3^n-1$ est divisible par $7$.
		\item {\footnotesize Réciproquement, montrer que si $3^n - 1$ est divisible par 7, alors $U_n$ est divisible par 7.}\\
		Supposons que $3^n-1$ soit divisible par $7$ alors $2U_n=3^n-1$ est divisible par $7$.
		\\
		\textbf{Remarque} : On a $2U_n\equiv 0[7]$, mais la division n'est pas une opération permise pour les congruences, alors on va procéder autrement.
		\\
		Puisuqe $7$ divise $2U_n$ il existe un entier naturel $k$ tel que :
		$$ 2U_n=7k \qquad \text{et} \qquad U_n\text{ entier} $$
		Ainsi :
		$$ U_n=7\times \dfrac{k}{2} \qquad \text{et} \qquad U_n\text{ entier}$$
		Si $k$ est impair alors il existe un entier $t$ tel que $k=2t+1$ auquel cas $\dfrac{k}{2}=t+\dfrac{1}{2}$ auquel cas $7\times \dfrac{k}{2}=7t+3,5$
		\\
		Or, pour tout entier $t$, $2U_n=7t+3,5\notin \N$, par conséquent, puisque $U_n$ est entier, il est impossible que $k$ soit impair, donc $k$ est pair. Ainsi il existe un entier naturel $m$ tel que $k=2m$. D'où :
		$$ U_n=7\times m\Longrightarrow 7|m$$
 \\
\begin{footnotesize}
	En déduire les valeurs de $n$ telles que $U_n$ soit divisible par 7. 
	\end{footnotesize}
\\
On vient de démontrer que $U_n$ est divisible par $7$ si et seulement si $3^n-1$ est divisible par $7$.\\
	Or, $3^n\equiv 3^r[7]$ où $r$ est le reste de la division euclidienne de $n$ par $6$.\\
	Donc :
	$$ 3^n-1\equiv 3^r-1[7]$$
	Enfin $3^r-1\equiv 0[7]$ si et seulement si $r=0$. Autrement dit $7|3^n-1$ si et seulement si $n$ est un multiple de $6$.\\
	\textbf{Conclusion} : $7|U_n$ si et seulement $n$ est un multiple de $6$. 
		\end{enumerate} 
\end{enumerate}   }




  
\end{document}