\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}}                                                   
                                                                



% 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 \\
17/01/96	\hfill  U.F.R. de Math\'ematiques\\
\mbox{ }	\hfill B. Keller\\[0.5cm]
{\large\bf Un corrig\'e du 2$^e$ examen partiel }
\end{center}

\begin{list-of-exercises}

\item 
Les nombres $13,15,17$ sont premiers entre eux deux \`a deux. 
Ce syst\`eme de congruences admet donc une solution 
$x$ dont la classe modulo $13\times 15\times 17 = 3315$ 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/3315 \iso \Z/13 \plus \Z/15 \plus \Z/17.
\]
Nous avons 
\[
\begin{array}{rcccrcl}
255\, u_1 + 13\, v_1  =  1; & \mbox{sol. part.} & 
255\times 5 + 13 \times -98  =  1. & \mbox{Posons } & x_1=1275. \\
221\, u_2 + 15\, v_2  =  1; & \mbox{sol. part.} &
221\times (-4) + 15 \times 59   =  1. & \mbox{Posons } & x_2=-884. \\
195\, u_3 + 17\, v_3  =  1; & \mbox{sol. part.} &
195 \times (-2) + 17 \times 23  =  1 & \mbox{Posons } &  x_3=-390 .
\end{array}
\]
Nous avons donc
$x \equiv 11\times 1275+5\times (-884) +11\times (-390) 
\equiv 5315 \equiv 2000 \;\; (3315)$. 

\item 
\begin{sublist}
\item D'apr\`es le lemme chinois (appliqu\'e \`a
$15=3\times 5$ et $35=5\times 7$), le syst\`eme donn\'e
est \'equivalent \`a
\begin{eqnarray*}
x & \equiv & a \;\;(3) \\
x & \equiv & a \;\;(5) \\
x & \equiv & b \;\;(5) \\
x & \equiv & b \;\;(7)
\end{eqnarray*}
Ce dernier syst\`eme est contradictoire, sauf si $a\equiv b\;\;(5)$.
Si cette condition est remplie, le syst\`eme est \'equivalent
au syst\`eme
\begin{eqnarray*}
x & \equiv & a \;\;(3) \\
x & \equiv & a \;\;(5) \\
x & \equiv & b \;\;(7)
\end{eqnarray*}
qui admet une solution puisque $3,5,7$ sont premiers entre eux
deux \`a deux. En conclusion, {\em le syst\`eme admet
une solution si et seulement si $a \equiv b \;(5)$.}
\item Si les conditions sont remplies, le dernier syst\`eme est
\'equivalent \`a 
\begin{eqnarray*}
x & \equiv & a \;\;(15) \\
x & \equiv & b \;\;(7)
\end{eqnarray*}
L'\'equation de B\'ezout $15-2\times 7=1$ montre que 
\[
x \equiv -14 \,a+ 15 b\;(105).
\]
\end{sublist}

\item 
\begin{sublist}
\item On a $2^4\equiv -1 \;(17)$ et donc $2^8\equiv 1\;(17)$.
Ainsi, 
\[
a = \sum_{k=0}^{999} 2^k = 2^{1000} -1 \equiv 1 -1 \equiv 0 \;(17).
\]
Donc $r=0$.

\item Le nombre $p=113$ est premier. Par le petit th\'eor\`eme
de Fermat, il s'ensuit que $r=1$.

\item Nous avons $b=323= 17\times 19$ et donc
$\phi(b)=\phi(17)\,\phi(19)=16\times 18=288$. Ainsi,
nous avons $243^{288}\equiv 1\;(323)$ d'apr\`es le
th\'eor\`eme d'Euler. D'o\`u
$243^{289}\equiv 243\;(323)$ et $r=243$.

\item Nous avons $b=25\times 13$. D'apr\`es le lemme chinois,
il suffit de d\'eterminer les restes de $r$ modulo $25$
et $13$. Puisque 
\begin{eqnarray*}
80 & \equiv & 5\;\;(25) \\
80 & \equiv & 2\;\;(13)
\end{eqnarray*}
il s'ensuit que
\begin{eqnarray*}
80^{206} & \equiv & 0\;\;(25) \\
80^{206} & \equiv & 2^{206}\;\;(13).
\end{eqnarray*}
(Pour la premi\`ere congruence, nous avons utilis\'e que
$5^2\equiv 0\;(25)$). D'apr\`es le petit th\'eor\`eme
de Fermat, nous avons $2^{12}\equiv 1\;(13)$. Puisque
$206\equiv 2\;(12)$, il s'ensuit que $2^{206}\equiv 2^2 \;(13)$.
Donc 
\begin{eqnarray*}
a & \equiv & 0\;\;(25) \\
a & \equiv & 4\;\;(13)
\end{eqnarray*}
Par l'\'equation de B\'ezout $-25+2\times 13=1$, nous trouvons
que 
\[
a \equiv 4\times(-25) \equiv -100 \equiv 225\;(325).
\]
Donc $r=225$.
\end{sublist}

\item 
\begin{sublist}
\item Si $k$ ou $l$ contient un facteur carr\'e, alors
$kl$ contient un facteur carr\'e et les deux c\^ot\'es
s'annulent. Si $k=1$ ou $l=1$, l'affirmation est
triviale. Finalement, si $k=p_1 \ldots p_r$ et $l=q_1 \ldots q_s$
o\`u les $p_i$ et les $q_j$ sont des nombres premiers
distincts, alors
\[
kl= p_1 \ldots p_r q_1 \ldots q_s
\]
o\`u tous les facteurs sont distincts (car $k$ et
$l$ sont premiers entre eux). Donc 
$\mu(kl)= (-1)^{r+s}= \mu(k) \,\mu(l)$.

\item Soit $s(n)=\sum_{d|n} \mu(d)$ et $p_1,\ldots, p_r$
les facteurs premiers (sans r\'ep\'etition) de $n$.
On a $s(n)= s(p_1 \ldots p_r)$, car les diviseurs
qui contiennent une puissance $>1$ d'un $p_i$ ne contribuent
pas \`a $s(n)$. On peut donc supposer que $n=p_1 \ldots p_r$.
Soit $D$ l'ensemble des diviseurs de $p_2 \ldots p_n$.
Alors nous avons clairement
\[
s(n) = \sum_{d\in D} \mu(d) + \sum_{d\in D} \mu(p_1 d).
\]
Or par la multiplicativit\'e de $\mu$, nous avons
$\mu(p_1 d) = \mu(p_1) \mu(d) = -\mu(d)$ pour tout $d\in D$, 
car $p_1$ est premier avec $p_2 \ldots p_r$. D'o\`u $s(n)=0$.

\item Nous avons
\begin{eqnarray*}
\sum_{d|n}\, \mu(\frac{n}{d}) \,g(d)  & = &
	\sum_{d|n}\, \mu(\frac{n}{d}) \,(\sum_{d'|d} f(d')) = 
	\sum_{d'|d|n}\, \mu(\frac{n}{d}) \,f(d') =
	\sum_{d'd'' | n} \mu(d') f(d'') \\
	& = & \sum_{d'' | n} f(d'') \sum_{d' | n/d''} \mu(d') =
	f(n) + \sum_{d''|n, d''<n} f(d'') \sum_{d'| n/d''} \mu(d')  \\
	& = &  f(n) \ko
\end{eqnarray*}
o\`u nous avons utilis\'e b) pour la derni\`ere \'egalit\'e.

\item Nous savons que 
\[
n= \sum_{d|n} \phi(d).
\]
Si nous appliquons c) \`a la fonction $f(n)=\phi(n)$,
nous trouvons donc
\[
g(n) = n
\]
et par cons\'equent
\[
\phi(n) = f(n) = \sum_{d|n} \mu(\frac{n}{d}) g(d) = 
                 \sum_{d|n} \mu(\frac{n}{d}) d.
\]

\end{sublist}

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

\item Comme $p$ est
premier, on sait que le groupe $G$ est cyclique.
Soit $g$ un g\'en\'erateur. Nous avons $f(g)= g^a$ pour
un entier $a$ unique modulo $p-1$. Si $x=g^b$ est un
\'el\'ement quelconque de $G$, nous avons 
$f(x)= f(g^b)=f(g)^b= (g^a)^b= (g^b)^a = x^a$.
Donc l'entier $a$ v\'erifie bien les propri\'et\'es
requises.
