\documentstyle[12pt]{article}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\textwidth}{15cm}
\setlength{\headheight}{0cm}
\setlength{\topmargin}{0cm} 
\setlength{\headsep}{0cm}
\setlength{\textheight}{23cm}
\setlength{\parindent}{1cm}



\def\aujourdhui{\number\day\space\ifcase\month\or
  Janvier\or F\'evrier\or Mars\or Avril\or Mai\or Juin\or
  Juillet\or Ao\^ut\or Septembre\or Octobre\or Novembre\or D\'ecembre\fi
, \number\year}



%sublist
\newcounter{point}
\newenvironment{sublist}{
\begin{list}{\alph{point})}{\usecounter{point}
\setlength{\itemsep}{0cm}\setlength{\leftmargin}{1.2em}}
}{\end{list}}
                                                                


%liste d'exercices
\newcounter{exo}
\newenvironment{list-of-exercises}{
\begin{list}{\arabic{exo})}{\usecounter{exo}            
\setlength{\itemsep}{0cm}}                                      
}{\end{list}}                                                   
                                                                
\newcommand{\plus}{\oplus}
\newcommand{\pgcd}{\mbox{PGCD}\,}


% abbreviations
% Black Board Bold Face
\newcommand{\N}{{\mbox{\bf N}}}
\newcommand{\sN}{{\mbox{\bf \scriptsize N}}}
\newcommand{\Z}{{\mbox{\bf Z}}}
\newcommand{\sZ}{{\mbox{\bf \scriptsize Z}}}
\newcommand{\R}{{\mbox{\bf R}}}
%Comma, forall
\newcommand{\ko}{\: , \;}
\newcommand{\fa}{\forall \,}
%Overline, Underline
\newcommand{\ol}{\overline}
\newcommand{\ul}{\underline}



%Calligraphic letters
\newcommand{\ca}{{\cal A}}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\cg}{{\cal G}}
\newcommand{\ch}{{\cal H}}
\newcommand{\ci}{{\cal I}}
\newcommand{\ck}{{\cal K}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cn}{{\cal N}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cq}{{\cal Q}}
\newcommand{\cs}{{\cal S}}
\newcommand{\ct}{{\cal T}}
\newcommand{\cu}{{\cal U}}
\newcommand{\cv}{{\cal V}}
\newcommand{\cw}{{\cal W}}
\newcommand{\cx}{{\cal X}}



%Arrows
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\arr}[1]{\stackrel{#1}{\rightarrow}}
\newcommand{\longarr}[1]{\stackrel{#1}{\longrightarrow}}
\newcommand{\longlarr}[1]{\stackrel{#1}{\longleftarrow}}
\newcommand{\iso}{\stackrel{_\sim}{\rightarrow}}
\newcommand{\liso}{\stackrel{_\sim}{\leftarrow}}
\newcommand{\larr}[1]{\stackrel{#1}{\leftarrow}}
\newcommand{\da}{\downarrow}
\newcommand{\ua}{\uparrow}
\newcommand{\pl}{\parallel}



\begin{document}
\begin{center}
MT 282 	        \hfill Universit\'e Paris 7 \\
19/10/95	\hfill  U.F.R. de Math\'ematiques\\
\mbox{ }	\hfill P.~Perrin/B.~Keller\\[0.5cm]
{\large\bf Exercices d'arithm\'etique \'el\'ementaire}
\end{center}

\begin{list-of-exercises}

{\bf\begin{flushleft} 
Exercices sur les anneaux $\Z/n\Z$
\end{flushleft}}

\item 
R\'esoudre dans $\Z/5\Z$  le syst\`eme suivant
\[
\begin{array}{rcl}
x+2\, y & = & 3 \\
2\,x + 3\,y & = & 4
\end{array}
\]

\item
R\'esoudre dans  $\Z/5\Z$  le syst\`eme suivant
o\`u  $a$  est un param\`etre.
\[
\begin{array}{rcl}
x + 2\, y & = & a \\
2\, x - y & = & 1
\end{array}
\]

\item
R\'esoudre dans  $\Z/6\Z$  le syst\`eme suivant
(on discutera suivant les valeurs de  $a$  et  $b$ ).
\[
\begin{array}{rcl}
5\,x + 2\,y & = & a \\
2\,x + 4\,y & = & b 
\end{array}
\]
{\bf\begin{flushleft}
Exercices sur la notion de divisibilit\'e. 
\end{flushleft}}

\item
Trouver la plus
grande puissance de  $2$  divisant  $1000!$ (il est raisonnable de 
trouver  $994$).
G\'en\'eraliser \`a un autre nombre premier comme  $3$  par exemple. Puis
g\'en\'eraliser \`a  $n!$ . Trouver le nombre de z\'eros figurant \`a la fin de
l'\'ecriture d\'ecimale de  $1000!$ .

\item Trouver le nombre de solutions (en entiers naturels) de  
$n = x + 2\,y$,  o\`u  $n$  est un param\`etre et  $x, y$  les inconnues.

\item Montrer que le nombre suivant
\[
u_n= 1 + \frac{1}{2} + \ldots + \frac{1}{n}
\]
ne peut \^etre entier. On pourra montrer par r\'ecurrence (en 
utilisant deux formules de r\'ecurrence diff\'erentes suivant que
$n$  est pair ou impair) qu'il s'\'ecrit
\[
u_n = \frac{2\,p_n + 1}{2\, q_n}.
\]


\item
Montrer que le nombre suivant
\[
u_1 = 1 + \frac{1}{2} + \ldots + \frac{1}{p-1}
\]
(o\`u  $p$  est un nombre premier) s'\'ecrit
\[
u_p = \frac{A_p}{B_p}\ko
\]
o\`u  $A_p$  et  $B_p$  sont premiers entre eux et  $A_p$  est 
divisible par  $p$. (On peut montrer en fait que $A_p$  est divisible par  
$p^2$ ; on le fera dans une prochaine feuille d'exercices).

\item Soit  $n$  un entier naturel non nul. Soit  $p$  un diviseur
premier de  $n$  et soit  $a$  l'exposant de la plus grande puissance de  $p$ 
divisant  $n$ .  Soit  $b$  un entier naturel inf\'erieur ou \'egal \`a  $a$ .
Montrer que  $a - b$  est l'exposant de la plus grande puissance de  p  divisant
le coefficient binomial
\[
C^{p^b}_n.
\]




{\bf
\begin{flushleft}
Exercices n\'ecessitant la division euclidienne ou la structure de corps sur
les  $F_p$
\end{flushleft}}


\item
Onze personnes d\'ecident de se r\'eunir
r\'eguli\`erement \`a d\^{\i}ner autour d'une table ronde (ou ovale!). Chaque
personne fait, \`a cette occasion, la connaissance de ses deux voisins.
Trouver (au moins) une strat\'egie pour qu'au bout de cinq repas chacun ait
fait la connaissance des dix autres personnes.

\item R\'esoudre l'\'equation $x^2 - 4\,x - 2 = 0$ dans  $\Z/5\Z$.
M\^eme question pour les deux \'equations suivantes: $x^2 - 2\,x + 2=0$  
et  $x^2 -4\,x-3=0$.

\item Soient  $a$  et  $b$  deux nombres premiers entre eux. Montrer
que le PGCD des deux nombres  $a + b$  et  $a - b$  est n\'ecessairement un
diviseur de  $2$ . Pr\'eciser quand cela peut \^etre  $2$ .


\item Soit  $a$  un entier relatif. Montrer que le PGCD de  $a$  et 
$a + k$ (o\`u  $k$  est un entier sup\'erieur ou \'egal \`a  $1$ ) divise  $k$.

{\bf 
\begin{flushleft}
Exercices sur la rationalit\'e
\end{flushleft}}

\item Montrer que
\[
\sqrt[n]{m}
\]
est un rationnel si et seulement si  $m$  est une puissance  
$n$-i\`eme dans  $\Z$.


\item Montrer que $\log_{10}(2)$  est irrationnel.

\item Montrer que  
\[
\sqrt{2}+\sqrt{3}
\]
est solution de l'\'equation  $x^4 - 10 x^2 + 1=0$. 
Chercher toutes les racines rationnelles de cette \'equation. 
Qu'en concluez vous pour $\sqrt{2}+\sqrt{3}$ ?

\item V\'erifier que le nombre 
\[
\sqrt[3]{20+14\sqrt{2}} + \sqrt[3]{20-14\sqrt{2}}
\]
est rationnel.

\item Montrer que l'\'equation  $3 \,x^2 + 2 = y^2$  n'a pas de
solutions dans l'anneau  $\Z$. M\^eme question pour 
l'\'equation  $7\, x^2 + 2 = y^3$.

\item Nous allons r\'esoudre compl\`etement l'\'equation 
$x^2 + y^2 = z^2$  o\`u  $x$, $y$  et  $z$  sont des entiers relatifs.
\begin{sublist}

\item Si  $(x,y,z)$  est un triplet solution, montrer qu'il s'\'ecrit 
$(dx',dy',dz')$  o\`u  $d$  est \'el\'ement de  $\Z$  
et  $x'$, $y'$  et  $z'$  sont premiers deux \`a deux.

\item Supposons que le triplet  $(x,y,z)$  soit solution et soit form\'e
d'entiers premiers deux \`a deux. Montrer que  $x$  et  $y$  n'ont pas la m\^eme
parit\'e.

\item Sous les hypoth\`eses pr\'ec\'edentes (cf. b) prenons  $x$  pair. Montrer
que l'on peut \'ecrire  $y = u - v$  et  $z = u + v$  o\`u  $u$  et  $v$  sont des
entiers premiers entre eux.

\item Sous les hypoth\`eses de c)  montrer que  $u$  et  $v$  sont les carr\'es de
deux entiers premiers entre eux.

\item Conclure. (Cette \'equation est un des cas triviaux de l'\'equation de
Fermat. Nous essaierons de r\'esoudre \'egalement le cas de l'exposant $3$ et
celui de l'exposant $4$).
\end{sublist}

\item Montrer que la congruence  $x^2 \equiv 1 \;(2^b)$  a une
solution si  $b$  est \'egal \`a  $1$ , deux solutions si  $b$  est \'egal \`a  $2$ 
et quatre solutions si  $b$  est sup\'erieur ou \'egal \`a  $3$.


\item Montrer que  $30$  divise  $n^5 - n$  quel que soit  $n\in\N$. 
Montrer de m\^eme que  $42$  divise  $n^7 - n$  quel que soit  $n$.


{\bf\begin{flushleft}
Exercices sur l'identit\'e de Bezout et le calcul des inverses dans  $F_p$
\end{flushleft}}

\item Les nombres  $1017$  et  $269$  sont-ils premiers entre eux?
Donner une identit\'e de Bezout entre ces deux nombres. 
Trouver toutes les identit\'es de Bezout entre ces deux nombres.
L'\'el\'ement  $269$  a-t-il un inverse dans  $\Z/1017\Z$ ?

\item R\'esoudre le syst\`eme de congruences suivant
\[
\begin{array}{rcl}
x & \equiv & 1\;\; (7) \\
x & \equiv & 4\;\; (9) \\
x & \equiv & 5\;\; (5) 
\end{array}
\]
(on pourra tout d'abord chercher une identit\'e de Bezout entre  $5$  et  $63$, 
$7$ et  $45$  puis enfin  $9$  et  $35$).

\item R\'esoudre les \'equations  $398\, u + 600\, v = 2$, 
$1841\, u + 3647 \,v = 1$  o\`u  $u$  et  $v$  sont des variables enti\`eres.

\item R\'esoudre l'\'equation  $323 x + 391 y + 437 z = 10473 $
o\`u  $x$, $y$  et  $z$  sont des variables enti\`eres.

\item Soient deux entiers  $n$  et  $m$ . Montrer que le produit  $mn$ 
est \'egal au produit de leur PGCD et de leur  PPCM.


{\bf \begin{flushleft}
Exercices sur les nombres premiers.
\end{flushleft}}


\item Montrer que, si  $a^n -1$  est un nombre premier, alors  $a$ 
est pair et \'egal \`a  $2$  et que  $n$  est premier (on pourra utiliser
l'\'egalit\'e remarquable donnant  $x^n - y^n$ ). De tels nombres s'appellent
nombres de Mersenne. C'est une question sans r\'eponse \`a ce jour de savoir
s'ils sont en nombre infini.

\item Montrer que, si  $a^n +1$  est un nombre premier, alors  a 
est pair et que  $n$  est une puissance de  $2$ (on pourra utiliser l'\'egalit\'e
remarquable donnant  $x^n + y^n$  lorsque  $n$  est impair). Donner un exemple de
nombre premier de cette forme pour lequel  $a$  est diff\'erent de  $2$. De tels
nombres s'appellent nombres de Fermat lorsque  $a$  est \'egal \`a  $2$ . C'est
une question sans r\'eponse \`a ce jour de savoir si ceux d'entre eux qui sont
premiers, sont en nombre infini.

\item Montrer que, si un entier  $n$  n'est divisible par aucun
facteur premier  $p$  inf\'erieur \`a sa racine cubique, il est premier ou
produit de deux facteurs premiers.

\item Soient  $p$  et  $q$  deux entiers premiers impairs
cons\'ecutifs. Montrer que  $p + q$  admet une d\'ecomposition en au moins trois
facteurs premiers (non n\'ecessairement distincts).

\item Nous allons montrer que l'\'equation  $x^4 + y^4 = z^4$  n'admet
pas de solutions enti\`eres  $(x,y,z)$  non triviales (i.e. avec  $xyz \neq 0$).
En fait nous allons montrer le m\^eme r\'esultat pour l'\'equation  
$x^4 + y^4 =z^2$. Raisonnons par l'absurde. Soit  $u$  le plus petit entier pour lequel il
existe des entiers  $x$  et  $y$  non nuls tels que $x^4 + y^4 = u^2$.
\begin{sublist}
\item Montrer que  $x$  et  $y$  sont premiers entre eux, que  $u$  est impair et
que, entre  $x$  et  $y$ , l'un est impair et l'autre pair.

\item Supposons d\'esormais  $x$  pair et  $y$  impair. Utiliser un exercice
pr\'ec\'edent pour \'ecrire  $x^2 = 2ab$, $y^2 = a^2 - b^2$ et  $u = a^2 + b^2$ 
(o\`u  $a$  et  $b$  sont premiers entre eux). Montrer que  $b$  est n\'ecessairement 
pair et  $a$ impair (on pourra raisonner modulo $4$).

\item On pose donc  $x = 2x'$  et  $b = 2d$ . Montrer que  $a = a'^2$  et  $d = d'^2$ 
et que  $a'$  et  $d'$  restent premiers entre eux.

\item Appliquer \`a nouveau le m\^eme exercice pr\'ec\'edent \`a l'identit\'e obtenue pour 
$y^2$  soit $(2d'^2)^2 + y2 = (a'^2)^2$. En d\'eduire une identit\'e  $a^4 + b^4 = a'^2$ 
o\`u  $a'$  est inf\'erieur strictement \`a  $u$.
\end{sublist}



\end{list-of-exercises}
\end{document}




