From: Jean-François Couchot Date: Tue, 2 Apr 2013 06:55:48 +0000 (+0200) Subject: t X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-maths-dis.git/commitdiff_plain/8b65de9031d067d9806854c011a513c92dcf113e t --- diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex index fbc1326..81ddb5b 100755 --- a/arithmetique/entiersNaturels.tex +++ b/arithmetique/entiersNaturels.tex @@ -311,21 +311,22 @@ def pgcd_euclide(a,b) : \end{scriptsize} \bigskip -\begin{Exo} +\begin{Exo}[Application de l'algorithme d'Euclide] Si $p$ est un nombre premier, et $n$ un entier avec $n \ge 2$, on note $a=p^n+1$ et $b=p^n-1$. \begin{enumerate} \item On suppose que $p$ est égal à 2. \begin{enumerate} +\item Montrer que $2^n -1 = 2 \times (2^{n-1} -1) +1$ pour $n \ge 2$. \item Calculer $d = a \et b$ au moyen de l'algorithme d'Euclide. -\item Déterminer tous les couples d'entiers relatifs $(u,v)$ tels que $ua + vb=d$. +\item Déterminer un couple d'entiers relatifs $(u,v)$ tels que $ua + vb=d$. \end{enumerate} \item On suppose maintenant que $p$ est différent de 2. \begin{enumerate} \item Montrer que $a$ et $b$ sont pairs et poser $a=2A$ et $b=2B$. \item Calculer $A-B$. En déduire la valeur $d$ de $a \et b$. -\item Déterminer tous les couples d'entiers relatifs $(u,v)$ tels que $ua + vb=d$. +\item Déterminer un couple d'entiers relatifs $(u,v)$ tels que $ua + vb=d$. \end{enumerate} \end{enumerate} \end{Exo} @@ -444,7 +445,7 @@ En informatique, on utilise couramment les bases 2, 8 et 16. -\subsection{Obtention de cette représentation} + L'algorithme pour obtenir la représentation en base $b$ d'un entier est : @@ -454,26 +455,20 @@ L'algorithme pour obtenir la représentation en base $b$ d'un entier est : \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} - -% \subsection{Algorithme de Hörner} - -% Réciproquement, étant donnée la représentation en base $b$ d'un -% entier, on obtient sa valeur par application de l'algorithme de Hörner : - -% $n= n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$ est calculé par -% $(......(((n_{p}b+n_{p-1})b+n_{p-2})b+\cdots+n_{1})b+n_{0})$ - - +\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, mêmes chiffres des dizaines et des unités. +\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$. +\item Soit $n\geqslant 7$. Donner l'écriture de $(n+1)^4$ en base $n$. \end{enumerate} \end{Exo} @@ -501,7 +496,7 @@ 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 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]$). @@ -526,8 +521,8 @@ $$x \equiv y [n] \Ssi \exi k \in \Z, x-y=k \cdot n $$ \begin{Exo} Calculez : \begin{enumerate} - \item $3*10^9 mod 97$, -\item $3^{1024} mod 1037$. + \item $3*10^9 \mod 97$, +\item $3^{1024} \mod 1037$. \end{enumerate} \end{Exo} @@ -545,9 +540,9 @@ En effet : \begin{itemize} \item $\qqs x \in \Z, x-x=0=0 \cdot n$; or $0 \in \Z$, donc $x \equiv x [n]$ (réflexivité). \item Si $x \equiv y -[n]$,$\exi k \in \Z$, $x-y=k \cdot n$; alors $y-x=(-k) \cdot n$, et, +[n]$, $\exi k \in \Z$, $x-y=k \cdot n$; alors $y-x=(-k) \cdot n$, et, puisque $k \in \Z$, $(-k) \in \Z$, donc $y \equiv x [n]$ (symétrie). -\item Si $x \equiv y [n]$,$\exi k\in\Z$, $x-y=k \cdot n$; si, de +\item Si $x \equiv y [n]$, $\exi k\in\Z$, $x-y=k \cdot n$; si, de plus, $y \equiv z [n]$, $\exi l\in\Z$, $y-z=l \cdot n$; alors (par addition), $x-z=(k+l) \times n$; comme $k\in\Z$ et $l\in\Z$, $(k+l)\in\Z$, donc $x \equiv z [n]$ (transitivité). @@ -704,8 +699,8 @@ Donc $pu \equiv 1\ [q]$ et $qv \equiv 1\ [p]$, et $x=bpu+aqv$ est une solution d $$\left\{\begin{array}{ccc} x & \equiv & 2\ [88] \\ x & \equiv & 1\ [27] \\ -\end{array}\right.$$ -\item {\it Application: Problème du cuisinier}: Une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or, toutes d'égale valeur. +\end{array}\right..$$ +\item {\it Application au problème du cuisinier}: une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or, toutes d'égale valeur. Ils décident de se les partager également et de donner le reste éventuel au cuisinier. Celui-ci recevrait alors 3 pièces d'or. @@ -790,10 +785,8 @@ la représentation physique est la même. Comme il nous est difficile de représenter ici la liste compléte de tous ces entiers, nous allons illustrer ce propos en supposant que les entiers sont représentés sur 4 bits. +Pour des mots de 4 bits, il y a alors 16 entiers représentables : (a.s.= arithmétique signée, a.n.s. = arithmétique non signée) -\subsubsection{Illustration dans le cas de 4 bits.} - -Pour des mots de 4 bits, il y a alors 16 entiers représentables : (a.s.= arithmétique signée, a.n.s. = arithmétique non signée)\vskip 10pt \begin{center}\begin{tabular}{|c|c|c|c|} \hline code binaire & & a.s. & a.n.s. \\ \hline 0000 & interprété par & 0 & 0 \\ \hline @@ -836,15 +829,11 @@ Mais il n'en reste pas moins que tous les entiers négatifs commencent par 1). Ainsi, il est facile de déduire la comparaison signée de la comparaison non signée : les codes qui commencent par 1 sont \og plus petits\fg{} que ceux qui commencent par 0, et, s'ils commencent par le même bit, c'est la comparaison non signée qui peut être utilisée. -Mais il y a quand même deux instructions assembleur distinctes pour la comparaison signée et pour la comparaison non signée. - -\subsubsection{Quelques exemples de calculs.} Pour l'addition et la soustraction, les opérations et les tests de validité des résultats sont les mêmes en arithmétique signée et non signée. - -\noindent Pour la multiplication, l'instruction assembleur n'est pas la même (le dépassement de capacité doit être ignoré en a.s. dans le dernier exemple). +Pour la multiplication, l'instruction n'est pas la même (le dépassement de capacité doit être ignoré en a.s. dans le dernier exemple). \begin{Ex} @@ -987,7 +976,7 @@ Montrez que, si on divise deux entiers naturels $a$ et $b$ par leur pgcd, alors Réciproquement, montrer que, si les quotients obtenus en divisant $a$ et $b$ par un diviseur commun $d$ sont premiers entre eux, alors $d=pgcd(a,b)$. \end{Exo} -\noindent Réponse : Soit $d = pgcd(a,b)$, et $q_1$ et $q_2$ les quotients de $a$ et $b$ par $d$. Alors $d = aa'+bb' = d q_1 a' + d q_2 b'$. Donc $1 = q_1 a' + q_2 b'$ : $q_1$ et $q_2$ sont premiers entre eux. La réciproque est du même genre. +\noindent Réponse : Soit $d = \textit{PGCD}(a,b)$, et $q_1$ et $q_2$ les quotients de $a$ et $b$ par $d$. Alors $d = aa'+bb' = d q_1 a' + d q_2 b'$. Donc $1 = q_1 a' + q_2 b'$ : $q_1$ et $q_2$ sont premiers entre eux. La réciproque est du même genre. @@ -1069,9 +1058,26 @@ et où $a$ et $b$ figurent dans cet ordre, et que l'algorithme a fourni un coupl Exprimer $pgcd(1330,602)$ comme combinaison à coefficients entiers des nombres 1330 et 602. \end{Exo} -%\noindent Réponse $14 = 1330*(-19)+602*42$. +\begin{Theo}[Théorème de Gauss] +Soient $a$, $b$ et $c$ trois entiers naturel non nuls. +Si $a$ divise le produit $bc$ et si $a$ est premier avec $b$, +alors $a$ divise $c$. +\end{Theo} + + +\begin{Exo} +L'objectif est de résoudre l'équation $(E)$ d'inconnues $x$ et $y$ +$405x -120y =15$. +\begin{enumerate} +\item Trouver le pgcd de 405 et 120 à l'aide de l'algorithme d'Euclide. +\item En déduire une solution particulière de cette équation. +\item En utilisant la solution particulière, montrer que $(E)$ est + équivalente à $27(x-3) = 8(y-10)$. +\item Utiliser le théorème de Gauss pour montrer que + l'ensemble solution de $(E)$ est $\{(8k+3;27k+10)| k \in \Z\}$. +\end{enumerate} +\end{Exo} -\gsaut \centerline{\x{Fin du Chapitre}} \ No newline at end of file