% Feuille de TD 7 Algebre et Arithmetique, Licence 3, 2007-2008

\documentclass{amsart}[14pt]

%Package

\usepackage[french]{babel}
\usepackage[all]{xy}
\usepackage{latexsym}
\usepackage{eufrak}
\usepackage{amssymb}
\usepackage{a4wide}
%\usepackage{fancyhdr}


\input{Macros.tex}
\def\spec{\textrm{Spec}\,  A}
\def\spe{\textrm{Spec}\, }

%  Parameters

\setlength{\parindent}{0pt}
\linespread{1.3}
%\addtolength{\headsep}{0.5cm}


%  Newtheorem
\theoremstyle{definition}
\newtheorem{ex}{\bf Exercice}
\newtheorem*{thm}{Th\'eor\`eme}
\newtheorem{prob}{\bf Probl\`eme}

% Newenvironment

%\newenvironment{proo}{\begin{trivlist} \item{\sc {Proof.}}}
%  {\hfill $\square$ \end{trivlist}}

%  Newcommand



\pagestyle{plain}

\title{$\boxed{\textsc{FEUILLE DE TRAVAUX DIRIG\'ES 7}}$}
\author{\bf Arithm\'etique des entiers}



\begin{document}


{\sc Alg\`ebre et Arithm\'etique} \hfill {\sc Math\'ematiques L3}

{Universit\'e de Nice Sophia-Antipolis} \hfill {Ann\'ee 2007-2008}\\

\vskip10pt

\maketitle



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{ex}$\ $

D\'eterminer les triplets $(a,\, b,\, c)\in (\NN^*)^3$ tels que
$$\textrm{ppcm}(a,\, b)=42 \quad, \quad \textrm{pgcd}(a,\, c)=3 \quad \textrm{et} \quad a+b+c=29.$$
\end{ex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{ex}[Algorithme d'Euclide et Th\'eor\`eme de B\'ezout]$\ $

\begin{enumerate}
\item Quel est le pgcd de $47$ et $111$ ?
\item D\'eterminer deux entiers $u$ et $v$ v\'erifiant $47u+111v=1$.
\end{enumerate}
\end{ex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{ex}[Congruences]$\ $

\begin{enumerate}
\item Montrer que pour tout entier naturel $n$, $5$ divise $2^{3n+5}+3^{n+1}$.

\item Montrer que pour tout entier $n$, $30$ divise $n^5-n$.

\item Quel est le reste de la division euclidienne de $16^{(2^{1000})}$ par $7$ ?


\end{enumerate}

\end{ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{ex}[Nombres de Mersenne, nombres de Fermat]$\ $


\begin{enumerate}
\item Soient $a\ge 2$ et $n\ge 2$ deux entiers. Si $a^n-1$ est un nombre premier, montrer que $a=2$ et que $n$ est premier. Les nombres premiers de cette forme sont appel\'es \emph{nombres de Mersenne}.

\item Soit $n\in \NN^*$. Si $2^n+1$ est premier, montrer que $n$ est une puissance de $2$. Les nombres de la forme $F_k=2^{2^k}+1$ sont appel\'es \emph{nombres de Fermat}.

\item Montrer que les nombres de Fermat $\lbrace F_k \rbrace_{k\in \NN}$ sont premiers entre eux deux \`a deux.

\item En d\'eduire une autre d\'emonstration du fait qu'il y a une infinit\'e de nombres premiers.

\end{enumerate}

\end{ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{ex}[]$\ $

Soit $A$ la somme des chiffres de $4444^{4444}$, \'ecrit dans le syst\`eme d\'ecimal, et soit $B$ la somme des chiffres de $A$. Que vaut $C$, la somme des chiffres de $B$ ?

\end{ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{ex}[Cas particuliers du th\'eor\`eme de la progression arithm\'etique de Dirichlet]$\ $

\begin{enumerate}
\item Montrer qu'il existe une infinit\'e de nombres premiers de la forme $6n-1$, $n\in \NN^*$.

\item Soit $p>5$ un nombre premier. Montrer que $5$ est un carr\'e dans $\ZZ/p\ZZ$ si et seulement si $p \equiv \pm 1 {}_{[10]}$


\noindent
\underline{Indication} : Utiliser la loi de r\'eciprocit\'e quadratique.

\item En d\'eduire qu'il existe une infinit\'e de nombres premiers de la forme $10n-1$, $n\in \NN^*$.

\end{enumerate}
\end{ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{prob}[Nombres pseudo-premiers et nombres de Carmichael]$\ $

Le th\'eor\`eme de Fermat affirme que si $n$ est premier et si $a\wedge n=1$, alors $a^{n-1}\equiv 1 {}_{[n]}$.
Le but de ce probl\`eme est de montrer que la r\'eciproque est fausse. \\


Soit un entier $a\ge 2$. Un entier $n$ est dit \emph{pseudo-premier} en base $a$ si $n$ n'est pas premier et si $a^{n-1}\equiv 1 {}_{[n]}$.


\begin{enumerate}
\item Si $p>2$ est un nombre premier ne divisant pas $a(a^2-1)$, montrer que $n=(a^{2p}-1)/(a^2-1)$ est un nombre pseudo-premier en base $a$.
\item  En d\'eduire que pour tout entier $a\ge 2$, il existe un infinit\'e de nombres pseudo-premiers en base $a$.\\

\noindent
Un entier $n\ge 2$ est appel\'e \emph{nombre de Carmichael} si $n$ n'est pas premier et si pour tout entier $a$ premier avec $n$, $a^{n-1}\equiv 1 {}_{[n]}$.

\item Si $n=p_1 p_2 \ldots p_k$, o\`u les $p_i$ sont des nombres premiers distincts, et si $p_i-1|n-1$ pour tout $i$, montrer que $n$ est un nombre de Carmichael.


\item R\'eciproquement, montrer que tout nombre de Carmichael peut se mettre soous la forme $n=p_1 p_2 \ldots p_k$ o\`u les $p_i$ sont des nombres premiers distincts et o\`u $p_i-1|n-1$ pour tout $i$

\noindent
\underline{Indication} : on pourra utiliser le fait que pour  un groupe commutatif fini $G$, si $p$ premier divise le cardinal de $G$, alors il existe dans $G$ au moins un \'el\'ement d'ordre $p$.

\item Montrer qu'un nombre de Carmichael a au moins $3$ facteurs premiers.

\item Soit $n=pqr$ un nombre de Carmichael \`a trois facteurs premiers $p<q<r$. Si $p$ est fix\'e, montrer que $q$ et $r$ sont born\'es.
\end{enumerate}

\end{prob}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\vfill

\end{document}
