\documentclass[12pt]{book}\usepackage{ammaths}\begin{document}

\exercices{3}{Nombres premiers entre eux\\ Théorèmes de Bézout et
Gauss}{Terminale S}


\exoc{Donner quelques exemples de nombres premiers entre eux, en
démontrant cette propriété par l'algorithme d'Euclide.}

\exoc{On dit que $b$ est un inverse de $a$ modulo $n$ si
$ab\equiv 1[n]$.
\begin{enumerate}
\item Prouver que 2 n'a pas d'inverse modulo 6.
\item Déterminer les entiers $n$ tels que 2 ait un inverse modulo
$n$.
\end{enumerate}}

\exoc{Les théorèmes de Bezout et Gauss sont notamment utilisés pour
la résolution des équations \emph{diophantiennes}. Nous allons voir
dans cet exercice un exemple de la méthode utilisée pour ce type
d'équations.
\begin{enumerate}
\item \begin{enumerate}
    \item Utiliser l'algorithme d'Euclide pour déterminer $d$, le PGCD de 24 et 17.
    \item L'équation $24x+17y=1$ admet-elle des solutions dans $\Z$ ?
    \item Utiliser les différentes étapes de l'algorithme d'Euclide de la question 1.a.
    pour exprimer chacun des restes successifs en tant que combinaison linéaire de 24 et 17.
    \item Déduire de la question précédente deux entiers $u_0$ et $v_0$ tels que $24u_0+17v_0=1$.
    Le couple $(u_0,v_0)$ est appelé \emph{solution particulière} de l'équation $$24x+17y=1.$$
    \end{enumerate}
\item Soit $(u,v)$ une autre couple solution de l'équation $24x+17y=1.$
    \begin{enumerate}
    \item Prouver que $24(u_0-u)=17(v-v_0).$
    \item Utiliser le théorème de Gauss pour prouver qu'il existe un entier $k$
    tel que $v=v_0+24k$.
    \item Utiliser les questions précédentes pour prouver que $u=u_0-17k$.
    \item Vérifier que tous les couples $(u_0-17k,v_0+24k)$, où $k$ est un entier, sont solutions
    de l'équation $24x+17y=1.$
    \end{enumerate}
\end{enumerate}
}

\exoc{On se propose de déterminer les entiers relatifs $x$ vérifiant le système de congruence :
$$\left\lbrace  \begin{array}{cc}
                 x\equiv3 & \textrm{ mod } 11\\
                 x\equiv4 & \textrm{ mod } 15
                \end{array}\right .$$
\begin{enumerate}
 \item Montrer que la résolution de ce système se ramène a résoudre dans $\Z\times\Z$ l'équation $11u+15v=1$.
 \item Résoudre cette équation et en déduire les solutions du système.
\end{enumerate}
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exoc{Soit $\N^*$ l'ensemble des entiers naturels non nuls. On
considère, lorsque $n$ appartient à $\N^*$, les deux entiers $a$ et
$b$ définis par $a=11n+3$ et $b=13n-1$.\par
\begin{enumerate}
\item Démontrer que tout diviseur commun de $a$ et $b$ est un diviseur de 50.
\item Résoudre, pour $x$ appartenant à $\N^*$ et $y$ appartenant à
$\N^*$, l'équation $50x-11y=3$. En déduire les valeurs de $n$ pour
lesquelles les nombres $a$ et $b$ ont 50 pour PGCD.
\item Pour quelles valeurs de $n$ les nombres $a$ et $b$ ont-ils 25 pour PGCD
?
\end{enumerate}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exoc{{\sl Amérique du Nord 4 juin 2009}\\
 Soit $A$  l'ensemble des entiers naturels de l'intervalle $[1~;~46]$. 
\begin{enumerate}
\item  On considère l'équation \[(E) : \quad  23x + 47y = 1\] où $x$ et $y$ sont des entiers relatifs.
	\begin{enumerate}
	\item Donner une solution particulière $\left(x_{0},~y_{0}\right)$ de $(E)$. 
	\item Déterminer l'ensemble des couples $(x,~y)$ solutions de $(E)$. 
	\item En déduire qu'il existe un unique entier $x$ appartenant à $A$ tel que $23x \equiv  1\quad  (47)$.
	\end{enumerate} 
\item  Soient $a$ et $b$ deux entiers relatifs. 
	\begin{enumerate}
	\item Montrer que si $ab \equiv 0 \quad  (47)$ alors $a \equiv 0 \quad  (47)$) ou $b \equiv 0 \quad  (47)$. 
	\item En déduire que si $a^2 \equiv  1 \quad  (47)$ alors $a \equiv  1 \quad  (47)$ ou a $a \equiv -1 \quad  (47)$.
	\end{enumerate} 
\item 	\begin{enumerate}
	\item  Montrer que pour tout entier $p$ de $A$, il existe un entier relatif $q$ tel que $p \times  q \equiv 1 \quad (47)$.\\
	Pour la suite, on admet que pour tout entier $p$ de $A$, il existe un unique entier, noté \emph{inv}$(p)$, appartenant à $A$ tel que $p \times inv(p) \equiv  1 \quad  (47)$. \\
	Par exemple : \\
	\emph{inv}$(1) = 1$ car $1 \times 1 \equiv 1 \quad  (47),~$ \emph{inv}$(2) = 24$ car $2 \times 24 \equiv  1 \quad  (47),$
	\emph{inv}$(3) = 16$ car $3 \times 16 \equiv  1 \quad  (47)$. 
	\item Quels sont les entiers $p$ de $A$ qui vérifient $p =$ \emph{inv}$(p)$ ?
	\item Montrer que $46 ! \equiv -1 \quad (47)$. 
	\end{enumerate}
\end{enumerate}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exoc{{\sl Asie, juin 2009}
\begin{enumerate}
\item On se propose, dans cette question, de déterminer tous les entiers relatifs $N$ tels que \[\left\{\begin{array}{l c l r}
N&\equiv&5&(13)\\
N&\equiv &1&(17)
\end{array}\right.\]

	\begin{enumerate}
		\item Vérifier que 239 est solution de ce système.
		\item Soit $N$ un entier relatif solution de ce système.
		
		Démontrer que $N$ peut s'écrire sous la forme $N = 1 + 17x = 5 + 13y$ où $x$ et $y$ sont deux entiers relatifs vérifiant la relation $17x - 13y = 4$.
		\item Résoudre l'équation $17x - 13y = 4$ où $x$ et $y$ sont des entiers relatifs.
		\item En déduire qu'il existe un entier relatif  $k$ tel que $N = 18 + 221k$.
		\item Démontrer l'équivalence entre $N \equiv 18 \quad (221)$ et $\left\{\begin{array}{l c l r}
N&\equiv&5&(13)\\
N&\equiv &1&(17)
\end{array}\right.$.

	\end{enumerate}
\item \emph{Dans cette question, toute trace de recherche, même incomplète, ou d'initiative, même infruxtueuse, sera prise en compte dans l'évaluation.}

\medskip

	\begin{enumerate}
		\item Existe-t-il un entier naturel $k$ tel que $10^k \equiv 1 \quad (17)$ ?
		\item Existe-t-il un entier naturel $l$ tel que $10^l \equiv 18 \quad (221)$ ?
	\end{enumerate}

\end{enumerate}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exoc{{\sl Liban, juin 2009}\\
Le but de l'exercice est de montrer qu'il existe un entier naturel $n$ dont l'écriture décimale du cube se termine par 2009, c'est-à-dire tel que $n^3 \equiv  2009 \mod \nombre{10000}$.
 
\probpart{}
 
\begin{enumerate}
\item Déterminer le reste de la division euclidienne de $\nombre{2009}^2$ par $16$. 
\item En déduire que $\nombre{2009}^{\nombre{8001}} \equiv  \nombre{2009} \;\mod 16$. 
\end{enumerate}


 \probpart{}
On considère la suite $\left(u_{n}\right)$ définie sur $\N$ par :

$u_{0} = \nombre{2009}^2 - 1$ et, pour tout entier naturel $n,~ u_{n+1} = \left(u_{n} + 1\right)^5 -1$. 
\begin{enumerate}
\item 
	\begin{enumerate}
		\item  Démontrer que $u_{0}$ est divisible par 5. 
	\item Démontrer, en utilisant la formule du binôme de Newton, que pour tout entier naturel $n,$
	\[ u_{n+1} = u_{n}\left[{u_{n}}^4 + 5\left({u_{n}}^3 + 2{u_{n}}^2 +2u_{n} + 1\right)\right].\] 
	\item Démontrer par récurrence que, pour tout entier naturel $n,~u_{n}$ est divisible par $5^{n+1}$.
	\end{enumerate} 
\item
	\begin{enumerate}
	\item Vérifier que $u_{3} = \nombre{2009}^{250} -1$ puis en déduire que $\nombre{2009}^{250} \equiv  1 \mod 625$.
	\item Démontrer alors que $\nombre{2009}^{\nombre{8001}} \equiv  \nombre{2009} \mod 625$.
	\end{enumerate}  
\end{enumerate}

\probpart{}

\begin{enumerate}
\item En utilisant le théorème de Gauss et les résultats établis dans les questions précédentes, montrer que $\nombre{2009}^{\nombre{8001}} - \nombre{2009}$ est divisible par \nombre{10000}. 
\item  Conclure, c'est-à-dire déterminer un entier naturel dont l'écriture décimale du cube se termine par \nombre{2009}. 
\end{enumerate}
}



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

\exoc{{\sl Asie, juin 2008}

Soit $a$ et $b$ deux entiers naturels non nuls ; on appelle \emph{réseau} associé aux entiers $a$ et $b$ l'ensemble des points du plan, muni d'un repère orthogonal, dont les coordonnées $(x;y)$ sont des entiers vérifiant les conditions : $0 \leqslant x\leqslant a$ et $0 \leqslant y \leqslant b$. On note $R_{a,b}$ ce réseau.\\
Le but de l'exercice est de relier certaines propriétés arithmétiques des entiers $x$ et $y$ à des propriétés géométriques des points correspondants du réseau.

\probpart{-- Représentation graphique de quelques ensembles}

Dans cette question, les réponses sont attendues sans explication, sous la forme d'un graphique qui sera dûment complété sur la feuille annexe 1 à rendre avec la copie.\\
Représenter graphiquement les points $M(x;y)$ du réseau $R_{8,8}$ vérifiant :
\begin{enumerate}
\item $x \equiv 2\quad (\text{modulo}~ 3)$ et $ y \equiv 1 \quad (\text{modulo}~ 3)$, sur le graphique 1 de la feuille annexe
\item $x+y \equiv 1$\quad (modulo 3), sur le graphique 2 de la feuille annexe ;
\item $x \equiv y$ \quad (modulo 3), sur le graphique 3 de la feuille annexe.
\end{enumerate} 

\probpart{-- Résolution d'une équation}

On considère l'équation (E) : $7x-4y=1$, où les inconnues $x$ et $y$ sont des entiers relatifs.
\begin{enumerate}
\item Déterminer un couple d'entiers relatifs $\left(x_{0};y_{0}\right)$ solution de l'équation (E).
\item Déterminer l'ensemble des couples d'entiers relatifs solutions de l'équation (E).
\item Démontrer que l'équation (E) admet une unique solution $(x;y)$ pour laquelle le point $M(x;y)$ correspondant appartient au réseau $R_{4,7}$.
\end{enumerate}

\probpart{-- Une propriété des points situés sur la diagonale du réseau.}

Si $a$ et $b$ sont deux entiers naturels non nuls, on considère la diagonale $[OA]$ du réseau $R_{a,b}$, avec
$O(0;0)$ et $A(a;b)$.

\begin{enumerate}
\item Démontrer que les points du segment $[OA]$ sont caractérisés par les conditions :
\[0 \leqslant x \leqslant a ~;~0 \leqslant y \leqslant b~;~ay=bx.\]
\item Démonter que si $a$ et $b$ sont premiers entre eux, alors les points O et $A$ sont les seuls points du segment $[OA]$ appartenant au réseau $R_{a,b}$.
\item Démontrer que si $a$ et $b$ ne sont pas premiers entre eux, alors le segment $[OA]$ contient au moins un autre point du réseau.\\ (On pourra considérer le pgcd $d$ des nombres $a$ et $b$ et poser $a=da'$ et $b=db'$.)
\end{enumerate}
}


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


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

\exoc{{\sl Antilles-Guyane, septembre 2003}

Soit l'équation (1) d'inconnue rationnelle $x$ :
\[ 78x^3 + ux^2 + vx - 14 = 0.\]
où $u$ et $v$ sont des entiers relatifs.
\begin{enumerate} \item On suppose dans cette question que $\cfrac{14}{39}$ est solution de
l'équation (1).
    \begin{enumerate} \item Prouver que les entiers relatifs $u$ et $v$ sont liés par la relation
    $14x + 39y =1129.$
    \item Utiliser l'algorithme d'Euclide, en détaillant les diverses
    étapes du calcul, pour trouver un couple $(x ~;~ y)$ d'entiers
    relatifs vérifiant l'équation $14x + 39y = 1$.
    \item En déduire un couple $\left(u_{0}~ ; ~v_{0}\right)$ solution
    particulière de l'équation $14u + 39v =1129$.\\ Donner la solution
    générale de cette équation c'est-à-dire l'ensemble des couples
    $(u~;~ v)$ d'entiers relatifs qui la vérifient.
    \item Déterminer, parmi les couples $(u~;~ v)$ précédents, celui pour
    lequel le nombre $u$ est l'entier naturel le plus petit possible.
    \end{enumerate}
\item
    \begin{enumerate} \item Décomposer 78 et 14 en facteurs
    premiers.\\ En déduire, dans $\N$, l'ensemble des diviseurs de 78 et
    l'ensemble des diviseurs de 14.
    \item Soit $\frac{p}{q}$ une solution rationnelle de l'équation
    (1) d'inconnue $x$ :$$78x^3 + ux^2 + vx - 14 = 0$$ où $u$ et $v$
    sont des entiers relatifs.\\ Montrer que si $p$ et $q$ sont des
    entiers relatifs premiers entre eux, alors $p$ divise 14 et $q$
    divise 78.
    \item En déduire le nombre de rationnels, non entiers, pouvant
    être solutions de l'équation (1) et écrire, parmi ces rationnels,
    l'ensemble de ceux qui sont positifs.
    \end{enumerate}
\end{enumerate}
}

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

\exoc{{\sl Polynésie, juin 2006}

Pour chacune des cinq propositions suivantes, indiquer si elle est
vraie ou fausse et donner une démonstration de la réponse choisie.
Une réponse non démontrée ne rapporte aucun point.
\begin{enumerate}
\item <<~pour tout entier naturel $n$,
$3$ divise le nombre $2^{2n}-1$.~>>
\item <<~Si un entier relatif $x$ est solution de
l'équation $x^2+x \equiv 0\quad  (\text{modulo}~ 6)$ alors $x \equiv
0 \quad  (\text{modulo}~ 3)$.~>>
\item <<~l'ensemble des couples d'entiers relatifs $(x~;~ y)$
solutions de l'équation $12x - 5y = 3$ est l'ensemble des couples
$(4+10k~ ;~ 9+24k)$ où $k \in \Z$.~>>
\item <<~il existe un seul couple $(a~;~ b)$ de nombres entiers naturels,
tel que $a < b$ et PPCM$(a,~ b) - \text{PGCD}(a,~b) = 1$.~>>
\end{enumerate}
Deux entiers naturels $M$ et $N$ sont tels que $M$ a pour écriture
$abc$ en base dix et $N$ a pour écriture $bca$ en base dix.
\begin{enumerate}\setcounter{enumi}{4}
\item <<~Si l'entier $M$ est divisible par 27 alors l'entier $M -N$ est aussi divisible par 27.~>>
\end{enumerate}}




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

% 
% \exoc{{\sl La Réunion, juin 2005}
% 
% Dans cet exercice, on pourra utiliser le résultat suivant :
% 
% <<~Étant donnés deux entiers naturels $a$ et $b$ non nuls, si
% $PGCD(a~;~ b) =  1$ alors $PGCD(a^2~;~ b^2) = 1$~>>.
% 
% Une suite $\left(S_{n}\right)$ est définie pour $n
% > 0$ par $S_{n}=\displaystyle\sum_{p=1}^n p^3$. On se propose de
% calculer, pour tout entier naturel non nul $n$, le plus grand commun
% diviseur de $S_{n}$ et $S_{n+1}$.
% 
% \begin{enumerate}
% \item Démontrer que, pour tout $n > 0$, on a : $S_{n}  = \left(\cfrac{n(n+1)}{2}\right)^2$.
% \item Étude du cas où $n$ est pair. Soit $k$ l'entier naturel non nul tel que $n = 2k$.
%     \begin{enumerate}\item Démontrer que $PGCD(S_{2k};S_{2k+1})=(2k+1)^2PGCD\left(k^2~;~(k+1)^2\right)$.
%     \item Calculer $PGCD (k;k + 1)$.
%     \item Calculer $PGCD\left(S_{2k};S_{2k+1}\right)$.
%     \end{enumerate}
% \item Étude du cas où $n$ est impair. Soit $k$ l'entier naturel non nul tel que $n = 2k+ 1.$
% \begin{enumerate}\item Démontrer que les entiers $2k + 1$ et $2k +3$ sont premiers entre eux.
% \item Calculer $PGCD\left(S_{2k+1}~;~ S_{2k+2}\right)$.
% \end{enumerate}
% \item Déduire des questions précédentes qu'il existe une unique valeur de $n$,
% que l'on déterminera, pour laquelle $S_{n}$ et $S_{n+1}$ sont
% premiers entre eux.
% \end{enumerate}}
% 
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\exoc{{\sl Antilles-Guyane, juin 2003}
\begin{enumerate}\item
    \begin{enumerate}\item  Calculer : $\left(1 + \sqrt{6}\right)^2,~
    \left(1 + \sqrt{6}\right)^4,~\left(1 + \sqrt{6}\right)^6$.
    \item Appliquer l'algorithme d'Euclide à 847 et 342. Que peut-on
    en déduire  ?
    \end{enumerate}
\item Soit $n$ un entier naturel non nul. On note $a$ et $b$ les
entiers naturels tels que :
\[\left(1 + \sqrt{6}\right)^n  = a_n + b_n\sqrt{6}.\]
Que valent $a_1$ et $b_1$ ?\\
D'après les calculs de la question {\bf\textsf{1.a.}}, donner
d'autres valeurs de $a_n$ et $b_n$.
    \begin{enumerate}\item Calculer $a_{n+1}$ et $b_{n+1}$ en fonction de $a_n$ et $b_n$.
    \item  Démontrer que, si 5 ne divise pas $a_n + b_n$, alors 5 ne
    divise pas non plus $a_{n+1} + b_{n+1}$.\\
    En déduire que, quel que soit $n$ entier naturel non nul, 5 ne
    divise pas $a_n + b_n$.
    \item Démontrer que, si $a_n$ et $b_n$ sont premiers entre eux,
    alors $a_{n+1}$ et $b_{n+1}$ sont premiers entre eux.\\ En déduire
    que, quel que soit $n$ entier naturel non nul, $a_n$ et $b_n$ sont
    premiers entre eux.
    \end{enumerate}
\end{enumerate}}

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



\exoc{{\sl Liban, mai 2003}

Les suites d'entiers naturels $(x_n)$ et $(y_n)$ sont définies sur
$\N$ par :
\[ \begin{array}{l}
x_0 = 3 \quad \text{et} \quad x_{n+1} = 2x_n - 1\\
y_0 = 1 \quad \text{et} \quad y_{n+1} = 2y_n + 3.
\end{array}\]
\begin{enumerate} \item Démontrer par recurrence que pour tout entier naturel
$n,~ x_n = 2^{n+1} + 1$.
\item
    \begin{enumerate} \item Calculer le pgcd de $x_8$ et $x_9$,
    puis celui de $x_{2002}$ et $x_{2003}$. Que peut-on en déduire pour
    $x_8$ et $x_9$ d'une part, pour $x_{2002}$ et $x_{2003}$ d'autre
    part ?
    \item $x_n$ et $x_{n+1}$ sont-ils premiers entre eux pour tout
    entier naturel $n$ ?
    \end{enumerate}
\item
    \begin{enumerate} \item Démontrer que pour tout entier
    naturel $n,~ 2x_n - y_n = 5$.
    \item Exprimer $y_n$ en fonction de $n$.
    \item En utilisant les congruences modulo 5, étudier suivant les
    valeurs de l'entier naturel $p$ le reste de la division euclidienne
    de $2^p$ par 5.
    \item On note $d_n$ le pgcd de $x_n$ et $y_n$ pour tout entier
    naturel $n$.\\ Démontrer que l'on a $d_n = 1$ ou $d_n = 5$ ; en
    déduire l'ensemble des entiers naturels $n$ tels que $x_n$ et $y_n$
    soient premiers entre eux.
    \end{enumerate}
\end{enumerate}
}

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




\exoc{{\sl Nouvelle Calédonie, novembre 2002}

On considère deux entiers naturels, non nuls, $x$ et $y$ premiers
entre eux.\\ On pose $S = x + y$ et $P =xy$.
\begin{enumerate}\item
    \begin{enumerate}\item Démontrer que $x$ et $S$ sont premiers entre eux, de même que
    $y$ et $S$.
    \item En déduire que $S = x+y$ et $P =xy$ sont premiers entre eux.
    \item Démontrer que les nombres $S$ et $P$ sont de parités
    différentes (l'un pair, l'autre impair).
    \end{enumerate}
\item Déterminer les diviseurs positifs de 84 et les ranger par
ordre croissant.
\item Trouver les nombres premiers entre eux $x$ et $y$ tels que :
$SP = 84$.
\item Déterminer les deux entiers naturels $a$ et $b$ vérifiant
les conditions suivantes :
\[ \left\{ \begin{array}{l c l}
a + b &=& 84\\
ab& =& d^3 \\
\end{array}\right. ~\text{avec}~ d = \text{pgcd}(a ; b)\]
(On pourra poser $a = dx$ et $b = dy$ avec $x$ et $y$ premiers entre
eux)
\end{enumerate}
}

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

\exoc{{\sl Polynésie, juin 2002}

$n$ est un entier naturel supérieur ou égal à 2.
\begin{enumerate} \item Montrer que $n$ et $2n + 1$ sont premiers entre
eux.
\item On pose $\alpha = n + 3$ et $\beta = 2n + 1$ et on note
$\delta$ le PGCD de $\alpha$ et $\beta$.
    \begin{enumerate} \item Calculer $2\alpha - \beta$ et en déduire les valeurs
    possibles de $\delta$.
    \item Démontrer que $\alpha$ et $\beta$ sont multiples de 5 si et
    seulement si $(n - 2)$ est multiple de 5.
    \end{enumerate}
\item On considère les nombres $a$ et $b$ définis par :
\[ \begin{array}{l c l}
a & = & n^3 + 2n^2 - 3n\\
b & = & 2n^2 - n - 1\\
\end{array}\]
Montrer, après factorisation, que $a$ et $b$ sont des entiers
naturels divisibles par $(n - 1)$.
\item
    \begin{enumerate} \item On note $d$ le PGCD de $n(n + 3)$ et
    de $(2n + 1)$. Montrer que $\delta$ divise $d$, puis que $\delta =
    d$.
    \item En déduire le PGCD, $\Delta$, de $a$ et $b$ en fonction de
    $n$.
    \item Application :\\Déterminer $\Delta$ pour $n = 2001$ ;\\ Déterminer $\Delta$ pour $n
    = 2002$.
    \end{enumerate}
\end{enumerate}}

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



\exoc{{\sl Polynésie, septembre 2003}

On désigne par $p$ un nombre entier premier supérieur ou égal à 7.\\
Le but de l'exercice est de démontrer que l'entier naturel $n = p^4
- 1$ est divisible par 240, puis d'appliquer ce résultat.
\begin{enumerate}
\item Montrer que $p$ est congru à $- 1$ ou à $1$ modulo 3.\\
En déduire que $n$ est divisible par 3.
\item En remarquant que $p$ est impair, prouver qu'il existe un
entier naturel $k$ tel que $p^2 - 1 = 4k(k + 1)$, puis que $n$ est
divisible par $16$.
\item En considérant tous les restes possibles de la division
euclidienne de $p$ par 5, démontrer que $5$ divise $n$.
\item
    \begin{enumerate} \item Soient $a,~ b$ et $c$ trois entiers
    naturels. Démontrer que si $a$ divise $c$ et $b$ divise $c$, avec
    $a$ et $b$ premiers entre eux, alors $ab$ divise $c$.
    \item Déduire de ce qui précède que $240$ divise $n$.
    \end{enumerate}
\item Existe-t-il quinze nombres premiers $p_1,~p_2, ...,~ p_{15}$
supérieurs ou égaux à 7 tels que l'entier $A =  p_1^4 + p_2^4 +... +
p_{15}^4$ soit un nombre premier ?
\end{enumerate}
}

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

\exoc{{\bf Devoir maison 3, exercice 1/2}

%{\sl France métropolitaine, juin 2004}
\begin{enumerate}
\item Montrer que, pour tout entier naturel non nul $k$ et pour tout entier
naturel $x$ :
\[(x-1)\left(1 +x + x^2 + \cdots + x^{k-1}\right) = x^k - 1.\]
Dans toute la suite de l'exercice, on considère un nombre entier $a$
supérieur ou égal à 2.
\item
    \begin{enumerate} \item Soit $n$ un entier naturel non nul
    et $d$ un diviseur positif de $n~ :~ n = dk$.\\ Montrer que $a^d- 1$
    est un diviseur de $a^n - 1$.
    \item Déduire de la question précédente que $2^{2004} - 1$ est
    divisible par 7, par 63 puis par 9.
    \end{enumerate}
\item Soient $m$ et $n$ deux entiers naturels non nuls et $d$ leur
pgcd.
    \begin{enumerate} \item On définit $m'$ et $n'$ par $m = dm'$ et $n = dn'$. En appliquant le théorème  de Bezout à $m'$ et $n'$, montrer qu'il existe des entiers relatifs $u$
    et $v$ tels que : $mu - nv = d$.
    \item On suppose $u$ et $v$ strictement positifs.\\
    Montrer que : $\left(a^{mu} - 1 \right) - \left(a^{nv} - 1 \right) a^d
    = a^d - 1$.\\ Montrer ensuite que $a^d - 1$ est le pgcd de $a^{mu} -
    1$ et de $a^{nv} - 1$.
    \item Calculer, en utilisant le résultat précédent, le pgcd de
    $2^{63} - 1$ et de $2^{60} - 1$.
    \end{enumerate}
\end{enumerate}
}

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


%  \exoc{{\bf Devoir maison 3, exercice 2/2} DM de 2009
% 
% %\exoc{{\sl France métropolitaine, juin 2002} 
% \begin{enumerate} \item On considère l'équation
% \[(E) ~:~ 6x + 7y = 57\]
%  où $x$ et $y$ sont des entiers relatifs.
%     \begin{enumerate} \item Déterminer un couple d'entiers relatifs $(u,~ v)$ tel que
%     $6u+7v=1$ ; en déduire une solution particulière $(x_{0},~ y_{0})$ de
%     l'équation $(E)$.
%     \item Déterminer les couples d'entiers relatifs solutions de
%     l'équation $(E)$.
%     \end{enumerate}
% \item Soit $\oijk$ un repère orthonormal de l'espace.\\
% On considère le plan (P) d'équation : $6x + 7y + 8z = 57$.\\
% On considère les points du plan P qui appartiennent aussi au plan
% $\oij$. Montrer  qu'un seul de ces points a pour coordonnées des
% entiers naturels ; déterminer
%  les coordonnées de ce point.
% \item On considère un point $M$ du plan P dont les coordonnées
% $x,~ y$ et $z$ sont des entiers naturels.
%     \begin{enumerate} \item Montrer que l'entier $y$ est impair.
%     \item On pose $y = 2p + 1$ où $p$ est un entier naturel.\\
%     Montrer que le reste dans la division euclidienne de $p + z$ par 3
%     est égal à 1.
%     \item On pose $p + z = 3q + 1$ où $q$ est un entier naturel.
%     Montrer que les entiers naturels $x,~ p$ et $q$ vérifient la
%     relation : $x + p + 4q = 7$. En déduire que $q$ prend les valeurs 0
%     ou 1.
%     \item En déduire les coordonnées de tous les points de (P) dont
%     les coordonnées sont des entiers naturels.
%     \end{enumerate}
% \end{enumerate}
% }
\newpage
\exoc{{\bf Devoir maison 3, exercice 2/2}% de 08-09

%{\sl France métropolitaine et La Réunion, septembre 2006}
\begin{enumerate}
\item On considère l'équation
\[(\mathcal{E})\quad: \quad  17x - 24y = 9,\]
où $(x,~ y)$ est un couple d'entiers relatifs.
    \begin{enumerate}
    \item Vérifier que le couple $(9;6)$ est solution de l'équation $(\mathcal{E})$.
    \item Résoudre l'équation $(\mathcal{E})$.
    \end{enumerate}
\item Dans une fête foraine, Jean s'installe dans un manège circulaire représenté par
le schéma donné en annexe. Il peut s'installer sur l'un des huit points indiqués sur le cercle.\\
Le manège comporte un jeu qui consiste à attraper un pompon qui, se
déplace sur un câble formant un carré dans lequel est inscrit le
cercle. Le manège tourne dans le sens des aiguilles d'une montre, à
vitesse constante. Il fait un tour en 24 secondes.
Le pompon se déplace dans le même sens à vitesse constante. Il fait un tour en 17 secondes.\\
Pour gagner, Jean doit attraper le pompon, et il ne peut le faire
qu'aux points de contact qui sont notés A, B, C et D sur le dessin.\\
A l'instant $t=0$, Jean part du point H en même temps que le pompon part du point A.\\
\begin{enumerate}
\item On suppose qu'à un certain instant $t$ Jean attrape le pompon en A.
Jean a déjà pu passer un certain nombre de fois en A sans y trouver
le pompon. A l'instant $t$, on note $y$ le nombre de tours effectués
depuis son premier passage en  A et $x$  le nombre de tours
effectués par le  pompon. Montrer que $(x,y)$ est solution de
l'équation $(\mathcal{E})$ de la question 1.
\item Jean a payé pour 2 minutes ; aura-t-il le temps d'attraper le pompon ?
\item Montrer, qu'en fait, il n'est possible d'attraper le pompon qu'au point A.
\item Jean part maintenant du  point E. Aura-t-il le temps d'attraper le pompon en A avant les deux minutes ?
\end{enumerate}
\end{enumerate}

\begin{center}
\psset{unit=0.7cm}
\begin{pspicture}(-5,-5)(5,5)
\psframe(-5,-5)(5,5) \psline(-5,-5)(5,5) \psline(-5,5)(5,-5)
\pscircle(0,0){5} \psline[linewidth=2.5pt]{->}(-4,5)(-3.8,5)
\psline[linewidth=2.5pt]{->}(4,5)(4.2,5)
\psarc[linewidth=2.5pt]{<-}(0,0){5}{205}{208} \uput[r](-3.5,3.5){E}
\uput[u](0,5){A}  \uput[l](3.5,3.5){F}  \uput[l](-5,0){D}
\uput[r](5,0){B}  \uput[r](-3.5,-3.5){H}  \uput[l](3.5,-3.5){G}
\uput[d](0,-5){C}
\end{pspicture}
\end{center}}


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

\end{document}
