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

\begin{list-of-exercises}

\item Soit $x$ le nombre de pistolets \`a eau que poss\`ede Jean.
D'apr\`es les informations fournies, nous avons
\begin{eqnarray*}
x & \equiv & 9  \;\; (7) \\
x & \equiv & -1  \;\; (9) \\
x & \equiv & 4 \;\; (8).
\end{eqnarray*}
Les nombres $7,9,8$ sont premiers entre eux deux \`a deux. 
Ce syst\`eme de congruences admet donc une solution 
$x$ dont la classe modulo $7\times 9\times 8 = 504$ 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/504 \iso \Z/7 \plus \Z/9 \plus \Z/8.
\]
Nous avons 
\[
\begin{array}{rcccrcl}
72\, u_1 + 7\, v_1  =  1; & \mbox{sol. part.} & 
72\times (-3) + 7 \times 31  =  1. & \mbox{Posons } & x_1=-216. \\
56\, u_2 + 9\, v_2  =  1; & \mbox{sol. part.} &
56\times (-4) + 8 \times 25   =  1. & \mbox{Posons } & x_2=-224. \\
63\, u_3 + 8\, v_3  =  1; & \mbox{sol. part.} &
63 \times (-1) + 8 \times 8  =  1 & \mbox{Posons } &  x_3=-63 .
\end{array}
\]
Nous avons donc
$x \equiv 9\times (-216)-1\times (-224) +4\times (-63) 
\equiv -1972 \equiv 44 \;\; (504)$. On a donc $x=44+k\times 504$
et si $y$ d\'esigne le nombre d'amis de Jean, on a
$y=(x-9)/7=5+72\,k$. Puisque $y\leq 100$, il s'ensuit que
$x=44$ et $y=5$. {\em Jean poss\`ede 44 pistolets \`a eau
et il a $5$ amis.}


\item 
\begin{sublist}
\item Nous avons $16\equiv 2\;(7)$, donc $16^2\equiv 4\;(7)$,
$16^3\equiv 1\;(7)$ et $16^k\equiv 16^l\;(7)$ si $k\equiv l\; (3)$.
Par cons\'equent
\[
a \equiv B\times (1 + 2 + 4 + 1 + 2 + 4 ) +
         A\times (1 + 2 + 4 + 1 + 2 + 4 ) 
   \equiv 0\;\;(7)
\]
et $r=0$.
\item Le nombre $31$ est premier et ne divise pas $19$.
Le petit th\'eor\`eme de Fermat permet donc de conclure
que $19^{30} \equiv 1\;(31)$.
Puisque $330=11\times 30$, nous avons $19^{330} \equiv 1\;(31)$
et $r=1$. 

\item Nous avons $2025=25\times 81$ et $\phi(2025)=
\phi(25)\phi(81)= 20\times 54 = 1080$. Le nombre
$532=4\times 7\times 19$ est premier avec $2025$.
D'apr\`es le th\'eor\`eme d'Euler, nous avons
$532^{1080}\equiv 1\;(2025)$ et donc $532^{2160}\equiv 1\;(2025)$
car $2160=2\times 1080$. Donc $r=1$.

\item Nous avons $437=19\times 23$. 
Comme $19$ et $23$ sont premiers entre eux, il suffit de
calculer les restes de $a$ par $19$ et $23$ pour conna\^{\i}tre
le reste de $a$ par $437$, d'apr\`es le lemme chinois.
Nous avons
\begin{eqnarray*}
a  &\equiv & 217^{18} \equiv 8^{18}             \equiv 1      \;(19)\\
a & \equiv & 217^{18} \equiv 10^{18}\; (23).
\end{eqnarray*}
Ici, nous avons utilis\'e le petit th\'eor\`eme de Fermat pour calculer
que $8^{18}\equiv 1\;(19)$. Nous avons 
$10^2\equiv 8\;(23)$,
$10^4\equiv 18\;(23)$, 
$10^8\equiv 2\;(23)$, 
$10^{16}\equiv 4\;(23)$ et $10^{18}\equiv 8\times 4 \equiv 9\;(23)$.  Donc 
\begin{eqnarray*}
a & \equiv & 1\;(19) \\
a & \equiv & 9\;(23).
\end{eqnarray*}

Nous avons $5\times 23 - 6\times 19=1$ et
donc $a \equiv 5\times 23 -9\times 6\times 19 \equiv -37 \;(437)$.
Donc $r=400$.
\end{sublist}


\item Supposons que $p$ ne divise pas $n$. Alors $p$ et $n$ sont
premiers entre eux et on a donc 
\[
\phi(p\,n)=\phi(p^{k+1}\,n')=\phi(p)\, \phi(n).
\]
Puisque $p$ est premier, on a $\phi(p)=p-1$. Donc on a
$\phi(p\,n)=(p-1)\,\phi(n)$, si $p$ ne divise pas $n$. 

Supposons maintenant que $p$ divise $n$ et que 
$n=p^k\, n'$ o\`u $k\geq 1$
et $p$ ne divise pas $n'$. Alors toute puissance de $p$
est premi\`ere avec $n'$
et on a donc $\phi(p\,n)= \phi(p^{k+1})\, \phi(n)$.
Comme $p$ est premier, on a $\phi(p^{k+1}) = p^{k+1} -p^k$.
Donc finalement, on a 
\begin{eqnarray*}
\phi(p\,n)& = & \phi(p^{k+1}\,n')= (p^{k+1} -p^k)\, \phi(n')
                            = p\, (p^{k}-p^{k-1})\,\phi(n') \\
          & = & p\, \phi(p^{k})\,\phi(n')
                            = p\, \phi(p^k\, n') \\
          & = & p\, \phi(n).
\end{eqnarray*}

\item 
\begin{sublist}
\item
Nous avons $75=3\times 25$ et $45=9\times 5$. Comme
$\pgcd(3,25)=1$ et $\pgcd(9,5)=1$, le lemme chinois
montre que le syst\`eme est 
\'equivalent au syst\`eme de quatre congruences
\[
\begin{array}{cccc}
x & \equiv & c & (3) \\
x & \equiv & c & (25) 
\end{array}
\quad\quad
\begin{array}{cccc}
x & \equiv & 6 & (9) \\
x & \equiv & 1 & (5) .
\end{array}
\]
Nous r\'e\'ecrivons ces congruences dans un ordre diff\'erent :
\begin{eqnarray}
x & \equiv & 6 \;\;(9) \\
x & \equiv & c \;\;(3) \\
x & \equiv & c \;\;(25) \\
x & \equiv & 1 \;\;(5) .
\end{eqnarray}
Si ce syst\`eme poss\`ede une solution $x\in\Z$, la congruence
$(1)$ implique que $x \equiv 0\;(3)$. La congruence $(2)$
montre alors que $c\equiv 0\; (3)$. De m\^eme la congruence
$(3)$ implique que $x \equiv c \; (5)$ et la congruence $(4)$
donne que $c\equiv 1\;(5)$. Ainsi, le nombre entier $c$ doit
satisfaire les conditions
\begin{eqnarray*}
c & \equiv & 0 \;\; (3) \\
c & \equiv & 1 \;\; (5).
\end{eqnarray*}
R\'eciproquement, si ces conditions sont remplies, la congruence
$(2)$ r\'esulte de $(1)$, et $(4)$ r\'esulte de $(3)$. Ainsi
les conditions ci-dessus sont n\'ecessaires et suffisantes pour
que le syst\`eme admette une solution. Par le lemme chinois
$(\pgcd(3,5)=1)$, nous pouvons conclure que le syst\`eme admet
une solution ssi $c \equiv 6\;(15)$ c'est-\`a-dire que
{\em la classe $\ol{c}$ de $c$ modulo $75$ est 
$\ol{6}, \ol{21}, \ol{36}, \ol{51}$ ou $\ol{66}$.}

\item Nous avons vu dans a) que si $c\equiv 6\;(9)$, le syst\`eme
est \'equivalent \`a
\begin{eqnarray*}
x & \equiv & 6 \;\;(9) \\
x & \equiv & c \;\;(25) 
\end{eqnarray*}
Les nombres $9$ et $25$ sont premiers entre eux et nous
avons l'identit\'e de B\'ezout $(-11)\times 9 + 4 \times 25 = 1$.
Le syst\`eme est donc \'equivalent \`a 
\[
x \equiv 6 \times 4\times 25  + c \times (-11) \times 9
\equiv 150 - 99\times c \;\;(225).
\]
{\em Si $c$ est congru \`a $6, 21, 36, 51$ et $66$ modulo $75$
nous trouvons que $x$ est congru \`a 
$6, 96, 186, 51$ et $141$ modulo $225$, respectivement.}
\end{sublist}


\item 
\begin{sublist}
\item On a $\sigma(1)=1$, $\sigma(2)=1+2=3$, $\sigma(3)=4$,
$\sigma(5)=6$, $\sigma(6)=1+2+3+6=13$, $\sigma(7)=8$, 
$\sigma(8)=1+2+4+8= 15$, $\sigma(9)=1+3+9=12$ et
$\sigma(10)= 1+2+5+10=18$.

\item La liste des diviseurs positifs 
de $p^k$ est $1, p, p^2, \ldots, p^k$.
Donc
\[
\sigma(p^k)= 1+p+p^2+ \cdots + p^{k} = \frac{p^{k+1}-1}{p-1}.
\]

\item Soient
\[
r=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}
\mbox{ et }
s=q_1^{f_1} q_2^{f_2} \cdots q_k^{f_k}
\]
les d\'ecompositions de $r$ et $s$ en produit de puissances 
strictement positives de nombres premiers distincts deux \`a deux.
Comme $r$ et $s$ sont premiers deux \`a deux, les ensembles
des $p_i$ et celui de $q_j$ sont disjoints. Ainsi,
\[
rs=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \, q_1^{f_1} q_2^{f_2} 
   \cdots q_k^{f_k} 
\]
est la d\'ecomposition de $rs$ en produit de puissances 
strictement positives de nombres premiers distincts deux \`a deux.
Un diviseur de $rs$ est un nombre de la forme
\[
n=p_1^{e'_1} p_2^{e'_2} \cdots p_k^{e'_k} \, q_1^{f'_1} q_2^{f'_2} 
   \cdots q_k^{f'_k} 
\]
o\`u $e'_i\leq e_i$ et $f'_j\leq f_j$ pour tous $i,j$.
Il s'\'ecrit de fa\c{c}on unique comme le produit d'un
diviseur $d$ de $r$ par un diviseur $e$ de $s$, \`a savoir
\[
d=p_1^{e'_1} p_2^{e'_2} \cdots p_k^{e'_k} \ko
e=q_1^{f'_1} q_2^{f'_2} \cdots q_k^{f'_k} .
\]
L'application $\psi$ est donc injective et surjective. 

\item En utilisant c) nous calculons que
\begin{eqnarray*}
\sigma(rs) & = & \sum_{f\in D(rs)} f
          = \sum_{(d,e)\in D(r)\times D(s)} de
          = \sum_{d\in D(r)} \, \sum_{e\in D(s)} de
          = (\sum_{d\in D(r)} d)\, (\sum_{e\in D(s)} e) \\
           & = & \sigma(r) \, \sigma(s).
\end{eqnarray*}



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

\end{document}











