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

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

\newcommand{\typedoc}{Correction devoir maison 7}          %%%%%%%%%%%%%%% 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}


\begin{exoi}\hfill $\spadesuit\spadesuit \spadesuit $\\ 
 \textbf{Partie A}\\
\begin{footnotesize}
Soit $N$ un entier naturel, impair non premier.\\
On suppose que $N = a^2 - b^2$ o\`u $a$ et $b$ sont deux entiers naturels.
\end{footnotesize}
\begin{enumerate}
\item  {\footnotesize Montrer que $a$ et $b$ n'ont pas la m\^eme parit\'e.}\\
Si $a\equiv 0 [2]$ et $b\equiv 0[2]$ alors :
$$ a^2\equiv 0[2] \qquad \text{et}\qquad b^2\equiv 0[2]$$
Et enfin :
$$ N=a^2-b^2\equiv 0[2]$$
Or, $N$ est impair, par conséquent il n'est pas possible d'avoir simultanément $a\equiv 0 [2]$ et $b\equiv 0[2]$.\\
De même si $a\equiv 1 [2]$ et $b\equiv 1[2]$ alors :
$$ a^2\equiv 1[2] \qquad \text{et}\qquad b^2\equiv 1[2]$$
Et enfin :
$$ N=a^2-b^2\equiv 0[2]$$
Or, $N$ est impair, par conséquent il n'est pas possible d'avoir simultanément $a\equiv 1 [2]$ et $b\equiv 1[2]$.\\
$a$ et $b$ ne peuvent pas donc pas avoir la même parité. Si l'un est pair, l'autre est nécessairement impair.
\item  {\footnotesize Montrer que $N$ peut s'\'ecrire comme produit de deux entiers naturels $p$ et $q$.}
On a :
$$ N=a^2-b^2=(a-b)(a+b)$$
Puisque $N$ est un entier naturel alors $a^2-b^2\geq 0\Longrightarrow a^2\geq b^2$, et puisque $a$ et $b$ sont aussi des entiers naturels, alors $a\geq b$. Ainsi $p=a-b$ et $q=a+b$ sont deux entiers naturels dont le produit vaut $N$.
\item  {\footnotesize Quelle est la parit\'e de $p$ et de $q$ ?}
Si $a\equiv 1[2]$ alors $b\equiv 0[2]$ d'après $1.$, auquel cas $$ p=a-b\equiv 1[2]\qquad \text{et}\qquad q=a+b\equiv 1[2]$$
De même si $a\equiv 0[2]$ alors $b\equiv 1[2]$, auquel cas $$ p=a-b\equiv -1[2]\Longrightarrow p\equiv 1[2] \qquad \text{et}\qquad q=a+b\equiv 1[2]$$
Dans tous les cas, $p$ et $q$ sont deux entiers naturels impairs.
\end{enumerate}
\textbf{Partie B}\\
\begin{footnotesize}
On admet que $250\:507$ n'est pas premier.\\
On se propose de chercher des couples d'entiers naturels $(a ~;~ b)$ v\'erifiant la relation :
\[(\text{E}) \quad  a^2 - 250 507 = b^2.\]
\end{footnotesize}\begin{enumerate}
\item  {\footnotesize Soit $X$ un entier naturel.}
	\begin{enumerate}
		\item  {\footnotesize Donner dans un tableau, les restes possibles de $X$ modulo 9 ; puis ceux de $X^2$ modulo 9.}
		\begin{center}
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
		\hline
		Reste possible de $X$ par $9$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ \\ \hline
		Reste possible de $X^2$ par $9$& $0$ & $1$ & $4$ & $0$ & $7$ & $7$ & $0$ & $ 4$ & $1$ \\ \hline
		\end{tabular}
		\end{center}
		\item \begin{footnotesize}
		Sachant que $a^2 - 250\:507 = b^2$, d\'eterminer les restes possibles modulo 9 de $a^2 - 250\:507$ ; en
d\'eduire les restes possibles modulo 9 de $a^2$.
		\end{footnotesize}
		\\
		Puisque $a^2 - 250\:507 = b^2$, $a^2-250\:507$ est un carré, donc les restes possibles modulo $9$ de $a^2 - 250\:507$ sont $0$, $1$, $4$ et $7$ d'après la question qui précède.
		\\
		Si $a^2-250\:507\equiv 0[9]$ alors $a^2\equiv 250\:507[9]$. 
		Or, $250 \:507=27834\times 9+1\Longrightarrow 250\:507\equiv 1[9]$ donc $a^2\equiv 1[9]$.\\
		De même si $a^2-250\:507\equiv 1[9]$ alors $a^2\equiv 250\:507+1[9]$ d'où $a^2\equiv 2[9]$. Ceci est impossible, un carré ne pouvant être congrue à $2$ modulo $9$ d'après la question précédente.\\
		De même si $a^2-250\:507\equiv 4[9]$ alors $a^2\equiv 5[9]$ (puisque toujours $250\:507\equiv 1[9]$). Ceci est impossible, un carré ne pouvant être congrue à $5$ modulo $9$.\\
		Enfin si $a^2-250\:507\equiv 7[9]$ alors $a^2\equiv 8[9]$ ce qui est impossible.
		\\
		\textbf{Conclusion} : $a^2\equiv 1[9]$.
		\item {\footnotesize Montrer que les restes possibles modulo 9 de $a$ sont 1 et 8.}\\
		D'après la question précédente $a^2\equiv 1[9]$, les seuls nombres dont le carré est congrue à $1$ modulo $9$ sont congrues à $1$ modulo $9$ ou à $8$ modulo $9$ d'après le tableau réalisé en $1.(a)$.
	\end{enumerate}
\item {\footnotesize Justifier que si le couple $(a ~;~ b)$ v\'erifie la relation (E), alors $a > 501$. Montrer qu'il n'existe pas de solution du type $(501 ~;~ b)$.}\\
$a^2-250\:507=b^2$ donc $a^2-250\:507\geq 0$ donc $a^2\geq 250\:507$. Puisque $a\in N$ on a :
$$ a\geq \sqrt{250\:507}\Longrightarrow a\geq 500,5\Longrightarrow a\geq 501$$
De plus $501=9\times 55+6$ donc $501\equiv 6[9]$, or $a$ est congrue à $1$ ou à $8$ modulo $9$, il est impossible que $a=501$, par conséquent :
$$ a>501$$
Puisque $a>501$ il ne peut exister de solutions du type $(501,b)$.
\item {\footnotesize On suppose que le couple $(a ~;~ b)$ v\'erifie la relation (E).}
	\begin{enumerate}
		\item  {\footnotesize D\'emontrer que $a$ est congru \`a 503 ou \`a 505 modulo 9.}\\
		On sait que $a$ est congru à $1$ ou à $8$ modulo $9$. Or :
		$$ 503\equiv 8 [9]\qquad \text{et} \qquad 505\equiv 1[9]$$
		Par conséquent si $a\equiv 1[9]$ alors $a\equiv 505 [9]$ et si $a\equiv 8[9]$ alors $a\equiv 503 [9]$.
		\item {\footnotesize D\'eterminer le plus petit entier naturel $k$ tel que le couple $(505 + 9k~;~ b)$ soit solution de (E), puis donner le couple solution correspondant.}\\
		Si $k=0$ alors $a=505+9\times 0=505$ et :
		$$ a^2-250507=505^2-250507=4518$$
		Et $\sqrt{4518}\simeq 67,2\in \N$ donc $k=0$ n'offre pas une solution à l'équation $(E)$.\\
		Si $k=1$ alors $a=505+9=514$ et :
		$$ a^2-250507=514^2-250507=13689$$
		Et $\sqrt{13689}=117\in \N$ donc pour $k=1$ le couple $(a=514, b=117)$ est solution de $(E)$.
	\end{enumerate}
\item {\footnotesize D\'eduire des questions pr\'ec\'edentes une \'ecriture de $250\:507$ en un produit deux facteurs.}\\
D'après la question précédente on a :
$$ 514^2-250507=117^2\Longleftrightarrow 514^2-117^2=250507\Longleftrightarrow (514-117)(514+117)=250507\Longleftrightarrow 397\times 631=250507$$
\end{enumerate}
\end{exoi}
  
  
% \begin{exoi}
% On rappelle le (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 \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}
%\item On consid\`ere l'\'equation (E) :   $17x - 28y = 1$ o\`u $(x,~y) \in \Z^2$.
%\item Quel th\'eor\`eme permet d'affirmer que l'\'equation (E) admet au moins un couple solution d'entiers relatifs ?
%\\En utilisant l'algorithme d'Euclide, trouver un tel couple solution. 
%\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}