% \end{Exo}
- \begin{Exo}
- Montrer que pour tout entier naturel $n$, 3 divise $4^n -1$.
- \end{Exo}
-
\begin{Exo}
Soit la suite $(U_n)_{n\in \N}$ définie par $U_n = 3^{2n+1} + 2^{n+2} $.
\begin{enumerate}
\end{enumerate}
\end{Exo}
- % \begin{Exo}
- % Soit $(u_n)_{n \in \N}$ une suite réelle telle que pour tout $ n \in \N$,
- % $$u_{n+2}-5u_{n+1}+6u_n = 0$$
- % Montrez qu'il existe $\alpha, \beta \in \N$ tels quel pour tout $ n \in \N, u_n = \alpha 3^n + \beta 2^n$.
- % \end{Exo}
- % \begin{Exo}
- % Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divisible par $m+n$.
- % \end{Exo}
+
+ \begin{Exo}
+ Montrer que pour tout entier naturel $n$, 3 divise $4^n -1$.
+ \end{Exo}
+
+ \begin{Exo}
+ Soit $(u_n)_{n \in \N}$ une suite réelle telle que pour tout $ n \in \N$,
+ $$u_{n+2}-5u_{n+1}+6u_n = 0$$
+ Montrez qu'il existe $\alpha, \beta \in \N$ tels quel pour tout $ n \in \N, u_n = \alpha 3^n + \beta 2^n$.
+ \end{Exo}
+
+ \begin{Exo}
+ Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divisible par $m+n$.
+ \end{Exo}
Ainsi, le plus petit nombre premier (et le seul qui soit pair) est 2.
\end{Exo}
- \begin{Th}
- Il existe une infinité de nombres premiers.
- \end{Th}
-
- \begin{Exo}[Nombres premiers en quantité infinie]
- Supposons comme hypothèse que l'ensemble des nombres premiers $\{ p_1, p_2, p_3 \ldots p_{n-1}, p_n \}$ est de cardinalité finie $n$.
- On construit le nombre $N = p_1. p_2. p_3. \ldots .p_{n-1}. p_n +1$.
- \begin{enumerate}
- \item Montrer que d'après l'hypothèse, il existe un nombre premier $q$ tel que
- $N$ est un multiple de $q$.
- \item Montrer cependant que $N$ n'est pas un multiple de $p_1$. Idem pour $p_2$, \ldots $p_n$.
- \item En déduire que $q$ est un nombre premier différent de $p_1$, de $p_2$, \ldots de $p_n$.
- \item En déduire une contradiction dans l'hypothèse.
- \end{enumerate}
- \end{Exo}
-
+
+
%\subsection{Décomposition en facteurs premiers}
\begin{Def}[Décomposition en facteurs premiers]
L'écriture d'un entier $n$ sous la forme $n=a^{\alpha}b^{\beta}c^{\gamma}\ldots$, où \begin{itemize}
\item $a$, $b$, $c$, \ldots sont des nombres premiers distincts
-deux à deux tels que $a < b < c < ldots$;
+deux à deux tels que $a < b < c <\ldots$;
\item les exposants $\alpha$, $\beta$, $\gamma$ sont des entiers naturels
non nuls;
\end{itemize}
\'Ecrivez les nombres 3850 et 1911 sous forme de produits de nombres premiers.
\end{Exo}
+
+
+
%\noindent Réponses : $2*5^2*7*11$ et $3*7^2*13$.
+ \begin{Th}
+ Il existe une infinité de nombres premiers.
+ \end{Th}
+
+ \begin{Exo}[Nombres premiers en quantité infinie]
+ Supposons comme hypothèse que l'ensemble des nombres premiers $\{ p_1, p_2, p_3 \ldots p_{n-1}, p_n \}$ est de cardinalité finie $n$.
+ On construit le nombre $N = p_1. p_2. p_3. \ldots .p_{n-1}. p_n +1$.
+ \begin{enumerate}
+ \item Montrer que d'après l'hypothèse, il existe un nombre premier $q$ tel que
+ $N$ est un multiple de $q$.
+ \item Montrer cependant que $N$ n'est pas un multiple de $p_1$. Idem pour $p_2$, \ldots $p_n$.
+ \item En déduire que $q$ est un nombre premier différent de $p_1$, de $p_2$, \ldots de $p_n$.
+ \item En déduire une contradiction dans l'hypothèse.
+ \end{enumerate}
+ \end{Exo}
+
%\subsection{Relation de divisibilité}
Pour $p \in \N$, on appelle nombres de Fermat les nombres de la forme
$F_p = 2^{2^p}+1$.
\begin{enumerate}
+ \item Question préliminaire: montrer que les deux égalités suivantes sont établies:
+ \begin{enumerate}
+ \item $x^n- 1 = (x-1)(x^{n-1}+x^{n-2}+\ldots+ x + 1)$ pour tout entier naturel $n$ strictement positif.
+ \item $x^n+ 1 = (x+1)(x^{n-1}-x^{n-2}+\ldots \pm x \mp 1)$ pour tout entier naturel $n$ impair
+ \end{enumerate}
+
\item Montrer que,
pour que $2^n+1$ soit premier, il est nécessaire
- que $n$ soit une puissance de 2.
+ que $n$ soit une puissance de 2.
\item Pour montrer que ce n'est pas suffisant, vérifier que $F_5$ est
divisible par 641.
\item En déduire que $F_p$ et $F_{p+k}$ sont premiers entre eux.
- %\item En déduire qu'il existe une infinité de nombres premiers.
+
\end{enumerate}
\end{Exo}
\end{Exo}
\begin{Exo}
- On considère l'équation $\frac{x}{0}-\frac{y}{4}=3$ où $x$ et $y$ sont des entiers naturels.
+ On considère l'équation $\frac{x}{9}-\frac{y}{4}=3$ où $x$ et $y$ sont des entiers naturels.
\begin{enumerate}
\item Montrer que cela implique qu'il existe $k \in \N$ tel que
$x= 9(k+ 3)$ et $y=4k$.
avoir d’hommes et de femmes dans le groupe?
\end{Exo}
-
-\section{Représentation des nombres entiers}
-
-
-
-\begin{Def}[Principe de la numération de position]
-\index{Principe de la numérotation de position}
-Il consiste à choisir une base $b$ de numération, et $b$ symboles qui constitueront les chiffres dans la représentation d'un entier positif en base $b$.
-Celle-ci s'écrira alors
-$$n=n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$$
-
-Cette écriture est abrégée en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.
-\end{Def}
-
-En informatique, on utilise couramment les bases 2, 8 et 16.
-
-
-
-
-
-L'algorithme pour obtenir la représentation en base $b$ d'un entier est :
-
-\begin{enumerate}
- \item Effectuer la division euclidienne de cet entier par $b$, division qui donne un premier quotient et un premier reste.
- \item Le quotient est à sont tour divisé par $b$ pour donner un second quotient et un second reste, et ainsi de suite jusqu'à obtenir un quotient nul.
-\item Les restes successifs (tous strictement inférieurs à $b$), et en commençant par le dernier, constituent la représentation en base $b$ de l'entier donné.
-\end{enumerate}
-
-\begin{Exo}
-Donner la représentation de 23 en base 2.
-\end{Exo}
-
-
-
-\begin{Exo}[Numération, changements de base]
-\begin{enumerate}
-\item Chercher les entiers dont le carré a, en représentation décimale,
-le même chiffre pour les dizaines et les unités.
-\item On pose $a=2p-1$, $b=2p+1$, $c=2p+3$; trouver l'entier $p$ de manière que $a^2+b^2+c^2$ soit de la forme $\sur{xxxx}_{10}$.
-\item L'entier $n$ s'écrit $\sur{341}_{10}$ et $\sur{2331}_a$. Trouver $a$.
-\item Montrer que, dans toute base $b$ supérieure ou égale à 3, l'entier qui s'écrit $\sur{11211}_b$ n'est pas premier.
-\item Soit $n\geqslant 7$. Donner l'écriture de $(n+1)^4$ en base $n$.
-\end{enumerate}
-\end{Exo}
-
-
-
-\begin{Exo}[Développement décimal]
-On considère le nombre réel $x$ dont le dé\-ve\-lop\-pe\-ment décimal s'écrit $x=0,012\ 345\ 679\ 012\ 345\ 679\ \ldots\ \ldots\ \ldots$ (la séquence $012\ 345\ 679$ est reproduite indéfiniment). Ce développement décimal est périodique, de période 9.
-\begin{enumerate}
-\item Montrer que $x$
-vérifie une équation de la forme $10^kx=n+x$, où $k$ et $n$ sont
-des entiers à déterminer. En résolvant cette équation,
-montrer que $x$ est un nombre rationnel, et le mettre sous la forme
-$x= \fr pq$ , où $p$ et $q$ sont premiers entre eux.
-\item Appliquer
-la même méthode au ``nombre" $y$ dont le développement
-décimal est $y= 0,999\ 999\ 999\ 999\ \ldots$ (périodique de période
-1). Quelle conclusion peut-on en tirer?
-\item Démontrer que tout nombre réel dont le développement
-décimal est fini ou périodique à partir d'un certain rang
-est un nombre rationnel.
-\item Réciproquement, on se propose de démontrer que le
-développement décimal de tout nombre rationnel est fini ou
-périodique à partir d'un certain rang. Pour cela, on
-considère un rationnel $x=\fr pq$ , avec $q>0$, $p\in
-\Z$, $p$ et $q$ premiers entre eux, et on étudiera successivement
-les cas suivants:
-\begin{itemize}
-\item $x$ est entier (c'est à dire $q=1$).
-\item $x$ est rationnel non entier, et $q$ est premier avec 10 (On
-pourra montrer que, si $q$ est premier avec 10, il existe un entier
-$k$, non nul, tel que $10^k\equiv 1\ [q]$).
-\item $x$ est rationnel non entier, mais $q$ n'est pas premier avec 10.
-\end{itemize}
-\end{enumerate}
-
-\end{Exo}
-
-
\section{Arithmétique modulo $n$}
On rappelle ici la définition de la relation dite de \og congruence modulo n\fg{} définie dans $\Z$ étudiée dans le chapitre consacré aux relations entre ensembles.
\begin{Exo}
-Un nombre \og pseudo-premier de base $b$ \fg{}\index{pseudo-premier} est un entier naturel non premier $p$ tel que $(b^p-b) mod p = 0$.
+Un nombre \og pseudo-premier de base $b$ \fg{}\index{pseudo-premier} est un entier naturel non premier $p$ tel que $(b^p-b) \mod p = 0$.
Vérifier que 561 est pseudo-premier de base 3 et que 341 est pseudo-premier de base 2.
\end{Exo}
+
+\section{Représentation des nombres entiers}
+
+
+
+\begin{Def}[Principe de la numération de position]
+\index{Principe de la numérotation de position}
+Il consiste à choisir une base $b$ de numération, et $b$ symboles qui constitueront les chiffres dans la représentation d'un entier positif en base $b$.
+Celle-ci s'écrira alors
+$$n=n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$$
+
+Cette écriture est abrégée en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.
+\end{Def}
+
+En informatique, on utilise couramment les bases 2, 8 et 16.
+
+
+
+
+
+L'algorithme pour obtenir la représentation en base $b$ d'un entier est :
+
+\begin{enumerate}
+ \item Effectuer la division euclidienne de cet entier par $b$, division qui donne un premier quotient et un premier reste.
+ \item Le quotient est à sont tour divisé par $b$ pour donner un second quotient et un second reste, et ainsi de suite jusqu'à obtenir un quotient nul.
+\item Les restes successifs (tous strictement inférieurs à $b$), et en commençant par le dernier, constituent la représentation en base $b$ de l'entier donné.
+\end{enumerate}
+
+\begin{Exo}
+Donner la représentation de 23 en base 2.
+\end{Exo}
+
+
+
+\begin{Exo}[Numération, changements de base]
+\begin{enumerate}
+\item Chercher les entiers dont le carré a, en représentation décimale,
+le même chiffre pour les dizaines et les unités.
+\item On pose $a=2p-1$, $b=2p+1$, $c=2p+3$; trouver l'entier $p$ de manière que $a^2+b^2+c^2$ soit de la forme $\sur{xxxx}_{10}$.
+\item L'entier $n$ s'écrit $\sur{341}_{10}$ et $\sur{2331}_a$. Trouver $a$.
+\item Montrer que, dans toute base $b$ supérieure ou égale à 3, l'entier qui s'écrit $\sur{11211}_b$ n'est pas premier.
+\item Soit $n\geqslant 7$. Donner l'écriture de $(n+1)^4$ en base $n$.
+\end{enumerate}
+\end{Exo}
+
+
+
+\begin{Exo}[Développement décimal]
+On considère le nombre réel $x$ dont le dé\-ve\-lop\-pe\-ment décimal s'écrit $x=0,012\ 345\ 679\ 012\ 345\ 679\ \ldots\ \ldots\ \ldots$ (la séquence $012\ 345\ 679$ est reproduite indéfiniment). Ce développement décimal est périodique, de période 9.
+\begin{enumerate}
+\item Montrer que $x$
+vérifie une équation de la forme $10^kx=n+x$, où $k$ et $n$ sont
+des entiers à déterminer. En résolvant cette équation,
+montrer que $x$ est un nombre rationnel, et le mettre sous la forme
+$x= \fr pq$ , où $p$ et $q$ sont premiers entre eux.
+\item Appliquer
+la même méthode au ``nombre" $y$ dont le développement
+décimal est $y= 0,999\ 999\ 999\ 999\ \ldots$ (périodique de période
+1). Quelle conclusion peut-on en tirer?
+\item Démontrer que tout nombre réel dont le développement
+décimal est fini ou périodique à partir d'un certain rang
+est un nombre rationnel.
+\item Réciproquement, on se propose de démontrer que le
+développement décimal de tout nombre rationnel est fini ou
+périodique à partir d'un certain rang. Pour cela, on
+considère un rationnel $x=\fr pq$ , avec $q>0$, $p\in
+\Z$, $p$ et $q$ premiers entre eux, et on étudiera successivement
+les cas suivants:
+\begin{itemize}
+\item $x$ est entier (c'est à dire $q=1$).
+\item $x$ est rationnel non entier, et $q$ est premier avec 10 (On
+pourra montrer que, si $q$ est premier avec 10, il existe un entier
+$k$, non nul, tel que $10^k\equiv 1\ [q]$).
+\item $x$ est rationnel non entier, mais $q$ n'est pas premier avec 10.
+\end{itemize}
+\end{enumerate}
+
+\end{Exo}
+
+
+
\section{Arithmétique en informatique}
