From 80079fdbe496fad2aa3c13e5fb5943f0eca61858 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?= Date: Tue, 2 Apr 2013 11:10:49 +0200 Subject: [PATCH] inversion bezout ordi --- arithmetique/entiersNaturels.tex | 360 +++++++++++++++++-------------- 1 file changed, 203 insertions(+), 157 deletions(-) diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex index 81ddb5b..945a103 100755 --- a/arithmetique/entiersNaturels.tex +++ b/arithmetique/entiersNaturels.tex @@ -428,6 +428,208 @@ On se place dans l'ensemble $\N$. \end{Exo} + + +\section{Théorème de Bézout} + + +On considère deux nombres entiers strictement positifs $a$ et $b$. + +\begin{Th}[Théorème de Bézout] +\index{théorème!de Bézout} +Il existe un couple d'entiers $u$ et $v$ tels que $au-bv=d$, où $d$ est le PGCD de $a$ et de $b$. +\end{Th} + +\begin{Proof} +On peut se ramener au cas où $a \et b=1$. + +En effet, si $d>1$, on peut écrire $a=a'd$ et $b=b'd$ avec $a' \et b'=1$; si le théorème est établi dans le cas du PGCD égal à $1$, on peut affirmer l'existence de $u$ et de $v$ tels que $a'u-b'v=1$; en multipliant les deux membres de cette égalité par $d$, on obtient $a'du-b'dv=d$, +soit $au-bv=d$. + +Il suffit donc d'établir le théorème dans le cas où $d=1$ ($a$ et $b$ premiers entre eux). Plaçons nous dans $(\Z/b\Z)^*$ et considérons l'application de cet ensemble dans lui-même définie par $x \fc ax$. Essayons de résoudre $ax=ax'$, soit $a(x-x')=0$, soit encore $a(x-x') \equiv 0[b]$, ou finalement $a(x-x')=kb$, avec $k \in \Z$. + +Comme $a\et b=1$, $a$ ne divise pas $b$, donc divise $k$; on peut écrire $k=k'a$, il reste $x-x'=k'b$, donc $x \equiv x'[b]$, donc $x=x'$; finalement $ax=ax' \Imp x=x'$, donc l'application envisagée est injective; comme il s'agit d'un ensemble fini, elle est évidemment aussi surjective, donc il existe $u$ tel que $au=1$, ce qui s'écrit encore $au \equiv 1[b]$, ou encore $au=bv+1$, finalement $au-bv=1$. +\end{Proof} + + + +\begin{Rem} +Ce couple n'est pas unique. +\begin{Proof} +En effet, si $(u,v)$ est un couple de Bézout pour $(a,b)$, donc tel que $au-bv=d$, où $d=a\et b$, alors, pout tout $k$ dans $\Z$, $a(u+kb)-b(v+ka)= au-bv+kab-kab=au-bv=d$ aussi. +\end{Proof} +\end{Rem} + + + +\begin{Exo} +Montrez que, si $m$ est multiple de deux nombres premiers entre eux $a$ et $b$, alors $m$ est multiple de $ab$. +\end{Exo} + +% \noindent Réponse : $1 = aa'+bb'$, donc $m = maa'+mbb'$. Or $m=ax=by$, donc $m = ab(ya'+xb')$. + + + +\begin{Exo} +\begin{enumerate} +\item Montrez que, si on divise deux entiers naturels $a$ et $b$ par leur pgcd, alors les quotients obtenus sont premiers entre eux. + +\item Réciproquement, montrer que, si les quotients obtenus en divisant $a$ et $b$ par un diviseur commun $d$ sont premiers entre eux, alors $d=\textit{PGCD}(a,b)$. +\end{enumerate} +\end{Exo} + +% \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. + +\subsection{Algorithme d'Euclide généralisé} + + + +Pour deux entiers positifs $a$ et $b$, on a vu que l'algorithme d'Euclide s'écrit : $a \et b = b \et r$, où $r$ est le reste dans la division euclidienne de $a$ par $b$. + + +En supposant $a>b$, si on pose $a=r_0$ et $b=r_1$, on définit une famille finie $(r_0,r_1,\ldots,r_k,r_{k+1})$ par $r_i=q_{i+1}r_{i+1}+r_{i+2}$ (c'est-à-dire que $r_{i+2}$ est le reste dans la division euclidienne de $r_i$ par $r_{i+1}$). + + +\noindent Cette famille... +\begin{itemize} +\item est strictement décroissante, +\item est telle que $r_{k+1}=0$, +\item vérifie $r_0 \et r_1 = r_1 \et r_2= \ldots = r_{k-1} \et r_k = r_k \et r_{k+1} = r_k \et 0 = r_k$. +\end{itemize} + +\bigskip + +On remarque que $r_{k-1}$ est un multiple de $r_k$, puisque la division euclidienne de $r_{k-1}$ par $r_k$ s'écrit $r_{k-1}=q_kr_k$. + +Soit $d$ le PGCD de $a$ et de $b$ (évidemment, $d=r_k$), on peut écrire $1 \times r_k-0 \times r_{k-1} = d$ puis $1 \times r_{k-2} - q_{k-1} \times r_{k-1}=d$. + + +D'une manière générale, si $(u,v)$ est un couple de Bézout pour $r_{i+1}$ et $r_{i+2}$, soit $u \cdot r_{i+1}+v \cdot r_{i+2}=d$, comme $r_i=q_{i+1}\cdot r_{i+1} + r_{i+2}$, on a $u\cdot r_{i+1}+v \cdot (r_i-q_{i+1}\cdot r_{i+1})=d$, soit $(u-q_{i+1}\cdot v)\cdot r_{i+1}+v \cdot r_i=d$. + +\subsection{L'algorithme.} +\index{algorithme!d'Euclide!généralisé} +Ceci donne l'idée de construire deux familles par les relations : +\begin{itemize} +\item $u_0=1$, $u_1=0$,$u_{i+2}=u_i-q_{i+1} \cdot u_{i+1}$ +\item $v_0=0$, $v_1=1$, $v_{i+2}=v_i-q_{i+1} \cdot v_{i+1}$. +\end{itemize} + +C'est ce que l'on appelle algorithme d'Euclide généralisé. On a alors $(u_k,v_k,r_k)=(u,v,d)$, $u$ et $v$ tels que $a \cdot u+b \cdot v=d$. + +\begin{Pre} +Pour cela, il suffit de montrer par récurrence que $\qqs i \in +\{0,\ldots,k\}, r_0 \cdot u_i + r_1 \cdot v_i = r_i$. +\begin{itemize} + \item Initialisation de la récurrence : la relation est vraie pour $i=0$, en effet $r_0 \cdot u_0+r_1 \cdot v_0=r_0$, puisque $u_0=1$ et $v_0=0$. +\item Caractère héréditaire de la propriété : en supposant que $i$ est un entier pour lequel $r_0 \cdot u_i + r_1 \cdot v_i = +r_i$ et $r_0 \cdot u_{i+1}+r_1 \cdot v_{i+1}=r_{i+1}$, calculons $r_0 \cdot u_{i+2}+r_1 \cdot v_{i+2}= r_0 \cdot (u_i-q_{i+1} \cdot u_{i+1}) + r_1 \cdot (v_i-q_{i+1} \cdot v_{i+1}) = r_0 \cdot +u_i+r_1 \cdot v_i-q_{i+1}\cdot (r_0 \cdot u_{i+1}+r_1 \cdot +v_{i+1})=r_i-q_{i+1}\cdot r_{i+1}=r_{i+2}$. +\end{itemize} +\end{Pre} + + +\subsection{Exemple.} + +Illustrons la mise en \oe{}uvre de cet algorithme... + +\begin{Ex} +Soit à obtenir un couple de Bézout pour (23,17) :\vskip 10pt +\begin{center}\begin{tabular}{c c c c} +(23,1,0) & (17,0,1) & $\longrightarrow$ & $q=1$ \\ +(17,0,1) & (6,1,-1) & $\longrightarrow$ & $q=2$ \\ +(6,1,-1) & (5,-2,3) & $\longrightarrow$ & $q=1$ \\ +(5,-2,3) & (1,3,-4) & $\longrightarrow$ & $q=5$ \\ +(1,3,-4) & (0,-17,23) & $\longrightarrow$ & FIN +\end{tabular}\end{center}\vskip 10pt +On a bien $3 \times 23-4 \times 17=1$.\psaut +\end{Ex} + +\begin{Rem} +Il est possible d'obtenir -1 (ou $-d$ en général) comme résultat, donc $au-bv=-1$, cela dépend de la parité du nombre d'itérations effectuées dans l'algorithme précédent. + +Ce n'est pas un résultat faux, puisqu'alors $bv-au=1$ et qu'on a quand même un couple de Bézout pour $(b,a)$. + +S'il est nécessaire d'obtenir un couple $(u,v)$ tel que $au-bv=1$ +et où $a$ et $b$ figurent dans cet ordre, et que l'algorithme a fourni un couple $(u',v')$ tel que $bv'-au'=1$, il suffit de prendre $u=b-u'$ et $v=a-v'$ et, dans ces conditions $au-bv=a(b-u')-b(a-v')= ab -au' -ab +bv'=bv'-au'=1$. +\end{Rem} + +\begin{Exo} +Exprimer $\textit{PGCD}(1330,602)$ comme combinaison à coefficients entiers des nombres 1330 et 602. +\end{Exo} + + + +\begin{Th}[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{Th} + + +\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} + +\begin{Exo} + On considère l'équation $\frac{x}{0}-\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$. +\item Démontrer que le PGCD de $x$ et $y$ ne peut être qu’un diviseur de 108. +\item Soit $m$ le ppcm de $x$ et de $y$. + On envisage la décomposition de $m$ en facteurs premiers. + Trouver l'ensemble des entiers naturel $k$ pour que + \begin{enumerate} + \item $m$ ne contienne pas le facteur 2. + \item $m$ contienne le facteur 2 ou le facteur $2^2$. +\item $m$ ne contienne pas le facteur 3. +\item $m$ contienne le facteur 3, ou le facteur $3^2$, ou le facteur $3^3$. +\end{enumerate} +\item Comment faut-il choisir $x$ et $y$ de telle façon que + l’on ait $\textit{PGCD}(x,y) = 18$? +\end{enumerate} +\end{Exo} + +\begin{Exo} +\begin{enumerate} +\item Décomposer 319 en facteurs premiers. + +\item Démontrer que si $x$ et $y$ sont deux entiers + naturels premiers entre eux, il en est de même pour les + nombres $3x + 5y$ et $x + 2y$. +\item Résoudre dans $\Z^2$ le système d’inconnues $a$ et $b$: +$$ +\left\{ +\begin{array}{rcl} +(3a +5b)(a+2b) &= & 1276\\ +ab & = & 2m +\textrm{ tel que $m$ est le PPCM de $a$ et $b$. } +\end{array} +\right. +$$ +\end{enumerate} +\end{Exo} + +\begin{Exo} +Au 8° siècle, un groupe composé d’hommes et +de femmes a dépensé 100 pièces de monnaie dans une +auberge. +Les hommes ont dépensé 8 pièces chacun et les femmes 5 +pièces chacune. Combien pouvait-il y +avoir d’hommes et de femmes dans le groupe? +\end{Exo} + + \section{Représentation des nombres entiers} @@ -467,7 +669,7 @@ Donner la représentation de 23 en base 2. 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 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} @@ -924,160 +1126,4 @@ Opération binaire & Entiers non signés & Entiers signés \\ \end{tabular} \end{center} \end{Ex} - - - - - - -\section{Théorème de Bézout} - - -On considère deux nombres entiers strictement positifs $a$ et $b$. - -\begin{Th}[Théorème de Bézout] -\index{théorème!de Bézout} -Il existe un couple d'entiers $u$ et $v$ tels que $au-bv=d$, où $d$ est le PGCD de $a$ et de $b$. -\end{Th} - -\begin{Proof} -On peut se ramener au cas où $a \et b=1$. - -En effet, si $d>1$, on peut écrire $a=a'd$ et $b=b'd$ avec $a' \et b'=1$; si le théorème est établi dans le cas du PGCD égal à $1$, on peut affirmer l'existence de $u$ et de $v$ tels que $a'u-b'v=1$; en multipliant les deux membres de cette égalité par $d$, on obtient $a'du-b'dv=d$, -soit $au-bv=d$. - -Il suffit donc d'établir le théorème dans le cas où $d=1$ ($a$ et $b$ premiers entre eux). Plaçons nous dans $(\Z/b\Z)^*$ et considérons l'application de cet ensemble dans lui-même définie par $x \fc ax$. Essayons de résoudre $ax=ax'$, soit $a(x-x')=0$, soit encore $a(x-x') \equiv 0[b]$, ou finalement $a(x-x')=kb$, avec $k \in \Z$. - -Comme $a\et b=1$, $a$ ne divise pas $b$, donc divise $k$; on peut écrire $k=k'a$, il reste $x-x'=k'b$, donc $x \equiv x'[b]$, donc $x=x'$; finalement $ax=ax' \Imp x=x'$, donc l'application envisagée est injective; comme il s'agit d'un ensemble fini, elle est évidemment aussi surjective, donc il existe $u$ tel que $au=1$, ce qui s'écrit encore $au \equiv 1[b]$, ou encore $au=bv+1$, finalement $au-bv=1$. -\end{Proof} - - - -\begin{Rem} -Ce couple n'est pas unique. -\begin{Proof} -En effet, si $(u,v)$ est un couple de Bézout pour $(a,b)$, donc tel que $au-bv=d$, où $d=a\et b$, alors, pout tout $k$ dans $\Z$, $a(u+kb)-b(v+ka)= au-bv+kab-kab=au-bv=d$ aussi. -\end{Proof} -\end{Rem} - - - -\begin{Exo} -Montrez que, si $m$ est multiple de deux nombres premiers entre eux $a$ et $b$, alors $m$ est multiple de $ab$. -\end{Exo} - -\noindent Réponse : $1 = aa'+bb'$, donc $m = maa'+mbb'$. Or $m=ax=by$, donc $m = ab(ya'+xb')$. - - - -\begin{Exo} -Montrez que, si on divise deux entiers naturels $a$ et $b$ par leur pgcd, alors les quotients obtenus sont premiers entre eux. - -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 = \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. - - - -\subsection{Algorithme d'Euclide généralisé} - - - -Pour deux entiers positifs $a$ et $b$, on a vu que l'algorithme d'Euclide s'écrit : $a \et b = b \et r$, où $r$ est le reste dans la division euclidienne de $a$ par $b$. - - -En supposant $a>b$, si on pose $a=r_0$ et $b=r_1$, on définit une famille finie $(r_0,r_1,\ldots,r_k,r_{k+1})$ par $r_i=q_{i+1}r_{i+1}+r_{i+2}$ (c'est-à-dire que $r_{i+2}$ est le reste dans la division euclidienne de $r_i$ par $r_{i+1}$). - - -\noindent Cette famille... -\begin{itemize} -\item est strictement décroissante, -\item est telle que $r_{k+1}=0$, -\item vérifie $r_0 \et r_1 = r_1 \et r_2= \ldots = r_{k-1} \et r_k = r_k \et r_{k+1} = r_k \et 0 = r_k$. -\end{itemize} - -\bigskip - -On remarque que $r_{k-1}$ est un multiple de $r_k$, puisque la division euclidienne de $r_{k-1}$ par $r_k$ s'écrit $r_{k-1}=q_kr_k$. - -Soit $d$ le PGCD de $a$ et de $b$ (évidemment, $d=r_k$), on peut écrire $1 \times r_k-0 \times r_{k-1} = d$ puis $1 \times r_{k-2} - q_{k-1} \times r_{k-1}=d$. - - -D'une manière générale, si $(u,v)$ est un couple de Bézout pour $r_{i+1}$ et $r_{i+2}$, soit $u \cdot r_{i+1}+v \cdot r_{i+2}=d$, comme $r_i=q_{i+1}\cdot r_{i+1} + r_{i+2}$, on a $u\cdot r_{i+1}+v \cdot (r_i-q_{i+1}\cdot r_{i+1})=d$, soit $(u-q_{i+1}\cdot v)\cdot r_{i+1}+v \cdot r_i=d$. - -\subsection{L'algorithme.} -\index{algorithme!d'Euclide!généralisé} -Ceci donne l'idée de construire deux familles par les relations : -\begin{itemize} -\item $u_0=1$, $u_1=0$,$u_{i+2}=u_i-q_{i+1} \cdot u_{i+1}$ -\item $v_0=0$, $v_1=1$, $v_{i+2}=v_i-q_{i+1} \cdot v_{i+1}$. -\end{itemize} - -C'est ce que l'on appelle algorithme d'Euclide généralisé. On a alors $(u_k,v_k,r_k)=(u,v,d)$, $u$ et $v$ tels que $a \cdot u+b \cdot v=d$. - -\begin{Pre} -Pour cela, il suffit de montrer par récurrence que $\qqs i \in -\{0,\ldots,k\}, r_0 \cdot u_i + r_1 \cdot v_i = r_i$. -\begin{itemize} - \item Initialisation de la récurrence : la relation est vraie pour $i=0$, en effet $r_0 \cdot u_0+r_1 \cdot v_0=r_0$, puisque $u_0=1$ et $v_0=0$. -\item Caractère héréditaire de la propriété : en supposant que $i$ est un entier pour lequel $r_0 \cdot u_i + r_1 \cdot v_i = -r_i$ et $r_0 \cdot u_{i+1}+r_1 \cdot v_{i+1}=r_{i+1}$, calculons $r_0 \cdot u_{i+2}+r_1 \cdot v_{i+2}= r_0 \cdot (u_i-q_{i+1} \cdot u_{i+1}) + r_1 \cdot (v_i-q_{i+1} \cdot v_{i+1}) = r_0 \cdot -u_i+r_1 \cdot v_i-q_{i+1}\cdot (r_0 \cdot u_{i+1}+r_1 \cdot -v_{i+1})=r_i-q_{i+1}\cdot r_{i+1}=r_{i+2}$. -\end{itemize} -\end{Pre} - - -\subsection{Exemple.} - -Illustrons la mise en \oe{}uvre de cet algorithme... - -\begin{Ex} -Soit à obtenir un couple de Bézout pour (23,17) :\vskip 10pt -\begin{center}\begin{tabular}{c c c c} -(23,1,0) & (17,0,1) & $\longrightarrow$ & $q=1$ \\ -(17,0,1) & (6,1,-1) & $\longrightarrow$ & $q=2$ \\ -(6,1,-1) & (5,-2,3) & $\longrightarrow$ & $q=1$ \\ -(5,-2,3) & (1,3,-4) & $\longrightarrow$ & $q=5$ \\ -(1,3,-4) & (0,-17,23) & $\longrightarrow$ & FIN -\end{tabular}\end{center}\vskip 10pt -On a bien $3 \times 23-4 \times 17=1$.\psaut -\end{Ex} - -\begin{Rem} -Il est possible d'obtenir -1 (ou $-d$ en général) comme résultat, donc $au-bv=-1$, cela dépend de la parité du nombre d'itérations effectuées dans l'algorithme précédent. - -Ce n'est pas un résultat faux, puisqu'alors $bv-au=1$ et qu'on a quand même un couple de Bézout pour $(b,a)$. - -S'il est nécessaire d'obtenir un couple $(u,v)$ tel que $au-bv=1$ -et où $a$ et $b$ figurent dans cet ordre, et que l'algorithme a fourni un couple $(u',v')$ tel que $bv'-au'=1$, il suffit de prendre $u=b-u'$ et $v=a-v'$ et, dans ces conditions $au-bv=a(b-u')-b(a-v')= ab -au' -ab +bv'=bv'-au'=1$. -\end{Rem} - -\begin{Exo} -Exprimer $pgcd(1330,602)$ comme combinaison à coefficients entiers des nombres 1330 et 602. -\end{Exo} - - - -\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} - \centerline{\x{Fin du Chapitre}} \ No newline at end of file -- 2.39.5