summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordavid <david>2008-12-08 17:59:36 +0000
committerdavid <david>2008-12-08 17:59:36 +0000
commit0684099989ef1913b1650f5258765a1e5c0a1990 (patch)
treecf3bfe8a270fb5ad6395af7bf3a9be3dda5f41ee
parentf60f1fe89e1ab4b45c09e7f4472ff4e7262bc7b1 (diff)
downloadinfmdi720-0684099989ef1913b1650f5258765a1e5c0a1990.tar.gz
infmdi720-0684099989ef1913b1650f5258765a1e5c0a1990.tar.bz2
infmdi720-0684099989ef1913b1650f5258765a1e5c0a1990.zip
Solution to first exercice.
-rw-r--r--controle-20081202.tex32
1 files changed, 32 insertions, 0 deletions
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épendantes.
(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}
+
%
%
%