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

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

\newcommand{\typedoc}{Devoir Maison 18}          %%%%%%%%%%%%%%% 1ere ligne du titre de la feuille
\newcommand{\Ch}{Calcul de  PGCD}		   %%%%%%%%%%%%%%%% 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}


\DocDav
\vspace{1cm}

\begin{exoi}
\begin{footnotesize}
Dans cet exercice, on pourra utiliser le résultat suivant ;

\og Etant donnés deux entiers naturels $a$ et $b$ non nuls, si $PGCD(a;b)=1$ alors $PGCD(a^2;b^2)=1$\fg{}.

Une suite $(S_n)_{n\in \N}$ est définie pour $n>0$ par :
$$ S_n=\sum_{i=1}^n p^3$$
On se propose de calculer, pour tout entier naturel $n$ le plus grand diviseur commun entre $S_n$ et $S_{n+1}$.
\end{footnotesize}

 \begin{enumerate}
 \item {\footnotesize Démontrer, par récurrence, que pour tout $n>0$, on a : $$ S_n=\left(\dfrac{n(n+1)}{2}\right)^2$$}
 \\
 Notons cette propriété $\mathscr P(n)$ et montrons la par récurrence.
 \begin{itemize}
 \item \textbf{\textit{Initialisation}} : Si $n=1$ alors $S_n=1$ et $n(n+1)/2=1$ donc $\left(\dfrac{n(n+1)}{2}\right)^2=1$ ce qui montre bien que $\mathscr P(1)$ est vraie.
 \item \textbf{\textit{Initialisation}} Montrons que si $S_n=\left(\dfrac{n(n+1)}{2}\right)^2$ alors $S_{n+1}=\left(\dfrac{(n+1)(n+2)}{2}\right)^2$.\\
  $S_{n+1}=S_n+(n+1)^3$ donc si $S_n=\left(\dfrac{n(n+1)}{2}\right)^2$ alors :
  $$ S_{n+1}=\left(\dfrac{n(n+1)}{2}\right)^2+(n+1)^3=\dfrac{n^2(n+1)^2+4(n+1)^3}{4}=\dfrac{(n+1)^2\left[n^2+4(n+1)\right]}{4}=\dfrac{(n+1)^2(n+2)^2}{4}$$
  Par conséquent $$ S_{n+1}=\left(\dfrac{(n+1)(n+2)}{2}\right)^2$$
  $\mathscr P$ est héréditaire.
  \item \textbf{\textit{Conclusion}} : $\mathscr P$ est initialisée à partir de $n=1$ et est héréditaire par conséquent on a démontré par récurrence que pour tout $n>0$ :
  $$ S_n=\left(\dfrac{n(n+1)}{2}\right)^2$$
 \end{itemize}
 \item {\footnotesize Etude du cas où $n$ est pair. Soit $k$ l'entier naturel non nul tel que $n=2k$.}
 \begin{enumerate}
 \item {\footnotesize Démontrer que $PGCD(S_{2k};S_{2k+1})=(2k+1)^2PGCD(k^2;(k+1)^2)$.}
$$S_{2k}=\left(\dfrac{2k(2k+1)}{2}\right)^2=\left(k(2k+1)\right)^2=k^2(2k+1)^2$$
$$ S_{2k+1}=\left(\dfrac{(2k+1)(2k+2)}{2}\right)^2=\left((2k+1)(k+1)\right)^2=(k+1)^2(2k+1)^2$$
On rappelle que si $k\neq 0$ on a :
$$ PGCD(ka;kb)=kPGCD(a;b)$$
donc ici :
$$ PGCD(S_{2k;2k+1})=PGCD(k^2(2k+1)^2;(k+1)^2(2k+1)^2)=(2k+1)^2PGCD(k^2;(k+1)^2)$$
 \item {\footnotesize Calculer $PGCD(k;k+1)$.}
 $n>0$ on a alors $k\geq 1$, si $k=1$ alors $k+1=2$ et $PGCD(1;2)=1$ sinon on effectue la suite de division euclidienne :
 $$ k+1=1\times k +1$$
 $$ k=1\times k +0$$
 donc dans tous les cas $PGCD(k;k+1)=1$.
 \item {\footnotesize Calculer $PGCD(S_{2k};S_{2k+1})$.}
\\
Puisque $PGCD(k;k+1)=1$ on a $PGCD(k^2;(k+1)^2)=1$ donc :
$$ PGCD(S_{2k};S_{2k+1})=(2K+1)^2\times 1=(2k+1)^2$$
 \end{enumerate}
 \item {\footnotesize Etude du cas où $n$ est impair. Soit $k$ l'entier naturel non nul tel que $n=2k+1$.}
 \item \begin{enumerate}
 \item {\footnotesize Démontrer que les entiers $2k+1$ et $2k+3$ sont premiers entre eux.}
 \\
 $2k+1$ et $2k+3$ sont deux nombres impairs. De plus toute combinaison linéaire de $2k+3$ et $2k+1$ divise leur $PGCD$ en particulier $ 2k+3-2k-1=2$ divise leur $PGCD$ donc $PGCD(2k+1;2k+3)=1$ ou $2$. \\
 Etant deux nombres impairs on conclut que :
 $$ PGCD(2k+1;2k+3)=1$$
 \item {\footnotesize Calculer $PGCD(S_{2k+1};S_{2k+2})$}
 $$S_{2k+1}=\left(\dfrac{(2k+1)(2k+2}{2}\right)^2=(2k+1)^2(k+1)^2$$
 $$ S_{2k+2}=\left(\dfrac{(2k+2)(2k+3}{2}\right)^2=(2k+3)^2(k+1)^2$$
 Donc :
 $$ PGCD(S_{2k+1};S_{2k+2})=PGCD((2k+1)^2(k+1)^2;(2k+3)^2(k+1)^2)=(k+1)^2PGCD((2k+1)^2;(2k+3)^2$$
 Puisque $PGCD(2k+1;2k+3)=1$ il suit que $PGCD((2k+1)^2;(2k+3)^2=1$ par conséquent :
 $$PGCD(S_{2k+1};S_{2k+2})=(k+1)^2 $$
 \end{enumerate}
 \item {\footnotesize Déduire des questions précédentes qu'il existe une unique valeur de $n$, que l'on déterminera, pour laquelle $S_n$ et $S_{n+1}$ sont premiers entre eux.}
 \\
 Si $n$ est pair, alors $S_n$ et $S_{n+1}$ sont premiers entre eux si et seulement si : $$(2k+1)^2=1\Longleftrightarrow 2k+1=1 \qquad \text{ou} \qquad 2k+1=-1\Longleftrightarrow k=0\qquad \text{ou} \qquad k=-1$$
 Si $k=0$ alors $n=0$ ce qui impossible puisque $n>0$ et si $k=-1$ alors $n=-2$ ce qui est impossible pour la même raison.\\
 Si $n$ est pair, alors $S_n$ et $S_{n+1}$ ne sont jamais premiers entre eux.\\
 Si $n$ est impair alors $S_n$ et $S_{n+1}$ sont premiers entre eux si et seulement si $$ (k+1)^2=1 \Longleftrightarrow k+1=1\qquad \text{ou} \qquad k+1=-1\Longleftrightarrow k=0\qquad \text{ou}\qquad k=-2$$
 Si $k=0$ alors $n=1$ auquel cas $S_n$ et $S_{n+1}$ sont premiers entre eux.\\
 Si $k=-2$ alors $n=-3$ ce qui est impossible puisque $n>0$.\\
 Au final $S_n$ et $S_{n+1}$ sont premiers entre eux si et seulement si $n=1$ auquel cas $S_1=1$ et $S_{2}=1+8=9$.
 \end{enumerate}
 \end{exoi}
 
\begin{footnotesize}
\begin{exoi}
\begin{enumerate} 
\item Montrer que, pour tout entier naturel non nul $k$ et pour tout entier  naturel $x$ :

\[(x-1)\left(1 +x + x^2 + \cdots + x^{k-1}\right) = x^k - 1.\]

Dans toute la suite de l'exercice, on considère un nombre entier $a$ supérieur ou égal à 2.
\item 
	\begin{enumerate} 
		\item Soit $n$ un entier naturel non nul et $d$ un diviseur positif de $n~:~n = dk$.

Montrer que $a^d- 1$ est un diviseur de $a^n - 1$.
		\item Déduire de la question précédente que $2^{{2004}} - 1$ est divisible par 7, par 63 puis par 9. 
	\end{enumerate} 
\item Soient $m$ et $n$ deux entiers naturels non nuls et $d$ leur pgcd.
	\begin{enumerate} 
		\item On définit $m'$ et $n'$ par $m = dm'$ et $n = dn'$. En appliquant le théorème  de Bezout à $m'$ et $n'$, montrer qu'il existe des entiers relatifs $u$  et $v$ tels que : $mu - nv = d$.
		\item On suppose $u$ et $v$ strictement positifs.

Montrer que : $\left(a^{mu} - 1 \right) - \left(a^{nv} - 1 \right) a^d =  
a^d - 1$.

Montrer ensuite que $a^d - 1$ est le pgcd de $a^{mu} - 1$ et de $a^{nv} - 1$.
		\item Calculer, en utilisant le résultat précédent, le pgcd de $2^{63} - 1$ et de $2^{60} - 1$.
	\end{enumerate}
\end{enumerate}
\end{exoi}
\end{footnotesize}

\textbf{Solution} : 

\begin{enumerate}
\item $1 + x + x^2 + \cdots + x^{k-1}$ est la somme des $k$ premiers termes de la suite géométrique  de premier terme $1$ et de raison $x$ : elle est donc égale à : $\dfrac{x^k - 1}{x - 1}$ (pour $x \neq 1$).\\
Donc $(x-1)\left(1 + x + x^2 + \cdots + x^{k-1} \right) = (x - 1) \times \dfrac{x^k - 1}{x - 1} = x^k - 1$.

Pour $x = 1$ : l'égalité est évidente.
\item
	\begin{enumerate}
		\item $n \in \ N,~n = dk$.
		
D'après la question \textbf{1.} $a^n - 1 = (a - 1)\left(1 + a + a^2 + \cdots + a^{n - 1} \right) = a^{dk} - 1 = \left(a^d \right)^k - 1 = \left(a^d - 1\right)\left( \cdots + \cdots \right)$,~ la parenthèse étant une somme d'entiers donc un entier.
		
Conclusion : $a^n - 1 =  \left(a^d - 1\right)\left(\cdots + \cdots \right)$, ce qui signifie que $\left(a^d - 1\right)$ est un diviseur de $a^n - 1$.
		\item On a donc 
		\begin{itemize}	\item {2004} est multiple de 3, donc d'après le \textbf{a.} $2^{{2004}} - 1$ est divisible par $2^3 - 1 = 7$ ;
	\item {2004} est multiple de 3 et de de 2, donc de 6 ; d'où $2^{{2004}} - 1$ est divisible par $2^6 - 1 = 63$ :
	\item On vient de voir que $2^{{2004}} - 1 = 63k = 9\times (7k)$, donc $2^{{2004}} - 1$ est divisible par $9$.
		\end{itemize}
	\end{enumerate}
\item 
	\begin{enumerate}
		\item $m = dm'$ et $n = dn'$. Puisque $d$ est le plus grand diviseur commun à $m$ et $n$, on sait que $m'$ et $n'$ sont premiers entre eux. D'après Bezout il existe $(u,~v) \in \Z^2$ tel que 
		\[m'u - n'v = 1 \iff m'ud - n'vd = d \iff mu - nv = d\]
		\item Avec $u$ et $v$ positifs, l'égalité précédente peut s'écrire $mu = nv + d.$
		
		D'où : $\left(a^{mu} - 1 \right)- \left(a^{nv} - 1\right)a^d = \left(a^{nv + d} - 1\right) - \left(a^{nv} - 1\right)a^d  = \left(a^{nv}\times a^d - 1\right) - \left(a^{nv} - 1\right)a^d   = \left(a^{nv}\times a^d\right) - 1 - \left(a^{nv}\times a^d\right)  + a^d = a^d - 1.$
		
Le PGCD de $a^{mu} - 1$ et $a^{nv} - 1$ divise aussi $a^{mu} - 1$ et $\left(a^{nv} - 1\right)a^d$ (et c'est le plus grand diviseur) donc leur différence  qui est $a^d - 1$.

Donc le PGCD de 	$\left(a^{mu} - 1 \right)- \left(a^{nv} - 1\right)a^d$ et de $a^{np} - 1$ est égal au PGCD de $a^d - 1$  et de $a^{np} - 1$.
Nous avons vu à la question précédente que comme $d$ divise $n$, $a^d - 1$  divise $a^{nv} - 1$.

Conclusion  :le PGCD de 	$a^{mu} - 1$ et $a^{nv} - 1$ est égal à $a^d - 1.$
		\item Application : $m = 63,~n = 60$.
		
		$63 = 3^2 \times 7$ et $60 = 2 \times 3 \times 5$. Donc PGCD$(63~;~60) = 3$.
		
On a $m = 63 = 3 \times 21= 3 m'$ et $n = 60 = 3 \times 20 = 3  n'$.

D'autre part 21 et 20 sont premiers et on trouve facilement 

$u = 1,~v = 1$ tels que $21 \times 1 - 20 \times 1 = 1$.

Donc $mu - nv = 63 - 60 = 3 = \text{PGCD}(63~;~60)$.
En appliquant le résultat de la question précédente : 
		
PGCD$\left(2^{63} - 1~;~2^{60} - 1\right) = 2^3 - 1 = 7$.
	\end{enumerate}
\end{enumerate}

\end{document}