\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 \\
11/09/96	\hfill  U.F.R. de Math\'ematiques\\
\mbox{ }	\hfill B. Keller\\[0.5cm]
{\large\bf Un corrig\'e de l'examen du 11.09.96}
\end{center}

\begin{list-of-exercises}

\item 
Soit $x$ le montant du ch\`eque de tante Emilie.
D'apr\`es les informations fournies, nous avons
\begin{eqnarray*}
x & \equiv & 15 \;\; (29) \\
x & \equiv & 11  \;\; (99) \\
x & \equiv & 53 \;\; (79).
\end{eqnarray*}
Les nombres $29,99,79$ sont premiers entre eux deux \`a deux. 
Ce syst\`eme de congruences admet donc une solution 
$x$ dont la classe modulo $29\times 99\times 79 = 226809$ 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/226809 \iso \Z/29 \plus \Z/99 \plus \Z/79.
\]
Nous avons 
\[
\begin{array}{rcccrcl}
7821\, u_1 + 29\, v_1  =  1; & \mbox{sol. part.} & 
7821\times (-13) + 29 \times 3506  =  1. & \mbox{Posons } & x_1=-101673. \\
2291\, u_2 + 99\, v_2  =  1; & \mbox{sol. part.} &
2291\times (-7) + 99 \times 162  =  1. & \mbox{Posons } & x_2=-16037. \\
2871\, u_3 + 79\, v_3  =  1; & \mbox{sol. part.} &
2871 \times (-38) + 79 \times 1381  =  1 & \mbox{Posons } &  x_3=-109098 .
\end{array}
\]
Nous avons donc
$x \equiv 15\times (-101673)+11\times (-16037) +53\times (-109098) 
\equiv 1001 \;\; (226809)$. On a donc $x=1001+k\times 226809$. 
Puisque $x\leq 10000$, il s'ensuit que
$x=1001$. {\em Le montant du ch\`eque \'etait de $1001$ francs.}


\item 
\begin{sublist}
\item Nous avons $311 \equiv 3\;(7)$ et $1000\equiv -1\;(7)$.
Donc
\begin{eqnarray*}
a & = & 311 + 1000\times 311 + \cdots + 1000^n\times 311 \\
  & \equiv & 3 + (-1)\times 3 + \cdots + (-1)^n\times 3 \;\;\;(7) \\
  & \equiv & \left\{
\begin{array}{ll} 0 & \mbox{si $n$ est pair} \\
                  3 & \mbox{si $n$ est impair}
\end{array} \right.
\end{eqnarray*}
Donc le reste est $r=0$ si $n$ est pair et $r=3$ si $n$ est impair.

\item Le nombre $b=863$ est premier. D'apr\`es le petit 
th\'eor\`eme de Fermat, nous avons donc $a=541^{b-1}\equiv 1\;(b)$.
Donc le reste est $r=1$.

\item Nous avons la d\'ecomposition en facteurs premiers
$561=3\times 11\times 17$. Pour l'indicatrice de Carmichael
$\lambda(561)$, nous trouvons donc
$\lambda(561)= \ppcm(2,10,16)= 80$. Comme $19$ est premier
avec $561$, nous pouvons appliquer le lemme de Carmichael
pour conclure que $19^{80}\equiv 1\;(561)$. Le reste
$r$ vaut donc $1$.

\item D'apr\`es le petit th\'eor\`eme de Fermat, le reste
de $2^{a'}$ modulo $13$ ne d\'epend que de la classe de
$a'$ modulo $12$. Or, nous avons $5^2\equiv 1\;(12)$
et ainsi, la classe de $a'$ modulo
$12$ ne d\'epend que de la classe de $7^{11}$ modulo $2$.
Or, $7\equiv 1\;(2)$ de fa\c{c}on que $7^{11}\equiv 1 \;(2)$.
Donc $a'\equiv 5 \;(12)$ et $a\equiv 2^{5} \equiv 6\;(13)$.
Finalement, nous trouvons $r=6$. 

\end{sublist}


\item a) Par r\'ecurrence, on voit que
\[
x_n= b\;(a^{n-1} + a^{n-2} + \cdots + a + 1).
\]
Si $a\not\equiv 1\;(p)$, alors en particulier, nous avons 
$a\neq 1$ et
\[
x_n= b\;\frac{a^n-1}{a-1}
\]
Dans ce cas, comme $p$ ne divise pas $a-1$, le nombre
$x_n$ est divisible par $p$ ssi le nombre $b\;(a^n-1)$ est divisible
par $p$. D'apr\`es le petit th\'eor\`eme de Fermat, c'est le
cas si $n$ est multiple de $p-1$. Par contre, si $a\equiv 1\;(p)$,
nous avons $x_n \equiv n b\;(p)$ et alors $x_n$ est divisible
par $p$ ssi $n$ ou $b$ est divisible par $p$.

b) Si $b\equiv 0\;(p)$, alors $p$ divise $x_n$ pour tout $n\in\N$.
Supposons donc que $b\not\equiv 0\;(p)$. Alors, si
$a\not\equiv 1\;(p)$, le nombre $x_n$ est divisible par $p$
si et seulement si $n$ divise l'ordre de $\ol{a}$ dans le
groupe $(\Z/p\Z)^*$.
Finalement, si $a\equiv 1\;(p)$, alors $p$ divise $x_n$ si
et seulement si $p$ divise $n$.

\item a) Si $p$ divise $y$, alors $p$ divise
$x^2=pz^2-y^2$. Donc $p$ divise $x$. Ainsi, $p^2$ divise
$pz^2=x^2+y^2$ et $p$ doit diviser $z$. Donc $x$, $y$ et
$z$ sont divisibles par $p$. Clairement, le triplet
$(x/p, y/p, z/p)$ est encore une solution de l'\'equation
$(*)$. Par r\'ecurrence on trouve que si $p^k$ divise
$y$, alors $p^k$ divise $x$ et $z$ et $(x/p^k, y/p^k, z/p^k)$
est encore une solution de l'\'equation $(*)$. En choisissant
pour $p^k$ la plus grande puissance de $p$ qui divise $y$,
on construit ainsi une nouvelle solution $(x',y',z')$ telle
que $p$ ne divise pas $y'$.

b) L'\'equation $(*)$ donne la congruence $x^2+y^2\equiv 0\;(p)$.
Comme $p$ ne divise pas $y$, la classe de $y$ modulo $p$ est
inversible. Supposons que la classe de $y'$ est son inverse.
En multipliant la congruence par $y'^2$, nous obtenons
$(xy')^2+1\equiv 0\;(p)$. Ainsi, la congruence $u^2+1\equiv 0\;(p)$
admet la solution $u=xy'$.

c) D'apr\`es b), $-1$ est un r\'esidu quadratique modulo
$p$, nombre premier impair. On sait que $-1$ est r\'esidu
quadratique modulo $p$ ssi $p$ est congru \`a $1$ modulo
$4$. D'o\`u l'affirmation.

\item a) Une condition n\'ecessaire est que
\[
(\frac{a}{p})=1
\]
(symbole de Legendre). La d\'emonstration est analogue \`a
celle de 4). 

b) Une condition n\'ecessaire est que
\[
(\frac{7}{p})=1
\]
D'apr\`es la r\'eciprocit\'e quadratique, si $p\equiv 1\;(4)$, nous avons
\[
(\frac{7}{p})= (\frac{p}{7})
\]
ce qui vaut $1$ seulement si $p$ est un carr\'e modulo $7$, c'est-\`a-dire
que $p \equiv 1,2,4\; (7)$. Nous arrivons au syst\`eme
\begin{eqnarray*}
p & \equiv & 1\;(4) \\
p & \equiv & x\; (7) \quad \mbox{o\`u } x= 1,2,4.
\end{eqnarray*}
Ceci nous donne $p \equiv 1,9,-3\;(28)$. 

Par contre, si $p\equiv -1\;(4)$, nous avons 
\[
(\frac{7}{p})= -(\frac{p}{7})
\]
ce qui vaut $1$ seulement si $p$ est un non carr\'e modulo $7$,
c'est-\`a-dire que $p \equiv 1,2,4\; (7)$.
Nous arrivons au syst\`eme
\begin{eqnarray*}
p & \equiv & 1\;(4) \\
p & \equiv & x\; (7) \quad \mbox{o\`u } x= 3,5,6.
\end{eqnarray*}
Ceci nous donne $p \equiv 3,-9,13\;(28)$. 

En conclusion, d'apr\`es a), l'\'equation ne peut admettre
de solutions non-triviales que si $p \equiv 1, \pm 3, \pm 9$ ou $13$ modulo $28$.


\end{list-of-exercises}
\end{document}

















