\documentclass{letter}%\nopagenumbers
%\magnification\magstep1
%\advance\vsize by 1truecm
\usepackage{isolatin1}
\textwidth=15truecm
\textheight=22.8truecm
\hoffset=-12mm
\voffset=-9mm
\baselineskip=12pt
\font\smc=cmcsc10
%\font\Large=cmr17
\def\R{{\bf R}}
\def\C{{\bf C}}
\def\N{{\bf N}}
\def\Z{{\bf Z}}
\def\ln{{\rm ln}}
\def\m#1{m_{#1}}
\def\v#1{v_{#1}}
\def\z#1{z^{#1}}
\def\y#1{y^{#1}}
\def\p#1{{{\pi}\over{#1}}}
\def\x#1{x^{#1}}
\def\n#1{n^{#1}}
\def\inv#1{{1\over{#1}}}
\def\d{\displaystyle}

\def\ex#1{\vskip 0.4truecm\centerline{#1}\vskip 0.1truecm}
\def\ques#1{\vskip 0.15truecm
\noindent{\bf #1}\hskip 0.4truecm}

\begin{document}


\vskip-0.5cm
\noindent{Universit\'e de Paris-Sud}\hfill  2002\par
\noindent{S2MIAS, option Arithm\'etique et Histoire des
Nombres}\par\hfill {\Large A}
  \vskip 0.8truecm
\centerline{\smc Corrig\'e du test}
\centerline{Lundi 25 mars 2002, dur\'ee 1h}

\vskip.4truecm

\ques{1.}{\sl Soit $a$ un entier tel que $3a\equiv 3~(199)$, et
$b$ un entier tel que $4b\equiv 4~(202)$.

Peut-on
affirmer que $a\equiv 1~(199)$ ?} OUI. D'apr\`es le th\'eor\`eme de
B\'ezout, comme 199 et 3 sont premiers entre eux, il existe des entiers
$u$ et $v$ tels que $199u+3v=1$. Alors $3v\equiv 1~(199)$,
donc $a\equiv 3va\equiv 3v~\equiv 1~(199)$.

\vskip .2cm

{\sl Que $b\equiv 1~(202)$ ?} NON. Par exemple, $b=102$ satisfait
$4b\equiv 4~(202)$ mais n'est pas congru \`a 1 modulo 202.


  \ques{2.}{\sl Artem Kazatchok, le plus vieux centenaire de
l'Ouzbekistan occidental, a v\'ecu 1 000 104 heures. Cela
repr\'esente-t'il un nombre entier de semaines ? On justifiera la
r\'eponse, sans poser de division, par des arguments de
congruences.} \par
OUI. Il s'agit de montrer que $n=$1 000 104 est divisible par
$7\times 24=2^{3}\times 3\times 7$. Les trois derniers chiffres de
$n$ forment 104, qui est divisble par 8, donc $n$ est divisible par
8. La somme des chiffres de $n$ vaut 6, divisible par 3, donc $n$ est
divisible par 3. D'apr\`es le th\'eor\`eme de Fermat, $10^{6}\equiv
1~(7)$, donc $n\equiv 105\equiv 0~(7)$. On conclut que $n$ est
divisible par $7\times 24$ qui est le nombre d'heures dans une
semaine.

\ques{3.}{\sl Montrer que si $n$ est un entier naturel impair, alors
$10^{n}+1$ est divisible par $11$. En d\'eduire que le nombre
1 343 113 431 est divisible par 121.}
\par
$10^{n}\equiv (-1)^{n}\equiv -1~(11)$ si $n$ est impair, donc 11
divise $10^{n}+1$. De plus, $a=$1 343 113 431$=13431\times(10^{5}+1)$
et 13431 est divisible par 11, car la somme altern\'ee de ses chiffres
l'est. Par cons\'equent $a$ est un multiple de $11\times 11=121$.
\vskip .2cm
{\sl Montrer que si $n$ est un entier naturel impair, alors
$10^{3n}+1$ est divisible par $13$. En d\'eduire que le nombre
169 169 000 169 169 est divisible par $13^{4}$.}
\par
$10\equiv -3$, d'o\`u $10^{2}\equiv 9$, d'o\`u $10^{3}\equiv 90\equiv
-1~(13)$, et on conclut que $10^{3n}\equiv (-1)^{n}\equiv -1~(13)$ si
$n$ est impair. De plus, $b=$ 169 169 000 169 169 = 169
169$\times(10^{9}+1)$. Enfin, $c=$ 169 169 = 169$\times(10^{3}+1)$
donc $c$ est divisible par $169\times 13=13^{3}$ et $b$ par
$13\times c$ donc par $13^{4}$.

\ques{4.}{\sl D\'eterminer tous les points $(x,y)$ du plan dont
les deux coordonn\'ees sont des entiers, qui sont sur la
droite affine d'\'equation
$y={{20}\over{9}}x+{1\over{3}}$. }
\par
Il s'agit de r\'esoudre en nombre entiers l'\'equation $9y-20x=3$. Des
divisions euclidiennes successives
$20=2\times 9+2$, $9=4\times 2+1$, on tire
$1=9-4\times 2=9-4\times (20-2\times 9)=9\times 9 - 20\times 4$,
puis $3=9\times 27 - 20\times 12$, d'o\`u une solution particuli\`ere
$x_{0}=12,\,y_{0}=27$. Les autres solutions sont de la forme
$x=12+9k$, $y=27+20k$, o\`u $k$ d\'ecrit $\Z$.

\end{document}

\vfill\eject
\vskip-0.5cm
\noindent{Universit\'e de Paris-Sud}\hfill  2002\par
\noindent{S2MIAS, option Arithm\'etique et Histoire des
Nombres}\par\hfill {\Large B}
  \vskip 0.8truecm
\centerline{\smc Corrig\'e du test}
\centerline{Lundi 25 mars 2002, dur\'ee 1h}
\vskip.4truecm

\ques{1.}{\sl D\'eterminer tous les points $(x,y)$ du
plan dont les deux coordonn\'ees sont des entiers,
qui sont sur la droite affine d'\'equation
$y=-{{17}\over{14}}x-{1\over{7}}$. }
\par
Il s'agit de r\'esoudre en nombre entiers l'\'equation $14y+17x=-2$. Des
divisions euclidiennes successives
$17=1\times 14+3$, $14=4\times 3+2$, $3=1\times 2+1$, on tire
$1=3-1\times 2=3-1\times (14-4\times 3)=-1\times 14+5\times 3$ puis
$1=-1\times 14+5\times(17-1\times 14)=5\times 17-6\times 14$, puis
$-2=14\times 12 - 17\times 10$, d'o\`u une solution particuli\`ere
$x_{0}=-10,\,y_{0}=12$. Les autres solutions sont de la forme
$x=-10+14k$, $y=12+17k$, o\`u $k$ d\'ecrit $\Z$.

\ques{2.}{\sl Soit $a$ un
entier tel que $2a\equiv 2~(197)$, et $b$ un entier tel que
$3b\equiv 3~(201)$. \par Peut-on affirmer que $a\equiv 1~(197)$ ? }
OUI. D'apr\`es le th\'eor\`eme de
B\'ezout, comme 197 et 3 sont premiers entre eux, il existe des entiers
$u$ et $v$ tels que $197u+3v=1$. Alors $3v\equiv 1~(197)$,
donc $a\equiv 3va\equiv 3v~\equiv 1~(197)$.

\vskip .2cm

{\sl Que $b\equiv 1~(201)$ ?} NON. Par exemple, $b=68$ satisfait
$3b\equiv 3~(201)$ mais n'est pas congru \`a 1 modulo 201.


\ques{3.}{\sl On note $a_n$ le nombre \`a $n$ chiffres tous
\'egaux \`a $1$. Que vaut $9a_n$ ? Montrer que si $n$ est
premier et $n>5$, alors $a_{n-1}$ est divisible par $n$.}
\par
$9a_{n}=10^{n}-1$. Si $n$ est premier et si $n$ ne divise pas 10,
d'apr\`es le th\'eor\`eme de Fermat, $10^{n-1}\equiv 1~(n)$,
donc $n$ divise $9a_{n-1}$. Si de plus $n\not=3$, $n$ est
premier avec 9, donc $n$ divise $a_{n-1}$, d'apr\`es le th\'eor\`eme de
Gauss. Comme les diviseurs de 10 sont 2 et 5, les seules exceptions
sont 2, 3 et 5, donc $n$ divise $a_{n-1}$ pour tout $n$ premier,
$n>5$.

\vskip .2cm
{\sl Montrer que $a_{12}$ est divisible par $21$.}
\par
D'apr\`es la d\'ecomposition en facteurs premiers, il suffit de montrer
que $a_{12}$ est divisible par les nombres premiers 3 et 7. Or la
somme des chiffres de $a_{12}$ vaut 12, divisible par 3, donc
$a_{12}$ est divisible par 3. D'apr\`es le th\'eor\`eme de Fermat,
$10^{6}\equiv 1~(7)$, donc  $10^{12}\equiv 1^2 \equiv 1~(7)$, donc 7
divise $9a_{12}$. Comme 7 est premier avec 9, 7 divise $a_{12}$,
d'apr\`es le th\'eor\`eme de Gauss. On conclut que $a_{12}$ est divisible
par 3 et par 7 donc par 21.

\ques{4.}{\sl La station Mir est rest\'ee en service pendant
473 050 800 secondes (fictif). Cela repr\'esente-t-il un
nombre entier d'heures ? On justifiera la r\'eponse, sans poser de
division, par des arguments de congruences.}
\par
OUI. En effet, la somme des chiffres de $n=$473 050 800 vaut 27, donc
$n$ est divisible par 9. Les deux derniers chiffres de $n/100$ sont
08, divisible par 4, donc $n/100$ est divisible par 4. Comme 4 et 9
sont premiers entre eux, on en d\'eduit que $36=4\times 9$ divise
$n/100$, donc $n$ est divisible par 3 600.


  %\end{document}
\bye

\ques{15.}Soient $a$ et $b$ deux nombres \`a 2 chiffres.
Posons la multiplication de $a$ par $b$. Combien
d'op\'erations \'el\'ementaires (\'ecriture d'un chiffre,
addition de deux chiffres compris entre 0 et 9, mise en
m\'emoire d'une retenue, multiplication de deux chiffres)
cela fait-il intervenir ?

On suppose que $a$ et $b$ ont
$n$ chiffres chacun, avec $n$ grand. Quel est l'ordre de
grandeur du nombre d'op\'erations n\'ecessaire pour les
multiplier ?