diff options
| author | David A. Madore <david+git@madore.org> | 2010-10-04 15:07:52 +0200 |
|---|---|---|
| committer | David A. Madore <david+git@madore.org> | 2010-10-04 15:07:52 +0200 |
| commit | 30b4ef2ae7f9391e948a5a1369886ebfdd58a6e0 (patch) | |
| tree | 4beab5261c10fb860d1793f967b046fe4eebf572 | |
| parent | 45c9e74d2fc91a01f24e083e192500018bf4d3de (diff) | |
| download | infmdi720-30b4ef2ae7f9391e948a5a1369886ebfdd58a6e0.tar.gz infmdi720-30b4ef2ae7f9391e948a5a1369886ebfdd58a6e0.tar.bz2 infmdi720-30b4ef2ae7f9391e948a5a1369886ebfdd58a6e0.zip | |
Start writing a list of exercises.
| -rw-r--r-- | exercices.tex | 170 |
1 files changed, 170 insertions, 0 deletions
diff --git a/exercices.tex b/exercices.tex new file mode 100644 index 0000000..243bf28 --- /dev/null +++ b/exercices.tex @@ -0,0 +1,170 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt]{article} +\usepackage[francais]{babel} +\usepackage[latin1]{inputenc} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\exercice{% +\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} +\newcommand{\limp}{\mathrel{\Rightarrow}} +\newcommand{\liff}{\mathrel{\Longleftrightarrow}} +\newcommand{\pgcd}{\operatorname{pgcd}} +\newcommand{\ppcm}{\operatorname{ppcm}} +\newcommand{\signe}{\operatorname{signe}} +\newcommand{\tee}{\mathbin{\top}} +\newcommand{\Frob}{\operatorname{Fr}} +% +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrig�.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\relax\else\egroup\fi\par} +% +% +% +\begin{document} +\ifcorrige +\title{INFMDI720\\Exercices --- Corrig�\\{\normalsize Rappels math�matiques pour la cryptographie}} +\else +\title{INFMDI720\\Exercices\\{\normalsize Rappels math�matiques pour la cryptographie}} +\fi +\author{} +\date{} +\maketitle +\pretolerance=10000 +\tolerance=8000 + +% +% +% + +\exercice + +(A)�Quel entier entre $0$ et�$100$ est congru � $19$ modulo�$13$ et � +$13$ modulo�$19$�? + +\begin{corrige} +(A)�Commen�ons par trouver un entier qui convient. On pourrait se + rendre compte que $19+13 = 32$ convient pour des raisons de + sym�trie. Pour proc�der de fa�on plus syst�matique, cherchons une + relation de B�zout entre $19$ et�$13$, qui sont visiblement premiers + entre eux (et ceci va de toute fa�on le confirmer)�: on a $19 = 1\times 13 + + 6$ puis $13 = 2\times 6 + 1$ donc le pgcd est bien�$1$, et on a $1 = + 13 - 2\times 6 = 3\times 13 - 2\times 19$. Ainsi, d'apr�s un + r�sultat du cours (version ��effective�� du th�or�me chinois), un + nombre congru � $19$ (soit�$6$) modulo�$13$ et � $13$ modulo�$19$ + est donn� par $3 \times 13 \times 13 - 2 \times 19 \times 6$�: ceci + vaut $279$, mais pour simplifier les calculs on pouvait calculer + $3\times 13 \equiv 1 \pmod{19}$ et $-2 \times 6 \equiv 1 \pmod{13}$, + donc il reste $13 + 19 = 32$. En tout �tat de cause, comme $13$ et + $19$ sont premiers entre eux, les nombres congrus � $x$ modulo�$13$ + et � $y$ modulo�$19$, quels que soient $x$ et�$y$ entiers, forment + une unique classe de congruence modulo�$13 \times 19 = 247$ (qu'il + n'�tait pas vraiment n�cessaire de calculer, seul importe que ce + soit�$>100$, ce qui est �vident), donc d�s qu'on a trouv� un nombre + v�rifiant les congruences demand�es (en l'occurrence�$32$), on sait + que les autres sont les nombres qui lui sont congrus modulo�$13 + \times 19$, et en particulier il n'y en a pas d'autre entre $0$ + et�$100$. +\end{corrige} + +\ifcorrige\medbreak\else\relax\fi + +(B)�Quel entier � trois chiffres en base�$10$ se termine par�$23$ et +est multiple de�$19$�? + +\begin{corrige} +(B)�Se terminer par�$23$ en base�$10$ signifie �tre congru � $23$ + modulo�$100$. Cherchons une relation de B�zout entre $100$ et�$19$ + qui sont premiers entre eux�: on a $100 = 5\times 19 + 5$ et $19 = + 3\times 5 + 4$ et $5 = 1\times 4 + 1$ donc $1 = 5 - 4 = 4 \times 5 - 19 = 4 + \times 100 - 21 \times 19$. Ainsi, d'apr�s un r�sultat du cours + (version ��effective�� du th�or�me chinois), un nombre congru � $23$ + modulo�$100$ et � $0$ modulo�$19$ (i.e., divisible par�$19$) est + donn� par $- 21 \times 19 \times 23$�: ceci vaut $-9177$, mais pour + simplifier les calculs on pouvait calculer $-21\times 23 \equiv -83 + \equiv 17 \pmod{100}$ et ainsi $- 21 \times 19 \times 23 \equiv 17 + \times 19 = 323 \pmod{1900}$. Le nombre $323$ r�pond aux conditions + demand�es, et comme tout les entiers congrus � $23$ modulo�$100$ et + � $0$ modulo�$19$ forment une unique classe de congruence + modulo�$1900$, on a trouv� le seul nombre � trois chiffres. +\end{corrige} + +\ifcorrige\medbreak\else\relax\fi + +(C)�Quel entier entre $0$ et�$100$ est congru respectivement � +$1,2,3,4$ modulo $2,3,5,7$�? (C'est-�-dire�: congru � $1$ modulo�$2$, +et � $2$ modulo�$3$, et � $3$ modulo�$5$, et � $4$ modulo�$7$.) + +\begin{corrige} +(C)�Les nombres $2,3,5,7$ sont premiers entre eux deux � deux. + Commen�ons par trouver des solutions � deux congruences + simultan�es�: comme les nombres sont assez petits, il est plus + simple de le faire par t�tonnement�: par exemple, $5$ est congru � + $1$ modulo�$2$ et � $2$ modulo�$3$, cela se trouve imm�diatement en + parcourant les entiers de $0$ � $5$ ou plus astucieusement ceux qui + v�rifient une des deux congruences pour chercher ceux qui v�rifient + l'autre. Comme on va vouloir mettre ensuite ensemble deux + congruences de ce genre, il vaut mieux les trouver de m�me taille + et, si possible, v�rifiant une relation de B�zout simple�: le plus + �conomique est donc de mettre $2$ avec�$7$ et $3$ avec $5$, ce qui a + le bon go�t que $1\times 15 - 1\times 14 = 1$ est une relation de B�zout �vidente + entre $3\times 5$ et $2\times 7$. Par t�tonnement, on trouve que + $11$ (et exactement les nombres de sa classe modulo�$14$) est congru + � $1$ modulo�$2$ et � $4$ modulo�$7$, et que $8$ (et exactement les + nombres de sa classe modulo�$15$) est congru � $2$ modulo�$3$ et � + $3$ modulo�$5$. Avec la relation de B�zout $1\times 15 - 1\times 14 + = 1$, toujours en appliquant la m�me version ��effective�� du + th�or�me chinois, on voit que les entiers v�rifiant les quatre + congruences demand�es sont exactement la classe de $1\times 15\times + 11 - 1\times 14\times 8 = 53$ modulo $15 \times 14 = 210$, donc le + seul entre $0$ et $100$ est�$53$. +\end{corrige} + +\ifcorrige\medbreak\else\relax\fi + +(D)�D�terminer tous les entiers entre $0$ et $2009$ congrus � $1$ +modulo chacun des nombres $7$, $11$ et�$13$. (C'est-�-dire�: congrus +� $1$ modulo�$7$, et � $1$ modulo�$11$, et � $1$ modulo�$13$.) +(Indication�: y-t-il un nombre �vident qui r�pond � cette condition�?) + +\begin{corrige} +(D)�Comme le sugg�re l'indication, il y a un nombre �vident congru � + $1$ modulo $7$ et $11$ et $13$ � la fois, c'est $1$ lui-m�me. Le + th�or�me chinois assure que, comme $7$ et $11$ et $13$ sont premiers + entre eux deux � deux, les entiers congrus � $1$ modulo chacun d'eux + forment une classe de congruence modulo $7 \times 11 \times 13 = + 1001$. Les nombres entre $0$ et $2009$ v�rifiant les congruences + demand�es sont donc�: $1$, $1002$ et $2003$. +\end{corrige} + +\ifcorrige\medbreak\else\relax\fi + +(E)�D�terminer tous les entiers entre $0$ et $100\,000$ congrus � +$192$ modulo�$300$ et � $169$ modulo�$305$. + +\begin{corrige} +(E)�Un entier congru � $192$ modulo�$300$ est (comme $5|300$) congru � + $192 \equiv 2$ modulo�$5$, et un entier congru � $169$ modulo�$305$ + est (comme $5|305$) congru � $169 \equiv 4$ modulo�$5$. Comme $2 + \not\equiv 4 \pmod{5}$, il n'existe \emph{aucun} entier v�rifiant + les deux congruences demand�es. +\end{corrige} + +% +% +% +\end{document} |