From 0684099989ef1913b1650f5258765a1e5c0a1990 Mon Sep 17 00:00:00 2001
From: david <david>
Date: Mon, 8 Dec 2008 17:59:36 +0000
Subject: Solution to first exercice.

---
 controle-20081202.tex | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

(limited to 'controle-20081202.tex')

diff --git a/controle-20081202.tex b/controle-20081202.tex
index 75c5a8d..7710f9f 100644
--- a/controle-20081202.tex
+++ b/controle-20081202.tex
@@ -25,6 +25,14 @@
 \newcommand{\tee}{\mathbin{\top}}
 \newcommand{\Frob}{\operatorname{Fr}}
 %
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\textit{Corrigé.}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\relax\else\egroup\fi\par}
+%
 %
 %
 \begin{document}
@@ -79,6 +87,30 @@ Les deux questions suivantes sont ind
 (2) Pourquoi a-t-on $a^{32} \equiv 1 \pmod{128}$ pour tout $a$ impair
 (note : $128 = 2^7$) ?
 
+\begin{corrige}
+(1) Comme $11$ et $31$ sont premiers entre eux,
+  $\mathbb{Z}/341\mathbb{Z} \cong (\mathbb{Z}/11\mathbb{Z}) \times
+  (\mathbb{Z}/31\mathbb{Z})$, donc il suffit de prouver $a^{31} \equiv
+  a \pmod{31}$ et $a^{31} \equiv a \pmod{11}$ pour tout $a
+  \in\mathbb{Z}$.  Or on a $a^{31} \equiv a \pmod{31}$ d'après le
+  petit théorème de Fermat ; s'agissant de la relation modulo $11$, on
+  a $a^{10} \equiv 1 \pmod{11}$ si $11$ ne divise pas $a$ (théorème
+  d'Euler), donc $a^{30} = (a^{10})^3 \equiv 1 \pmod{11}$ donc $a^{31}
+  \equiv a \pmod{11}$, et ceci est aussi vrai lorsque $a \equiv 0
+  \pmod{11}$, donc dans tous les cas $a^{31} \equiv a \pmod{11}$.
+
+(2) Le théorème d'Euler ne suffit pas, car $\varphi(128) = 64$ donc il
+  donne seulement $a^{64} \equiv 1 \pmod{128}$ lorsque $a$ est impair
+  (ce qui équivaut à premier à $128$).  En revanche, on sait (cours)
+  que $(\mathbb{Z}/128\mathbb{Z})^\times =
+  (\mathbb{Z}/2^7\mathbb{Z})^\times$ n'a pas d'éléments primitifs : il
+  est produit d'un groupe cyclique d'ordre $2$ (engendré par $-1$) et
+  d'un groupe cyclique d'ordre $2^5 = 32$ (engendré par $5$).  Si on
+  note ces deux groupes multiplicativement, on a $a^{32} = a$ dans
+  chacun d'entre eux par le théorème de Lagrange, donc c'est le cas
+  dans $(\mathbb{Z}/128\mathbb{Z})^\times$.
+\end{corrige}
+
 %
 %
 %
-- 
cgit v1.2.3