\documentstyle[12pt]{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{\plus}{\oplus}
\newcommand{\pgcd}{\mbox{PGCD}\,}


% 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}}}
%Comma, forall
\newcommand{\ko}{\: , \;}
\newcommand{\fa}{\forall \,}
%Overline, Underline
\newcommand{\ol}{\overline}
\newcommand{\ul}{\underline}



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

\font\tenmsb=msbm10
\font\sevenmsb=msbm7
\font\fivemsb=msbm5
\newfam\msbfam
\textfont\msbfam=\tenmsb
\scriptfont\msbfam=\sevenmsb
\scriptscriptfont\msbfam=\fivemsb
\def\Bbb#1{{\tenmsb\fam\msbfam#1}}
%
\font\teneuf=eufm10
\font\seveneuf=eufm7
\font\fiveeuf=eufm5
\newfam\euffam
\textfont\euffam=\teneuf
\scriptfont\euffam=\seveneuf
\scriptscriptfont\euffam=\fiveeuf
\def\goth#1{{\teneuf\fam\euffam#1}}


\begin{document}
\begin{center}
MT 282 	        \hfill Universit\'e Paris 7 \\
29/05/96	\hfill  U.F.R. de Math\'ematiques\\
\mbox{ }	\hfill P.~Perrin/B.~Keller\\[0.5cm]
{\large\bf Exercices sur la structure multiplicative de $\Z/n\Z$}
\end{center}

\begin{list-of-exercises}
% LaTeX 
%
% exo3.tex exercices sur la structure multiplicative de Z/nZ pour MT 
%

\item  Quel est le reste dans la division par $17$ de  $2^{1996}$ ?

\item Trouver \`a quoi est congru  $1995^{1995}$  modulo  $23$.

\item Soit  $n$  un entier premier avec $10$. Montrer qu'il admet
un multiple dont l'\'ecriture d\'ecimale ne comporte que des $1$.

\item Montrer que les entiers de la forme  $4\times14^k + 1$ 
(o\`u  $k$  est au moins \'egal \`a  $1$ ) ne sont pas premiers (on pourra
les regarder modulo $3$ ou $5$).

\item Montrer que les entiers de la forme  $521\times12^k + 1$
(o\`u  $k$  est au moins \'egal \`a  $1$ ) ne sont pas premiers (on pourra
les regarder modulo $5$, $13$  ou  $29$).

\item Soit  $2^n - 1$  un nombre de Mersenne. Montrer que, pour
$n$  premier inf\'erieur ou \'egal \`a  $7$, le nombre  $2^n - 1$ est premier.

\item Consid\'erons les deux nombres de Mersenne  $2^{11} - 1$ et
$2^{13} - 1 $. Chercher les facteurs premiers possibles de ces deux nombres.
On pourra tout d'abord majorer ces facteurs possibles par la racine carr\'ee 
du nombre en question. Ensuite remarquer que, si  $p$  divise  $2^n - 1$,
alors  $2^n$  est congru \`a  $1$  modulo  $p$  et que donc l'ordre de  $2$
divise $n$. 

\item Trouver les facteurs premiers de  $3^{12} - 1 = 531440$.
On pourra op\'erer comme ci-dessus en ajoutant la recherche des facteurs 
premiers des nombres  $3^d - 1$  o\`u  $d$  est un diviseur propre de $12$.

\item M\^eme exercice que ci-dessus avec le nombre  $2^{35} - 1$.

\item (Il s'agit de la g\'en\'eralisation des exercices 
pr\'ec\'edents) Soit  $p$ un facteur premier du nombre  $a^n - 1$ (o\`u  $a$
d\'esigne un entier naturel sup\'erieur ou \'egal \`a  $2$ ). Montrer que soit
$p$ divise un nombre de la forme  $a^d - 1$ (o\`u  $d$  est un diviseur de $n$
et $d$  est distinct de  $n$), soit  $p$  est congru \`a  $1$ modulo $n$. 
Montrer de plus que, si $p$ et $n$ sont impairs, le nombre  $p$  est congru 
\`a  $1$  modulo  $2n$.

\item Montrer que les quatre premiers nombres de Fermat (de la
forme  $2^a + 1$  o\`u  $a$  est une puissance de  $2$ ) sont \'egaux \`a  $3$,
$5$, $17$  et  $257$  et sont premiers.

\item Soit  $b$  un entier premier \`a  $m$ (o\`u  $m$  est
strictement sup\'erieur \`a $2$ ) et  $a, c$  deux entiers naturels. Montrer
que, si  $b^a$  est congru \`a  $-1$  modulo  $m$  et $b^c$  est congru \`a 
$\pm1$  modulo  $m$, alors  $b^d$ est congru \`a  $-1$  modulo  $m$  et  
$a/d$  est impair ($d$  d\'esigne le pgcd de  $a$  et  $c$).

\item (suite) Si  $p$  est un facteur premier de  $b^n + 1$ 
alors soit  $p$  divise un nombre de la forme  $b^d + 1$  (o\`u  $d$  est un 
diviseur propre de  $n$  et  $n/d$  est impair), soit  $p$  est congru \`a 
$1$  modulo  $2n$.

\item (application) Soit  $m$ l'entier  $2^{24} + 1$ (il vaut
$16\ 777\ 217$). Trouver un nombre premier de Fermat qui divise  $m$. Montrer
que tout autre facteur premier de  $m$  est congru \`a  $1$  modulo  $48$.

\item Montrer que  $341$  divise  $2^{341}-2$ sachant que 
$341 = 11\times 31$.


\bigskip


	Dans les exercices suivants le fait que  $(\Bbb Z /p \Bbb Z)^{*}$ soit 
cyclique d'ordre  $p-1$ ($p$ est suppos\'e premier) n'est pas n\'ecessaire.
Ce r\'esultat peut toutefois servir de guide dans la recherche d'une solution.
\bigskip

\item  Trouver l'ordre de tous les \'el\'ements de 
$(\Bbb Z/29\Bbb Z)^{*}$ (vu comme groupe multiplicatif). En d\'eduire un 
isomorphisme explicite de ce groupe sur le groupe $(\Bbb Z/28\Bbb Z,+)$ .

\item Trouver toutes les solutions des \'equations suivantes :

$x^3 = 1$  dans  $\Bbb Z/19\Bbb Z$  et  

$x^4 = 1$  dans  $\Bbb Z/17\Bbb Z$.

\item Discuter l'\'equation  $x^3 = a$  dans  $\Bbb Z/13\Bbb Z$
suivant les valeurs de l'\'el\'ement  $a$.

\item R\'esoudre l'\'equation  
$1 + x + x^2 + x^3 + x^4 + x^5 + x^6 = 0$  dans  $\Bbb Z/29\Bbb Z$.

\item Montrer que la somme des carr\'es de  $\Bbb F_p$  est
congrue \`a  $0$  modulo $p$  d\`es que  $p$  est au moins \'egal \`a  $5$.

En d\'eduire que le nombre suivant
$$
u_p=1+{1\over2}+\cdots+{1\over{p-1}}
$$
(o\`u  $p$  est un nombre premier) s'\'ecrit
$$
u_p={{A_p}\over{B_p}}
$$
o\`u  $A_p$  et  $B_p$ sont premiers entre eux et  $A_p$  est divisible par
$p^2$.
\bigskip

	Les exercices suivants utilisent le fait qu'un \'el\'ement est un 
carr\'e dans  $\Bbb F_p$ si et seulement si  $x^{{(p-1)}\over2}$ est \'egal 
\`a  $1$.


\bigskip
\item  Montrer que  $-1$  est une puissance quatri\`eme dans  
$\Bbb Z /p \Bbb Z$ (o\`u  $p$ est premier) si et seulement si  $p$  est 
congru \`a  $1$  modulo  $8$.

\item On cherche \`a \'etudier pour quels nombres premiers $p$
l'\'el\'ement  $2$ est un carr\'e dans  $\Bbb F_p$. On va donc calculer 
$2^{{(p-1)}\over 2}$  modulo  $p$. Soit  $\zeta$  la racine huiti\`eme de 
l'unit\'e donn\'ee par  $\exp(2\pi i/8)$.
\begin{sublist}
	\item Montrer que  $\zeta$  v\'erifie les relations suivantes : 
$\zeta^2 = i$, $\zeta + \zeta^{-1}=\sqrt{2}$, $\zeta^2 + \zeta^{-2} = 0$
, $\zeta^3 + \zeta^{-3} = -\sqrt{2}$ et $\zeta^4 + \zeta^{-4} = -2$.
En d\'eduire que, si on note  $y$  l'\'el\'ement $\zeta + \zeta^{-1}$, on a
$y^2 = 2$.

	\item Comme  $p$ est impair, on notera  $h = (p - 1)/2$  ou encore 
$p = 1 + 2h$. V\'erifier que  $y^p \zeta^p$  et  $y^p \zeta$  sont 
\'el\'ements de  $\Bbb Z[i]$. Montrer que  $y^p \zeta^p$  est congru 
dans  $\Bbb Z[i]$  \`a  $1 + i^p$. En d\'eduire que $y^{2h}\times (y\zeta)$
est congru \`a  $i^{-h}+ (-1)^h i^{1-h}$ modulo  $p$  dans  $\Bbb Z[i]$.

	\item	Utiliser ce qui pr\'ec\`ede pour \'evaluer $2^{(p-1)/2}= y^{p-1}
= y^{2h}$  modulo  $p$. En conclure que $2$ est un carr\'e modulo  $p$  si et
seulement si  $p$  est congru \`a  $\pm1$  modulo  $8$.
\end{sublist}

\bigskip
	Voici une autre d\'emonstration du r\'esultat ci-dessus.
\bigskip


\item Supposons que  $p$  soit premier et congru \`a  $1$ 
modulo  $8$. On pose $p =1 + 8m$.
\begin{sublist}
	\item En \'ecrivant, dans le produit  $A = 2.4.\cdots 4m.(4m+2).\cdots
 (8m-2).8m$, les entiers  $4m+2,\cdots, 8m$  sous la forme  $p-(4m-1-2h)$
(o\`u  $h$  varie entre  $0$  et  $2m- 1$ ) montrer que  $A = 24m(4m)!$.

	\item Remarquer que, pour la m\^eme raison,  $A$  est congru \`a
$(4m)!$ modulo  $p$.

	\item En conclure que  $2$  est un carr\'e modulo  $p$ .
\end{sublist}
\bigskip
	Pour m\'emoire voici un exercice d'une liste pr\'ec\'edente.
\bigskip


\item Il s'agit dans cet exercice de montrer que  $-3$ est un
carr\'e modulo  $p$  si  $p$  est un nombre premier dans  $\Bbb Z$  congru \`a
$1$  modulo  $3$ . Nous avons utilis\'e ce r\'esultat dans le cours pour 
\'etablir la liste des nombres premiers dans  $\Bbb Z[j]$.

	Soit  $p$  un nombre premier dans  $\Bbb Z$  congru \`a  $1$  modulo
$3$. Remarquer que  p est n\'ecessairement impair. On sait que  $-3$  est un 
carr\'e dans  $\Bbb F_p$  si et seulement si  $a = (-3)^{{(p-1)}\over2}$ est 
\'egal \`a  $1$  modulo  $p$ (voir le cours). Nous allons calculer $a$.
Montrer que  $-3 = (2j + 1)^2$. Montrer que  $a$ est congru \`a  $1$
modulo  $p$  dans  $\Bbb Z[j]$ donc dans  $\Bbb Z$. 


\bigskip
	L'exercice suivant porte sur le cinqui\`eme nombre de Fermat. On note 
$F_5$  ce nombre. Il vaut  $2^{32} + 1$  puisque  $2^5 = 32$. On notera $p$
un facteur premier (\`a priori quelconque) de  $F_5$. Au fait on a
$$
F_5 = 4\ 294\ 967\ 296 + 1 = 4\ 294\ 967\ 297.
$$
\bigskip



\item
\begin{sublist}
	\item En reprenant les notations pr\'ec\'edentes montrer que  $2$
est d'ordre  $2^6$ dans  $\Bbb F_p$. En conclure que $p$ est congru \`a $1$
modulo  $2^6$. 

	\item En utilisant l'exercice 22 ou 23 remarquer que  $2^{{(p-1)}\over2}$
est congru \`a  $1$ modulo  $p$. En conclure que  ${(p-1)}\over2$  est 
divisible par $2^6$ et que $p$ est congru \`a  $1$ modulo  $2^7$.

	\item En recherchant les nombres premiers de la forme  $1 + k\times 2^7 =
1 + 128k$, montrer que pour  $k = 5$  on obtient le nombre $641$ qui est un 
facteur de  $F_5$. Le quotient valant  $6\ 700\ 417$.
[Ce dernier r\'esultat fut remarqu\'e par Euler en 1732]

	\item Remarquer que $(1 + 21\times128)^2$  est sup\'erieur \`a 
$6\ 700\ 417$. En cherchant les nombres premiers de la forme  $1 + 128k$  o\`u
$k$  varie entre  $1$  et  $20$, montrer qu'aucun ne divise  $6\ 700\ 417$. 
En conclure que ce dernier nombre est premier. 
[Euler avait aussi d\'emontr\'e ce r\'esultat]
\end{sublist}

\end{list-of-exercises}

\end{document}


