\documentclass[11pt, francais]{smfart}
\usepackage{amsfonts, amssymb, amsmath, latexsym}
\usepackage{mathptmx}
\usepackage[frenchb]{babel}

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{textcomp}

\pagestyle{empty}

\input xy
\xyoption{all}

\addtolength{\hoffset}{-25mm}
%\addtolength{\voffset}{-10mm}
\addtolength{\topmargin}{-40mm} \addtolength{\headsep}{5mm}
\addtolength{\textwidth}{50mm} \addtolength{\textheight}{65mm}

\newcommand{\A}{\mathrm{A}}
\newcommand{\E}{\mathrm{E}}
\newcommand{\K}{\mathrm{K}}
\newcommand{\rP}{\mathrm{P}}
\newcommand{\T}{\mathrm{T}}
\newcommand{\B}{\mathrm{B}}
\newcommand{\M}{\mathrm{M}}
\newcommand{\V}{\mathrm{V}}
\newcommand{\F}{\mathrm{F}}
\newcommand{\N}{\mathrm{N}}
\newcommand{\Q}{\mathrm{Q}}
\newcommand{\U}{\mathrm{U}}
\newcommand{\Ir}{\mathrm{I}}
\newcommand{\Sr}{\mathrm{S}}
\newcommand{\C}{\mathrm{C}}
\newcommand{\X}{\mathrm{X}}
\newcommand{\D}{\mathrm{D}}
\newcommand{\Lr}{\mathrm{L}}

\thispagestyle{empty}

\begin{document}
\noindent \textbf{Alg\`ebre et Th\'eorie des nombres - Printemps 2008} \hfill \textbf{Universit\'e Claude Bernard Lyon 1}
\vspace{0.3cm}
\hrule

\vspace{0.7cm}

\begin{center} {\bfseries \scshape 1. Arithm\'etique \'el\'ementaire} \end{center}

\vspace{0.4cm}

\noindent \textbf{Exercice 1.} Calculer le pgcd de $341$ et $672$ puis \'ecrire une relation de B\'ezout explicite pour ces deux nombres.

\vspace{0.4cm}
\noindent \textbf{Exercice 2.} D\'eterminer tous les couples d'entiers naturels dont le pgcd est $56$ et dont le ppcm est $672$.

\vspace{0.4cm}
\noindent \textbf{Exercice 3.} Soient $a$, $b$ et $c$ trois nombres entiers relatifs ; on suppose que $a$ et $b$ sont non nuls et on pose $d = \mathrm{pgcd}(a,b)$.

\indent 1. D\'eterminer toutes les solutions enti\`eres de l'\'equation homog\`ene $ax+by=0$.

\indent 2. D\'emontrer que l'\'equation inhomog\`ene $ax+by = c$ admet une solution enti\`ere si et seulement si $d | c$.

\indent 3. D\'eterminer toutes les solutions enti\`eres de l'\'equation inhomog\`ene $ax+by=c$ lorsque $d|c$.

\vspace{0.4cm} \noindent \textbf{Exercice 4.} R\'esoudre les \'equations suivantes dans $\mathbb{Z}$ :
\begin{center} a)  $2x+3y = 4$ \qquad b) $341x-672y = 62$ \qquad c) $15x+51y = 41$

d) $10x-8y = 42$ \qquad e) $17x+19y = 23$
\end{center}

\vspace{0.4cm} \noindent \textbf{Exercice 5.} Exhiber trois nombres entiers $p$, $a$, $b$ tels que $p | ab$ mais $p\nmid a$ et $p \nmid b$. \'Etant donn\'e un nombre entier non nul $p$, \`a quelle condition l'assertion $$\forall a, \ b \in \mathbb{Z}, \ (p|ab \Longrightarrow p|a \ \textrm{ ou } \ p|b)$$ est-elle vraie?

\vspace{0.4cm} \noindent \textbf{Exercice 6.} Exhiber trois nombres entiers $p$, $q$, $a$ tels que $p| a$ et $q|a$ mais $pq \nmid a$. \'Etant donn\'es des nombres entiers non nuls $p, q$, \`a quelle condition l'assertion $$\forall a \in \mathbb{Z}, \ (p|a \ \mathrm{et} \ q|a \Longrightarrow pq|a)$$ est-elle vraie?

\vspace{0.4cm} \noindent \textbf{Exercice 7.} Un g\'en\'eral chinois livre bataille \`a la t\^ete de deux mille hommes. \`A l'issue du combat, il demande aux rescap\'es de se grouper par 11 et note que cinq soldats restent isol\'es ; il leur demande ensuite de se grouper par 13 et note que trois soldats restent isol\'es ; il leur demande enfin de se grouper par 15 et note alors que 11 soldats restent isol\'es. Quelle perte doit-il annoncer \`a l'empereur?

\vspace{0.4cm} \noindent \textbf{Exercice 8.} R\'esoudre dans $\mathbb{Z}$ les syst\`emes suivants :
$$\left\{\begin{array}{ll} x \equiv 3 & (\mathrm{mod}\ 6) \\ x \equiv 2 & (\mathrm{mod}\  5) \\ x \equiv 6 & (\mathrm{mod}\ 7) \end{array} \right.$$

\vspace{0.4cm} \noindent \textbf{Exercice 9.} R\'esoudre dans $\mathbb{Z}$ les syst\`emes suivants : $$a) \left\{\begin{array}{ll} 3x \equiv 2 & (\mathrm{mod}\ 5) \\ 5x \equiv 4 & (\mathrm{mod} \ 9) \end{array} \right. \qquad b) \left\{\begin{array}{ll} 3x \equiv 1 & (\mathrm{mod} \ 5) \\ 4x \equiv 6 & (\mathrm{mod} \ 14) \\ 5x \equiv 11 & (\mathrm{mod} \ 3) \end{array} \right. $$

\vspace{0.4cm} \noindent \textbf{Exercice 10.} R\'esoudre dans $\mathbb{Z}$ les syst\`emes suivants :
$$a) \left\{\begin{array}{ll} x \equiv 2 & (\mathrm{mod} \ 4) \\ x \equiv 3 & (\mathrm{mod} \ 6) \end{array} \right. \qquad \left\{\begin{array}{ll} 5x \equiv 1 & (\mathrm{mod} \ 12) \\ 4x \equiv 2 & (\mathrm{mod}\ 15) \end{array} \right. $$

\vspace{0.4cm} \noindent \textbf{Exercice 11.} (\emph{Divisibilit\'e par $9$}) 1. Prouver que $10^k \equiv 1 \ (\mathrm{mod} \ 9)$ pour tout $k \in \mathbb{N}$.\\
\indent 2. Prouver que $571356$ est un multiple de $9$. \\
\indent 3. Donner une condition n\'ecessaire et suffisante pour qu'un nombre entier soit divisible par $9$.

\vspace{0.4cm} \noindent \textbf{Exercice 12.} (\emph{Une infinit\'e de nombres premiers, 1}) Soit $\mathcal{E}= \{p_1, \ldots, p_n\}$ un ensemble fini de nombres premiers. D\'emontrer que le nombre $p_1 p_2 \ldots p_n +1$ n'est divisible par aucun des nombres $p_1, \ldots, p_n$ et en d\'eduire qu'il existe une infinit\'e de nombres premiers.

\vspace{0.4cm} \noindent \textbf{Exercice 13.} (\emph{Une infinit\'e de nombres premiers de la forme $4m+3$}) 1. V\'erifier que le produit de deux nombres entiers de la forme $4m+1$ est encore de cette forme. \\
\indent 2. En adaptant le raisonnement de l'exercice pr\'ec\'edent, d\'emontrer qu'il existe une infinit\'e de nombres premiers de la forme $4m+3$ (\emph{Indication : consid\'erer $2^2p_1 p_2 \ldots p_n - 1$}).

\vspace{0.4cm} \noindent \textbf{Exercice 14.} (\emph{Une infinit\'e de nombres premiers, 2}) \'Etant donn\'e un entier $n \geq 1$, le $n$-\`eme \emph{nombre de Fermat} est d\'efini par $F_n = 2^{2^n}+1$.

Quels que soient les entiers $n, k >0$, d\'emontrer que $F_n$ divise $F_{n+k}-2$. En d\'eduire que $F_n$ et $F_{n+k}$ sont premiers entre eux, puis qu'il existe une infinit\'e de nombres premiers.

\vspace{0.4cm} \noindent \textbf{Exercice 15.} (\emph{Une infinit\'e de nombres premiers, 3}) Soit $\mathcal{P}$ l'ensemble des nombres premiers.

En utilisant l'identit\'e $\frac{1}{1 - p^{-1}} = \sum_{m \geq 0} p^{-m}$, d\'emontrer que l'on a $$\sum_{n =1}^{N} \frac{1}{n} \leq \prod_{p \in \mathcal{P}, \ p \leq N} \frac{1}{1 - p^{-1}}$$ pour tout entier naturel $N \geq 2$. En d\'eduire que l'ensemble $\mathcal{P}$ est infini.

\vspace{0.4cm} \noindent \textbf{Exercice 16.} (\emph{Une infinit\'e de nombres premiers, 4}) Soit $\mathcal{P}_h = \{p_1, \ldots, p_h\}$ l'ensemble des $h$ premiers nombres premiers. On note $\mathcal{N}_h$ l'ensemble des entiers naturels dont tous les facteurs premiers appartiennent \`a $\mathcal{P}_h$ et, pour tout nombre r\'eel positif $x$, on note $N_h(x)$ le nombre d'\'el\'ements de $\mathcal{N}_h$ major\'es par $x$.

1. Montrer que tout \'el\'ement $n \in \mathcal{N}_h$ s'\'ecrit d'une mani\`ere et d'une seule sous la forme $n = n_1^2 p_1^{\varepsilon_1} \ldots p_h^{\varepsilon_h}$ avec $n_1 \in \mathcal{N}_h$ et $\varepsilon_1, \ldots, \varepsilon_h \in \{0,1\}$.

2. Si $n \leq x$, v\'erifier que l'on a $n_1 \leq \sqrt{x}$ et en d\'eduire la majoration $N_h(x) \leq 2^h \sqrt{x}$.

3. D\'eduire de ce qui pr\'ec\`ede qu'il existe une infinit\'e de nombres premiers.

4. \'Etant donn\'e un nombre r\'eel $x \geq 1$, on note $\pi(x)$ le cardinal de l'ensemble des nombres premiers major\'es par $x$. En utilisant ce qui pr\'ec\`ede, d\'emontrer que l'on a $$\pi(x) \geq \frac{\log(x)}{2\log(2)}.$$ Cette minoration est-elle de bonne qualit\'e?

5. D\'emontrer que le $n$-\`eme nombre premier $p_n$ est major\'e par $4^n$.

\vspace{0.4cm} \noindent \textbf{Exercice 17.} (\emph{\'Equation de Pythagore}) Le but de cet exercice est de d\'eterminer l'ensemble $\mathcal{E}$ de tous les triplets d'entiers naturels $(x,y,z)$ tels que $$x^2 + y^2 = z^2.$$


0. D\'eterminer tous les triplets $(x,y,z) \in \mathcal{E}$ dans lesquels une coordonn\'ee au moins s'annule.

\emph{\`A partir de maintenant, on ne consid\`ere que des triplets $(x,y,z)$ avec $x, y, z \geq 1$.}
 
\indent 1. Montrer que tout \'el\'ement $(x,y,z)$ de $\mathcal{E}$ est de la forme $(dx', dy', dz')$, o\`u $d \in \mathbb{N}$ et $(x',y',z')$ est un \'el\'ement de $\mathcal{E}$ tel que $x'$, $y'$ et $z'$ soient des entiers naturels premiers entre eux dans leur ensemble. \\
\indent 2. Prouver que les entiers $x'$, $y'$ et $z'$ sont en fait premiers entre eux deux \`a deux. 

\emph{\`A partir de maintenant, on consid\`ere un \'el\'ement $(x,y,z)$ de $\mathcal{E}$ telle que $x$, $y$ et $z$ soient des entiers naturels premiers entre eux deux \`a deux.}

\indent 3. D\'emontrer que l'un des deux nombres $x$ ou $y$ est pair (\emph{Indication : raisonner modulo $4$}). \\
\indent 4. Supposons que $x$ soit pair. D\'emontrer que les entiers $z+y$ et $z-y$ sont pairs, puis que $$\frac{z+y}{2} \ \ \ \textrm{ et } \ \ \  \frac{z-y}{2}$$ sont des carr\'es.\\
\indent 5. D\'eduire de ce qui pr\'ec\`ede que $\mathcal{E}$ est l'ensemble de tous les triplets $(x,y,z)$ qui, \`a permutation pr\`es de $x$ et $y$, sont de la forme $$x = 2dab, \ \ y = d(a^2 - b^2), \ \ z = d(a^2 + b^2),$$ o\`u $d \in \mathbb{N}$ et $a$, $b$ sont deux entiers premiers entre eux, de parit\'e diff\'erente et tels que $a>b>0$. \\
\indent 6. Dresser la liste de tous les triplets $(x,y,z) \in \mathcal{E}$ tels que $\max\{x, y, z\} \leq 30.$

\end{document} 