\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\big=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}
\vskip 0.8truecm
\centerline{\smc Feuille d'exercices n$^0$1}
\vskip.4truecm

\ques{1.}Montrer par r\'ecurrence sur $n$ que si $a$ est
un entier impair, alors $a^{2^{n}}-1$ est divisible par
$2^{n+1}$.
%Recurrence

\ques{2.}Montrer que pour tout entier naturel $n$,
$3^{3n+3}-26 n -27$ est divisible par 169.
%Recurrence

\ques{3.}Faire la liste de tous les diviseurs de 30.

\ques{4.}Calculer le PGCD de 10 000 001 et de 99 999, puis
le PGCD de -555 et de 66 066.
%Euclide

\ques{5.}Quel jour de la semaine sera le 4 f\'evrier 2005 ?
%Euclide

\ques{6.}Soit $k$ un entier. Montrer que $2k+1$ et $9k+4$
sont premiers entre eux. Quel est le PGCD de $2k-1$ et
$9k+4$ ?
%Euclide

\ques{7.}Vir\'ee \`a Carrefour avec les copains. On a
d\'epens\'e en tout 188 euros, en achetant des CD \`a 25
euros et des jeans \`a 21 euros. Combien de CD a-t-on
achet\'e ?
%Bezout

\ques{8.}Pierre et Paul f\^etent ensemble leur
anniversaire. Ils invitent des copains au cin\'ema puis au
resto. Certains copains n'ont pas pu rester pour le resto.
Pierre a pay\'e le cin\'ema (place \`a 7 euros) et Paul le
resto (repas \`a 9 euros). Pour partager \'equitablement
la d\'epense, Pierre a revers\'e 3 euros \`a Paul. Combien
y avait-il de copains au cin\'ema ? au resto ?
%Bezout

\ques{9.}``Paul :
--Je vais chercher un sandwich \`a la Kfet.
\par\noindent Pierre : --Prends-moi un pain au chocolat.''

De retour, Paul, qui tient \`a \^etre rembours\'e
exactement (pas d'arrondi), r\'eclame 1 euro \`a Pierre.
Celui-ci paie en francs et Paul lui rend la monnaie en
euros. Combien de francs Paul a t'il d\^u payer ? M\^eme
question si les deux comparses n'utilisent que des billets.
%Gauss

\ques{10.}Soient $a$ et $b$ deux entiers non nuls. Soit $d$
le PGCD de $a$ et de $b$. Montrer que $a/d$ et $b$ sont
premiers entre eux. En d\'eduire que $PPCM(a,b)=ab/d$.
Quel est le PPCM de 10 000 001 et de 99 999 ?
%Gauss

\ques{11.}Soit $n>0$ un entier. On se demande s'il est
possible d'\'ecrire $1/n$ comme une combinaison d'inverses
d'entiers strictement inf\'erieurs \`a $a$. Par exemple,
$1/6=1/2 - 1/3$ ou bien $1/6=1/3 + 1/3 -1/2$.

Montrer que si $n$ est une puissance d'un nombre premier, ce n'est 
pas possible.

Montrer que si $n=ab$ est le produit de deux entiers $>1$ premiers 
entre eux, c'est possible. Le faire pour $n=26.17$.
%Bezout

\ques{12.}On rappelle que la partie fractionnaire d'un
r\'eel $x$ est ${\rm frac}(x)=x-E(x)$. Soit $r$ un
rationnel non nul. D\'eterminer l'ensemble des valeurs que
prend la partie fractionnaire de $kx$ lorsque $k$ d\'ecrit
${\bf Z}$. Soit $r=125/256$. Trouver tous les entiers $k$
tels que ${\rm frac}(kr)=1/256$.
%Bezout

\ques{13.}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=-{8\over{15}}x+{1\over{15}}$.
%Bezout

\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}
\vskip 0.8truecm
\centerline{\smc Feuille d'exercices n$^0$2}
\vskip.4truecm


\ques{1.}Combien de chiffres comporte l'\'ecriture
d\'ecimale de $2^{32}$ ? Combien de chiffres comporte
l'\'ecriture en base 2 de $10^{10}$ ? On donne
$\log_{10}(2)=0.30102...$. Par combien de z\'eros cette \'ecriture se 
termine-t-elle ?
%Decomposition en facteurs premiers

\ques{2.}Etant donn\'e un entier $a>1$, on note
$E(a)$ l'ensemble des entiers compris entre $0$ et
$a-1$ qui sont premiers avec $a$, et $\phi(a)$ le nombre
d'\'el\'ements de $E(a)$.

Calculer $\phi(a)$ pour $a=$4, 5, 6, 9, 12, 15, 36.

Montrer que si $p$ est un nombre premier et $a=p^s$ est une puissance 
de $p$, alors $\phi(a)=p^{s-1}(p-1)$.

Soit $q$ un nombre premier distinct de $p$ et $b=q^t$ une puissance 
de $q$. En comptant les entiers non premiers avec $ab$, montrer que
$\phi(ab)=\phi(a)\phi(b)$.
%Decomposition en facteurs premiers

\ques{3.}Le tour du monde de Magellan a dur\'e 19 464
heures (fictif). Cela repr\'esente-t'il un nombre entier de
jours ?
%Congruences

\ques{4.}D\'eterminer tous les entiers $a$ tels que 10
divise $a^{10}+1$.
%Congruences

\ques{5.}Soient $a$ et $b$ deux entiers tels que $a^2 +
b^2$ soit divisible par 7. Montrer que $a$ et $b$ sont
divisibles par 7.
%Congruences

\ques{6.}D\'eterminer tous les entiers $n$ tels que $4 n^2
+1$ soit divisible par 5 et $n^2 -3$ par 13.
%Congruences/Bezout

\ques{7.}Triangles rectangles \`a c\^ot\'es entiers.
Soient $x$, $y$ et $z$ trois entiers n'ayant pas de
diviseur commun. On suppose que $x^2 + y^2 = z^2$.

Montrer que $z$ et $x$ sont premiers entre eux et que $z$ et $y$ sont 
premiers entre eux.

Montrer que $z$ est impair et que l'un de $x$ et de $y$ est pair.

Supposant $y$ pair, montrer que $(z-x)/2$ et $(z+x)/2$ sont des carr\'es.

R\'eciproquement, v\'erifier que si $m$ et $n$ sont des entiers, 
alors $x=m^2 -n^2$, $y=2mn$ et $z=m^2 +n^2$ satisfont $x^2 + y^2 = 
z^2$.
%Congruences

\ques{8.}Montrer que $2^{70}+3^{70}$ est divisible par 13.
%Fermat

\ques{9.}Montrer que pour tout entier naturel $n$,
$2^{2^{6n+2}}+3$ est divisible par 19.
%Fermat

\ques{10.}Montrer que $20^{15}-1$ est divisible par 20801.
%Fermat

\ques{11.}Montrer qu'il existe dans la suite $u_{n}=2^n
-3$ une infinit\'e de termes divisibles par 5 et une
infinit\'e de termes divisibles par 13, mais qu'aucun n'est
divisible par 65.
%Fermat

\ques{12.}Soit $p=2k+1$ un nombre premier impair. Soit $a$
un entier non divisible par $p$. Montrer que $a^{k}\equiv
1$ ou $a^{k}\equiv -1$ modulo $p$. Application
num\'erique : faire le tableau des restes des puissances
huiti\`emes modulo 17.
%Fermat

\ques{13.}En utilisant la formule du bin\^ome, montrer que
pour tout entier $a>0$, $(a+1)^a -1$ est divisible par
$a^2$.
%Binome

\ques{14.}En utilisant l'exercice pr\'ec\'edent, montrer que si
$n$ est un entier naturel et $m=2^{n} -1$, alors
$2^{mn}-1$ est divisible par $m^2$.
%Congruences

\ques{15.}Soit $k\in N$. Calculer la somme des
puissances $k$-\`emes des $n$ premiers entiers.
%Binome

\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 {\big A}
  \vskip 0.8truecm
\centerline{\smc Test}
\centerline{Lundi 25 mars 2002, dur\'ee 1h}
\centerline{{\sl Les documents et calculettes sont
interdits}}
\vskip.4truecm

\ques{1.}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)$ ?

\vskip 1.5cm

Que $b\equiv 1~(202)$ ?

\vskip 1.5cm

Justifier par une d\'emonstration ou un contre-exemple.

\ques{2.}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. \vskip 2cm


\ques{3.}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.
\vskip 2cm

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}$.
\vskip 2cm

\ques{4.}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}}$. \vskip 2cm

\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 {\big B}
  \vskip 0.8truecm
\centerline{\smc Test}
\centerline{Lundi 25 mars 2002, dur\'ee 1h}
\centerline{{\sl Les documents et calculettes sont
interdits}}
\vskip.4truecm

\ques{1.}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\vskip 3cm

\ques{2.}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)$ ?
\par\vskip 1.5cm
Que $b\equiv 1~(201)$ ?
\par\vskip 1.5cm
Justifier par une d\'emonstration ou un contre-exemple.

\ques{3.}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\vskip 2cm
Montrer que $a_{12}$ est divisible par $21$.
\par\vskip 1.5cm

\ques{4.}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.
\vskip 2cm


\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 {\big 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$.


\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 {\big 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 ?