\documentstyle{article}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\textwidth}{15cm}
\setlength{\headheight}{0cm}
\setlength{\topmargin}{0cm} 
\setlength{\headsep}{0cm}
\setlength{\textheight}{23cm}
\setlength{\parindent}{1cm}



\def\aujourdhui{\number\day\space\ifcase\month\or
  Janvier\or F\'evrier\or Mars\or Avril\or Mai\or Juin\or
  Juillet\or Ao\^ut\or Septembre\or Octobre\or Novembre\or D\'ecembre\fi
, \number\year}



%sublist
\newcounter{point}
\newenvironment{sublist}{
\begin{list}{\alph{point})}{\usecounter{point}
\setlength{\itemsep}{0cm}\setlength{\leftmargin}{1.2em}}
}{\end{list}}
                                                                


%liste d'exercices
\newcounter{exo}
\newenvironment{list-of-exercises}{
\begin{list}{\arabic{exo})}{\usecounter{exo}            
\setlength{\itemsep}{0cm}}                                      
}{\end{list}}                                                   
                                                                

\newcommand{\ppcm}{\mbox{PPCM}\,}
\newcommand{\leg}[2]{(\frac{#1}{#2})}

% abbreviations
% Black Board Bold Face
\newcommand{\N}{{\mbox{\bf N}}}
\newcommand{\sN}{{\mbox{\bf \scriptsize N}}}
\newcommand{\Z}{{\mbox{\bf Z}}}
\newcommand{\sZ}{{\mbox{\bf \scriptsize Z}}}
\newcommand{\R}{{\mbox{\bf R}}}
\newcommand{\Q}{{\mbox{\bf Q}}}
%Comma, forall
\newcommand{\ko}{\: , \;}
\newcommand{\fa}{\forall \,}
%Overline, Underline
\newcommand{\ol}{\overline}
\newcommand{\ul}{\underline}

\newcommand{\eps}{\varepsilon}
\newcommand{\Del}{\Delta}
\newcommand{\del}{\partial}
%\renewcommand{\phi}{\varphi}
\newcommand{\La}{\Lambda}
\newcommand{\lam}{\lambda}
\newcommand{\Ga}{\Gamma}
\newcommand{\Om}{\Omega}
\newcommand{\om}{\omega}
\newcommand{\Si}{\Sigma}
\newcommand{\si}{\sigma}


%Calligraphic letters
\newcommand{\ca}{{\cal A}}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\cg}{{\cal G}}
\newcommand{\ch}{{\cal H}}
\newcommand{\ci}{{\cal I}}
\newcommand{\ck}{{\cal K}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cn}{{\cal N}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cq}{{\cal Q}}
\newcommand{\cs}{{\cal S}}
\newcommand{\ct}{{\cal T}}
\newcommand{\cu}{{\cal U}}
\newcommand{\cv}{{\cal V}}
\newcommand{\cw}{{\cal W}}
\newcommand{\cx}{{\cal X}}



%Arrows
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\arr}[1]{\stackrel{#1}{\rightarrow}}
\newcommand{\longarr}[1]{\stackrel{#1}{\longrightarrow}}
\newcommand{\longlarr}[1]{\stackrel{#1}{\longleftarrow}}
\newcommand{\iso}{\stackrel{_\sim}{\rightarrow}}
\newcommand{\liso}{\stackrel{_\sim}{\leftarrow}}
\newcommand{\larr}[1]{\stackrel{#1}{\leftarrow}}
\newcommand{\da}{\downarrow}
\newcommand{\ua}{\uparrow}
\newcommand{\pl}{\parallel}




\newcommand{\plus}{\oplus}
\newcommand{\pgcd}{\mbox{PGCD}\,}
\newcommand{\add}[1]{\Z/#1}
\newcommand{\ind}{\mbox{{\rm ind}}}

\begin{document}
\begin{center}
MT 282 	        \hfill Universit\'e Paris 7 \\
06/02/96	\hfill  U.F.R. de Math\'ematiques\\
\mbox{ }	\hfill B. Keller\\[0.5cm]
{\large\bf Un corrig\'e de l'examen du 06.02.96}
\end{center}

\begin{list-of-exercises}

\item Soit $x$ le nombre d'amies de Miss M.
D'apr\`es les informations fournies, nous avons
\begin{eqnarray*}
x & \equiv & -11 \;\; (12) \\
x & \equiv & -5  \;\; (13) \\
x & \equiv & -12 \;\; (17).
\end{eqnarray*}
Les nombres $12,13,17$ sont premiers entre eux deux \`a deux. 
Ce syst\`eme de congruences admet donc une solution 
$x$ dont la classe modulo $12\times 13\times 17 = 2652$ est unique.
Pour trouver $x$, nous d\'eterminons
d'abord $x_1$, $x_2$, $x_3$ dont les classes sont les images
r\'eciproques de $(1,0,0), (0,1,0), (0,0,1)$ par la projection
\[
\Z/2652 \iso \Z/12 \plus \Z/13 \plus \Z/17.
\]
Nous avons 
\[
\begin{array}{rcccrcl}
221\, u_1 + 12\, v_1  =  1; & \mbox{sol. part.} & 
221\times 5 + 12 \times (-92)  =  1. & \mbox{Posons } & x_1=1105. \\
204\, u_2 + 13\, v_2  =  1; & \mbox{sol. part.} &
204\times 3 + 13 \times (-47)  =  1. & \mbox{Posons } & x_2=612. \\
156\, u_3 + 17\, v_3  =  1; & \mbox{sol. part.} &
156 \times 6 + 17 \times (-55)  =  1 & \mbox{Posons } &  x_3=936 .
\end{array}
\]
Nous avons donc
$x \equiv 1\times 1105+8\times 612 +5\times 936 
\equiv 73 \;\; (2652)$. On a donc $x=73+k\times 2652$. 
Puisque $x\leq 1000$, il s'ensuit que
$x=73$. {\em Miss M. a $73$ amies.}

\item 
\begin{sublist}
\item Nous avons $a=1+16+ \ldots + 16^{299}= (16^{300}-1)/(16-1)$. 
Or $16\equiv 3\;(13)$ et l'ordre de $3$ dans $(\Z/13\Z)^*$
est \'egal \`a $3$. Donc $16^{300}\equiv 1\;(13)$ et $r=0$.

\item Le nombre $541$ est premier et ne divise pas $113$.
D'apr\`es le petit th\'eor\`eme de Fermat, nous avons donc
$113^{140}\equiv 1\;(541)$ et $r=1$.

\item Le nombre $1000$ est premier avec $23\times 67$ et
$\phi(23\times 67)= \phi(23)\times \phi(67)= 22\times 66 = 1452$.
D'apr\`es le th\'eor\`eme d'Euler, nous avons donc 
$1000^{1452} \equiv 1\;(23\times 67)$ et $r=1$.

\item Nous avons $\lambda(12871)= \ppcm(\lambda(61), \lambda(211))=
\ppcm(60, 210)= 420$. Or, d'apr\`es un lemme du cours, nous
avons $x^{\lambda(n)}\equiv 1\;(n)$ pour tout $x$ premier \`a $n$.
Ainsi, la classe de $a$ modulo $b$ ne d\'epend que de la classe
de $2^{12}$ modulo $420$. Or $420=2^2 \times 3\times 5 \times 7$
et $\lambda(420)=\ppcm(2,2,4,6)= 12$. Donc $17^{12} \equiv 1\;(420)$
et $a\equiv 2\;(b)$. Donc $r=2$. 

\end{sublist}

\item 
\begin{sublist}
\item Par d\'efinition, l'ordre maximal d'un \'el\'ement de
$G=(\Z/675\Z)^*$ est \'egal \`a $\lambda(675)=\lambda(3^3\times 5^2)
=\ppcm(18, 20)=180$.
\item Je dis que la classe de $2$ est d'ordre maximal ($=180$) dans $G$.
D'apr\`es le th\'eor\`eme chinois, il suffit de v\'erifier que
la classe de $2$ est d'ordre $18$ dans $G_1=(\Z/27\Z)^*$ et
d'ordre $20$ dans $G_2=(\Z/25\Z)^*$. Or les diviseur maximaux de $18$
sont $9$ et $6$ et nous avons $2^9\equiv -1 \;(27)$ et $2^6 \equiv 10\;(27)$.
Donc $2$ est bien d'ordre $18$ dans $G_1$. Les diviseurs maximaux
de $20$ sont $10$ et $4$. Or nous avons $2^10\equiv -1\;(25)$ et
$2^4\equiv 16\;(25)$. Donc $2$ est bien d'ordre $20$ dans
$G_2$. 
\end{sublist}

\item Par d\'efinition, si $p$ est un entier et $q$ un
nombre premier, nous avons 
\[
(\frac{p}{q})=
\left\{ \begin{array}{cl} 
  0 & \mbox{si $p$ est divisible par $q$,}\\
  1 & \mbox{si $p$ est un r\'esidu quadratique modulo $q$,} \\
 -1 & \mbox{si $p$ est un non r\'esidu quadratique modulo $q$,} \\
\end{array} \right.
\]
\begin{sublist}
\item En utilisant les propri\'et\'es du symbole $\leg{p}{q}$, 
nous trouvons
\[
\leg{71}{113}=\leg{113}{71}= \leg{42}{71}=\leg{2}{71}\leg{3}{71}\leg{7}{71}=
(+1) (-\leg{71}{3}) (-\leg{71}{7})= -\leg{-1}{3} (-\leg{1}{7})= -1.
\]
\item Nous avons
\[
\leg{173}{229}=\leg{229}{173}= \leg{56}{173}=\leg{7}{173} \leg{8}{173}
=\leg{173}{7} \leg{2}{173}= \leg{5}{7} (-1) = \leg{7}{5} (-1)= \leg{2}{5} (-1)= 1.
\]
\end{sublist}

\item
\begin{sublist} 
\item Nous trouvons les valeurs suivantes
\begin{eqnarray*}
& & 0:0,    1:1,   2:1,   3:2, 4:3, 5:5, 6:8, 7:13, 8:21, 9:34, 10:55,  11:89, 
         12:144, \\
& & 13:233, 14:377, 15:610, 16:987, 17: 1597, 18:2584,
19: 4181, 20 : 6765.
\end{eqnarray*}
\item Notons $b_n=3\times (8^n-4^n)$. Nous avons $b_0=0=a_0$ et 
$b_1= 3\times 4=1=a_0$ dans $\Z/11\Z$. Supposons que nous avons montr\'e
que $a_p=b_p$ pour $p<n+2$. Alors 
\begin{eqnarray*}
a_{n+2} & = & a_{n+1}+a_{n}= b_{n+1}+b_{n}= 3\times (8^{n+1} - 4^{n+1} + 8^{n}-4^n)\\
        & = & 3\times (8^{n} (8+1) - 4^{n}\times (4+1))=3\times (8^{n+2} -4^{n+2})\\
        & = & b_{n+2}.
\end{eqnarray*}

\item D'apr\`es la question pr\'ec\'edente, nous avons $a_n\equiv 0\;(11)$
si et seulement si $8^n=4^n$ dans $\Z/11\Z$ ou encore $(8\times 4^{-1})^n=1$.
Or $4^{-1}= 3$ dans $\Z/11\Z$ et $8\times 4^{-1}= 2$. Donc $a_n\equiv 0\;(11)$
ssi $2^n\equiv 1\;(11)$. Or l'ordre de $2$ dans $(\Z/11\Z)^*$ est \'egal \`a $10$.
Donc finalement, $a_n\equiv 0 \;(11)$ ssi $n\equiv 0\;(10)$. 

\item Si $p\equiv \pm 1\;(5)$, alors $p$ est impair et $2$ est
inversible dans $\Z/p\Z$. Nous notons $1/2$ son inverse.
Nous affirmons en outre que $5$ est un carr\'e dans $\Z/p\Z$.
En effet, nous avons
\[
\leg{5}{p}= \leg{p}{5} = \leg{\pm 1}{5}= 1.
\]
Soit $\alpha\in\Z/p\Z$ tel que $\alpha^2=5$. Notons que
$\alpha\neq -\alpha$ puisque $p\neq 2$.

Nous avons
\[
x^2-x-1= (x-1/2)^2 -5/4
\]
et l'\'equation $x^2-x-1=0$ est \'equivalente \`a
\[
x= 1/2 \pm \alpha/2.
\]
Comme $\alpha\neq -\alpha$ les deux solutions $x_1= 1/2-\alpha/2$
et $x_2=1/2+\alpha/2$ sont distinctes. 


\item En notation matricielle le syst\`eme devient
\[
\left[ \begin{array}{cc} 1 & 1 \\ x_1 & x_2 \end{array} \right]
\left[\begin{array}{c} c_1 \\ c_2 \end{array} \right] 
= 
\left[\begin{array}{c} 0 \\ 1 \end{array}\right].
\]
Le d\'eterminant de la matrice $2\times 2$ \`a gauche vaut
$x_2-x_1\neq 0$ et le syst\`eme admet donc une unique solution
donn\'ee par
\[
\left[ \begin{array}{c} c_1 \\ c_2 \end{array} \right] 
=
\frac{1}{x_2-x_1} 
\left[\begin{array}{cc} x_2 & -1 \\ -x_1 & 1 \end{array} \right]
\left[\begin{array}{c} 0 \\ 1 \end{array}\right]
=
\frac{1}{\alpha}
\left[\begin{array}{c} -1 \\ 1 \end{array}\right].
\]
Montrons par r\'ecurrence que nous avons 
\[
a_n \equiv c_1 x_1^n + c_2 x_2^n \quad \mbox{dans $\Z/p\Z$}.
\]
En effet, pour $n=0,1$ cette \'egalit\'e se r\'eduit \`a
la premi\`ere resp. \`a la deuxi\`eme \'equation du syst\`eme
que v\'erifient $c_1, c_2$. Pour $n\geq 0$, nous avons
\begin{eqnarray*}
a_{n+2} & = & a_{n+1} + a_{n} = c_1(x_1^{n+1} + x_1^{n}) +
c_2(x_2^{n+1} + x_2^n) \\
& = & c_1 x_1^n (x_1 + 1) + c_2 x_2^n(x_2+1) =
      c_1 x_1^{n+2} + c_2 x_2^{n+2} 
\end{eqnarray*}
car $x_1, x_2$ sont solutions de $x^2= x+1$. 

\item D'apr\`es e), nous avons 
\[
a_n = \frac{1}{\alpha}( -x_1^n + x_2^n) \quad \mbox{dans $\Z/p\Z$.}
\]
Donc $a_n=0$ ssi $x_1^n=x_2^n$, c'est-\`a-dire que 
$(x_1/x_2)^n =1$ dans $(\Z/p\Z)^*$. Cette derni\`ere condition
est remplie ssi $n$ est multiple de l'ordre de $x_1/x_2$ dans
$(\Z/p\Z)^*$. Donc d'apr\`es le th\'eor\`eme de Lagrange,
nous avons $a_n=0$ si $n$ est multiple de $p-1$, l'ordre
de $(\Z/p\Z)^*$. 

\end{sublist}




\end{list-of-exercises}

\end{document}











