X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-maths-dis.git/blobdiff_plain/5e35d149cf50ea634e9a0c02fca2c79993d25427..8b65de9031d067d9806854c011a513c92dcf113e:/arithmetique/entiersNaturels.tex?ds=inline

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
