Arithmétique - T S1
Classe:
Terminale
Introduction
Le développement de l'informatique et plus généralement de ce qu'on appelle "le numérique", est étroitement lié à l'arithmétique.
Lorsqu'on a besoin de traiter des informations, de faire fonctionner des documents multimédias (textes, sons, images) sur des machines, il est souvent nécessaire de les coder.
Toute information peut être codée en utilisant des suites formées uniquement de deux symboles $0\ $ et $\ 1.$
On parle de représentation binaire...
I. Rappels
$\centerdot\ \ \mathbb{N}\subset \mathbb{Z}\subset\mathbb{D}\subset\mathbb{Q}\subset\mathbb{R}$
$\centerdot\ \ $ Soit $\mathcal{G}$ un ensemble.
Une loi $\ast$ est dite interne dans $\mathcal{G}$ si $\forall\;x, y \in \mathcal{G}$, $\ x\ast y\in \mathcal{G}$.
L'addition est interne dans $\mathbb{Z}$
$\mathcal{P}\ $ : ensemble des entiers pairs ; $x \in \mathcal{P}\Leftrightarrow x=2k$
$\mathcal{I}\ $ : ensemble des entiers impairs ; $x \in \mathcal{I}\Leftrightarrow x=2k+1$
$\begin{array}{rcl} x\;,\ y \in\mathcal{P}\;,\ x=2k\;,\ y=2k' & \Rightarrow & x+y=2(k+k')\in\mathcal{P} \\ \\ & \Rightarrow & (+) \text{ est interne dans }\mathcal{P} \end{array}$
$\begin{array}{rcl} x,\ y \in \mathcal{I}\;,\ x=2k+1\;,\ y=2k'+1 & \Rightarrow & x+y=2(k+k'+1)\notin \mathcal{I} \\ \\ & \Rightarrow & + \text{ n'est pas interne dans }\mathcal{I} \end{array}$
$\begin{array}{rcl} xy & = & (2k+1)(2k'+1)=4kk'+2k+2k'+1 \\ \\ & = & 2(2kk'+k+k'+1)+1 \\ \\ & = & 2p+1\in \mathcal{I}\end{array}$
Ainsi, $\cdot$ est interne dans $\mathcal{I}$
$\centerdot\ \ $ Une loi $\ast$ est dite associative dans $\mathcal{G}$ si $\forall\;a, b, c \in \mathcal{G}$, $\ (a\ast b)\ast c=a\ast(b\ast c)$
$\centerdot\ \ e$ est un élément neutre si $\forall\;x\in \mathcal{G}$, $\ x\ast e=e\ast x=x$
Dans $\mathbb{Z}\;,\ 0$ est l'élément neutre pour $+\;,\ 1$ est l'élément neutre pour $\cdot$
$\centerdot\ \ $ Le symétrique de $x\in \mathcal{G}$ pour la loi $\ast$ est l'élément $x'$ tel que $x\ast x'=x'\ast x=e$
On dira que $(\mathcal{G},\ \ast)$ est un groupe si :
$\centerdot\ \ \ast$ est interne
$\centerdot\ \ \ast$ est associative
$\centerdot\ \ (\mathcal{G}, \ast)$ admet un élément neutre
$\centerdot\ \ $ tout élément de $\mathcal{G}$ admet un symétrique.
Si de plus $\forall\;a,\ b \in \mathcal{G}$, $\ a\ast b=b\ast a$ , on dira que $(\mathcal{G},\ \ast)$ est un groupe commutatif
On dira qu'une loi $\perp$ est distributive par rapport à une loi $\ast$ si $\forall\;a,\ b,\ c \in \mathcal{G}$, $\ a\perp(b\ast c)=(a\perp b)\ast(a\perp c)$
Exemple :
$a\times(b+c)=(a\times b)+(a\times c)$ : la loi $\times$ est distributive par rapport à +
$\centerdot\ \ $ Une relation $R$ est dite réflexive dans $\mathcal{G}$ si $\forall\;a \in \mathcal{G}$ $\ aRa$
Exemple :
$\leq\ $ est une relation réflexive
$=\ $ est une relation réflexive
$<\ $ n'est pas réflexive
$\centerdot\ \ $ Une relation $R$ est dite symétrique dans $\mathcal{G}$ si $\forall\;a,\ b \in \mathcal{G}$ $\ aRb$ $\Rightarrow$ $bRa$
$\centerdot\ \ $ Une relation $R$ est dite antisymétrique dans $\mathcal{G}$ si $\forall\;a,\ b \in \mathcal{G}$ $\ aRb$ et $bRa$ $\Rightarrow$ $a=b$ (si $aRb$ $\Rightarrow$ $b\bar{R} a$)
$\centerdot\ \ R$ est dite transitive dans $\mathcal{G}$ si $\forall\;a,\ b,\ c \in \mathcal{G}$ $\ aRb$ et $bRc$ $\Rightarrow$ $aRc$
$\centerdot\ \ $ Une relation $R$ est une relation d'équivalence si elle est :
$\centerdot\ \ $ réflexive
$\centerdot\ \ $ symétrique
$\centerdot\ \ $ transitive
$\centerdot\ \ $ Une relation $R$ est une relation d'ordre si elle est :
$\centerdot\ \ $ réflexive
$\centerdot\ \ $ antisymétrique
$\centerdot\ \ $ transitive
Les trois axiomes fondamentaux
$\centerdot\ \ $ Toute partie non vide de $\mathbb{N}$ admet un plus petit élément. (Faux dans $\mathbb{Z}$)
$\centerdot\ \ $ Toute partie non vide et majorée de $\mathbb{N}$ admet un plus grand élément.
$\centerdot\ \ $ Toute suite d'entiers naturels strictement décroissante est finie. (Faux dans $\mathbb{Z}$)
II. Diviseurs et multiples d'un entier
II.1 Définitions
Soient $a$ et $b$ deux entiers relatifs.
On dit que $b$ divise $a$ ou $b$ est un diviseur de $a$ ou que $a$ est un multiplicateur de $b$ et on note $b|a$ s'il existe un entier $k$ tel que $a=b.k$
L'ensemble des diviseurs de $a$ est noté $D(a)$ et l'ensemble des multiplicateurs de $a$ est noté $m(a)$
L'ensemble des multiples de $n$ est noté $n\mathbb{Z}$
II.2 Propriétés
$\centerdot\ \ 1$ divise tout nombre, $0$ est un multiple de tout nombre
$\centerdot\ \ $ tout entier naturel non nul $a$ possède au moins quatre diviseurs $1\;,\ -1\;,\ a\ $ et $\ -a$
$\centerdot\ \ $ Si $a|b$ et si $b|a$ alors, $a=\pm b$
$a|b$ et $b|a$ alors, $|a|\leq |b|\ $ et $\ |b|\leq |a|$ donc $|a|=|b|$, soit $a=\pm b$
$\centerdot\ \ $ Si $a|b$ alors, $a|bc$ quel que soit l'entier $c$
$a|b$ alors il existe un entier $k$ tel que $b=a.k$. Alors, $b.c=(a.k).c=a.(k.c)$ donc, $a|bc$.
$\centerdot\ \ $ Si $a|b$ et $b\neq 0$ alors, $|a|\leq |b|$. Ainsi, tout entier non nul admet un nombre fini de diviseurs.
$a|b$ et $b\neq 0$ alors il existe un entier $k$ non nul tel que $b=ak$ donc, $|b|=|a||k|$ et $|k|\geq 1$ d'où $|b|\geq |a|$.
$\centerdot\ \ $ Si $a|b$ et si $b|c$ alors, $a|c$
$a|b$ et si $b|c$ alors il existe deux entiers $k$ et $r$ tels que $b=a.k$ et $c=b.r$ donc $c=(ak)r=a(kr)$ d'où $a|c$.
$\centerdot\ \ $ Si $a|b$ et si $a|c$ alors, $a$ divise toute combinaison linéaire de $b$ et $c$, $\alpha.b+\beta.c$ où $\alpha$ et $\beta$ sont des entiers relatifs.
$a|b$ et $a|c$ alors il existe deux entiers $k$ et $r$ tels que $b=ak$ et $c=ar$
donc, $\alpha b+\beta c=\alpha (ak)+\beta (ar)=a(\alpha k+\beta r)$ d'où $a|(\alpha b+\beta c).$
En particulier si $a|b$ et $a|c$ alors, $a|(b+c)$ et $a|(b-c)$
III. Les nombres premiers
III.1 Définitions
Un entier naturel $n$ est premier s'il possède exactement deux diviseurs distincts $1$ et lui-même.
Exemple :
$2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $59$, $61$, $71$, $73$, $79$, $83$, $89$, $91$, $97$
$2$ est le seul nombre premier pair
III.2 Propriétés
Soit $n$ un entier naturel strictement supérieur à $1$, alors
$\centerdot\ \ $ $n$ admet au moins un diviseur premier.
$\centerdot\ \ $ Si $n$ n'est pas premier, il admet un diviseur premier $p$ tel que $p^{2}\leq n$
Soit $D'(n)$ l'ensemble des diviseurs de $n$ strictement supérieur à $1.$
$D'(n)$ n'est pas vide car il contient $n$.
$D'(n)$ étant une partie non vide de $\mathbb{N}$ admet un plut petit élément $p$.
On sait que $p>1$ et que $p$ divise $n$
Montrons que $p$ est premier :
Soit $q$ un diviseur de $p$ strictement supérieur à $1.$
$q\leq p$ et $q|n$ (car $q|p$ et $p|n$), donc $q=p$ ($p$ étant le plus petit élément de $D'(n)$).
Si $n$ n'est pas premier, $n$ s'écrit $n=pk$ avec $p\leq k\ $ ($p$ étant le plus petit des diviseurs de $n$ strictement supérieur à $1)$
d'où, $p^{2}\leq pk$ soit $p^{2}\leq n$. $c.q.f.d$
$\centerdot$ Un entier naturel $n>1$ est premier s'il n'est divisible par aucun nombre premier inférieur à $\sqrt{n}$.
D'où un algorithme de recherche de primalité par essai de division par les nombres premiers successifs à partir de $2$ :
Si $n$ est divisible par $2$, $n$ n'est pas premier et c'est fini.
Sinon, on divise par $3.$
Si $3|n$ c'est fini Sinon, on divise par l'entier premier suivant $5$, etc...
On arrête les divisions au plus grand entier premier $p$ tel que $p\leq \sqrt{n}$.
Encore faut-il connaître la liste des nombres premiers inférieurs à $\sqrt{n}$!
Exemple :
$n=409$ est -il premier ?
$\sqrt{409}\approx 20.22$ On essai donc les divisions successives par les entiers premiers inférieurs ou égaux à $20$ soit : $2$, $3$, $5$, $7$, $11$, $13$, $17$ et $19$ $409$ est premier.
III.3 Décomposition en produits de facteurs premiers
Pour tout entier naturel $n$ , il existe des nombres premiers distincts $p_{1}, p_{2}, p_{3}, \ldots , p_{n}$ et des entiers naturels $\alpha_{1}, \alpha_{2}, \alpha_{3}\ldots ,\alpha_{n}$ tels que $n=p_{1}^{\alpha_{1}}.p_{2}^{\alpha_{2}}.p_{3}^{\alpha_{3}}.\ldots p_{n}^{\alpha_{n}}$ et que le nombre de diviseurs de $n$ est égal à $$(\alpha_{1}+1).(\alpha_{2}+1).(\alpha_{3}+1).\ldots .(\alpha_{n}+1)$$
Exemple :
$2^{4}*3^{2}*5^{3}*11=198\,000$
$(4+1)(2+1)(3+1)(1+1)=5*3*4*2=120$ diviseurs
IV. Plus grand et commun diviseur - Plus petit commun multiple
IV.1 Division euclidienne
$a\ $ et $\ b$ $\ (b\neq 0)$ deux entiers $a\geq b$, il existe un couple d'entiers $(q;\ r)$ tels que $a=b.q+r$ avec $0\leq r<b$
Cette opération est appelée division euclidienne.
Remarques :
$(q;\ r)$ est unique
$bq\leq a<b(q+1)$
IV.2 Algorithme d'Euclide
$a$ et $b$ $(b\neq 0)$ deux entiers tels que $a=b.q+r$ avec $0\leq r<b$
$\centerdot\ \ $ Si $d|a$ et $d|b$ alors, $d$ est un diviseur commun à $a$ et à $b.$
$\centerdot\ \ $ Si $r=0\;,\ 0|a$ alors, l'ensemble des diviseurs communs à $a$ et à $b$ sont les diviseurs de $r.$
$\centerdot\ \ $ Si $r\neq 0\;,\ d|(a-bq)$ alors, $d|r$
$\centerdot\ \ $ Si $d|b\ $ et $\ d|r$ alors, $d$ est un diviseur commun à $b$ et à $r\ $ $(b=q_{1}r+r_{1}$ avec $0\leq r_{1}<r).$
$\centerdot\ \ $ Si $d|b\ $ et $\ d|r$ alors, $d|(b-q_{1}r)$ $\Rightarrow$ $d|r_{1}$ ainsi, $d$ est un diviseur commun à $r$ et à $r_{1}$ $(r=q_{2}r_{1}+r_{2}$ avec $0\leq r_{2}<r_{1}).$
$\centerdot\ \ $ Si $d|r\ $ et $\ d|r_{1}$ alors, $d|(r-q_{2}r_{1})$ $\Rightarrow$ $d|r_{2}$, ainsi $d$ est un diviseur commun à $r_{1}$ et à $r_{2}$ $(r_{1}=q_{3}r_{2}+r_{3}$ avec $0\leq r_{3}<r_{2}).$
Ainsi de suite, si $r_{n}$ est le dernier reste non nul alors, $d|r_{n-1}\;,\ d|r_{n}\ $ et $\ r_{n-1}=qr_{n}$ $\Rightarrow$ $r_{n}|r_{n-1}$
D'où, les diviseurs communs à $a$ et à $b$ sont les diviseurs de $r_{n}\ $ et $\ r_{n}$ est le plus grand diviseur commun à $a$ et à $b.$
Cette suite de division est appelée algorithme d'Euclide
Exemple :
$a=37236$ $b=1650$
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
a & 37236 & 1650 & 936 & 714 & 222 & 48 & 30 & 18 & 12 \\
\hline
b & 1650 & 936 & 714 & 222 & 48 & 30 & 18 & 12 & 6 \\
\hline
\text{reste} & 936 & 714 & 222 & 48 & 30 & 18 & 12 & 6 & 0 \\
\hline
\end{array}$$
\hline
a & 37236 & 1650 & 936 & 714 & 222 & 48 & 30 & 18 & 12 \\
\hline
b & 1650 & 936 & 714 & 222 & 48 & 30 & 18 & 12 & 6 \\
\hline
\text{reste} & 936 & 714 & 222 & 48 & 30 & 18 & 12 & 6 & 0 \\
\hline
\end{array}$$
IV.3 Définitions
$a$ et $b$ deux entiers naturels. On appelle plus grand commun diviseur de $a$ et de $b$ l'entier noté $pgcd(a,\ b)$ ou $a\wedge b$ qui vérifie $pgcd(a,\ b)$ divise $a\ $ et $\ b$ et si $d|a\ $ et $\ d|b$ alors $d\leq pgcd(a,\ b)$
$\centerdot\ \ $ il existe et il est unique
$\centerdot\ \ $ si $b|a$ alors, $pgcd(a,\ b)=b$
$\centerdot\ \ $ si $b$ ne divise pas $a$ alors, $pgcd(a, b)$ est le dernier reste non nul par l'algorithme d'Euclide.
IV.4 Propriétés
$a$, $\ b$ et $k$ sont des entiers naturels non nuls.
$\centerdot\ \ pgcd(a,\ 1)=1$
$\centerdot\ \ pgcd(a,\ a)=a$
$\centerdot\ \ pgcd(a,\ 0)=a$
$\centerdot\ \ pgcd(a,\ b)=pgcd(b,\ a)$
$\centerdot\ \ pgcd(ka,\ kb)=k\times pgcd(a,\ b)$
$\centerdot\ \ $ Si $k|a\ $ et $\ k|b$ alors, $pgcd(\frac{a}{k},\ \frac{b}{k})=\frac{1}{k}\times pgcd(a,\ b)$
$\centerdot\ \ $ Si $a$ est premier et $a$ ne divise pas $b$ alors, $pgcd(a,\ b)=1$
$\centerdot\ \ $ le $pgcd(a,\ b)$ ne change pas si on remplace l'un des nombres par la différence entre ce nombre et un multiple de l'autre. $a>b$, $\ pgcd(a,\ b)=pgcd(a-kb,\ b)$
$\centerdot\ \ pgcd(a_{1},\ a_{2},\ \ldots,\ a_{n})$ divise $a_{i}$ $\forall\;i$ et si $d|a_{i}$ $\forall\;i$ alors, $d\leq pgcd(a_{1}, a_{2},\ \ldots, a_{n})$
Théorème
Soient $a\ $ et $\ b$ deux entiers naturels non nuls et $d$ leur $pgcd.$
Il existe deux entiers relatifs $u\ $ et $\ v$ tels que $a.u+b.v=d$
Preuve :
Soit $E=\{n.a+m.b/n\in \mathbb{Z}\,\ $ et $\ m\in \mathbb{Z}\}$
$E\cap \mathbb{N^{*}}\neq \emptyset$ car $a\in E$ (prendre $n=1\ $ et $\ m=0$)
$E\cap \mathbb{N^{*}}$ étant une partie non vide de $\mathbb{N}$ possède un plus petit élément ; notons-le $d.$
Comme $d\in E$ il existe deux entiers naturels $u$ et $v$ tels que $d=a.u+b.v.$
$\bullet\ \ E$ contient clairement tous les multiples de $d$
$\bullet\ \ $ Réciproquement, soit $x$ un élément de $E\cap \mathbb{N^{*}}$ il existe deux entiers $q\ $ et $\ r$ tels que :
$x=dq+r$ avec $0\leq r<d$.
Alors, $r=x-dq$ d'où, $r\in E$ (différence de deux éléments de $E$)
Si $r$ était non nul, on aurait $r\in E\cap \mathbb{N^{*}}$ ; impossible car $r<d$ (plus petit élément de $E\cap \mathbb{N^{*}}$), donc $r=0$.
Par suite $x$ est un multiple de $d$
On a prouvé que $E\cap \mathbb{N^{*}}$ est l'ensemble des multiples de son plus petit élément $d$
Montrons que $d$ est le $PGCD$ de $a$ et de $b$.
soit $d'=a\wedge b$
$\bullet\ \ d'|a\ $ et $\ d'|b$ donc $d'|(a.u+b.v)$ donc $d'|d$.
$\bullet\ \ d|a\ $ et $\ d|b$ donc $d|d'$.
$d'|d\ $ et $\ d|d'$ donc $d=d'$
Exemple :
Déterminer deux entiers $u\ $ et $\ v$ tels que $25\,872u+484v=44$
Calculons le $pgcd(25\,872\;,\ 484)$
$\begin{array}{rcl} 25\,872 & = & 484\times 53+220 \\ \\ 484 & = & 220\times 2+44 \\ \\ 220 & = & 44\times 5+0 \end{array}$
Donc, $pgcd(25\,872\;,\ 484)=44$
On peu utiliser les calculs précédents pour écrire $44$ comme combinaison linéaire de $25\,872\ $ et $\ 484.$
$\begin{array}{rcl} 44 & = & 484-2\times 220 \\ \\ & = & 484-2.(25872-484\times 53) \\ \\ & = & 484\times(1+2\times 53)+25872\times(-2) \\ \\ & = & (-2)\times 25872+107\times 484\end{array}$
Donc, $u=-2\ $ et $\ v=107$
Exercices d'application :
Déterminer deux entiers $u\ $ et $\ v$ tels que $37\,236u+1650v=6\;;\ 160u+84v=4$
IV.5 Plus petit commun multiple (PPCM)
IV.5.1 Définitions
Soient $a\ $ et $\ b$ deux entiers naturels non nuls. Le plus petit commun multiple de $a$ et de $b$ est l'entier noté $ppcm(a,\ b)$ qui vérifie :
$\centerdot\ \ a|ppcm(a,\ b)\ $ et $\ b|ppcm(a,\ b)$
$\centerdot\ \ $ Si $d$ est un multiple commun à $a$ et à $b$ ; $\ a|d\ $ et $\ b|d$ $\Longrightarrow$ $ppcm(a,\ b)\leq d$
$\centerdot\ \ $ Si $a\ $ et $\ b$ sont deux entiers relatifs alors, on convient que $ppcm(a, b)=ppcm(|a|,\ |b|)$
IV.5.2 Propriétés
$a\;,\ b\ $ et $\ k$ sont des entiers naturels non nuls.
$\centerdot\ \ ppcm(a,\ b)=ppcm(b,\ a)$
$\centerdot\ \ ppcm(a,\ 1)=a$
$\centerdot\ \ $ Si $a$ divise $b$ alors, $ppcm(a,\ b)=b$
$\centerdot\ \ a|m$ et $b|m$ $\Leftrightarrow ppcm(a,\ b)|m$
$\centerdot\ \ ppcm(ka,\ kb)=k\times ppcm(a,\ b)$
$\centerdot\ \ $ Si $k|a$ et $k|b$ alors, $ppcm(\frac{a}{k},\ \frac{b}{k})=\frac{1}{k}\times ppcm(a,\ b)$
IV.5.3 Relation entre $ppcm(a,\ b)\ $ et $\ pgcd(a,\ b)$
Soient $a\ $ et $\ b$ des entiers naturels non nul. Alors, $pgcd(a,\ b)\times ppcm(a,\ b)=ab$
Preuve :
Posons $m=ppcm(a,\ b)\;,\ d=pgcd(a,\ b)$, $\ a'=\frac{a}{d}\ $ et $\ b'=\frac{b}{d}$. $\ a'\ $ et $\ b'$ sont premiers entre eux.
Remarquons que : $ab=d^{2}a'b'=d\times da'b'$
$\bullet\ \ da'b'=ab'=a'b$ donc $da'b'$ est multiple de $a$ et de $b$ d'où $m\leq da'b'$
$\bullet\ \ $ il existe des entiers naturels non nuls $p\ $ et $\ q$ tels que $m=pa\ $ et $\ m=qb$.
Comme $pa=qb$, on a $pa'=qb'$ (en divisant par $d$).
Par suite $b'|pa'\ $ et $\ pgcd(a'\;,\ b')=1$ donc $b'|p$ (théorème de Gauss).
Il existe un entier $k\geq 1$ tel que $p=kb'$.
On a donc : $m=kb'a=k(da'b')$, d'où $m\geq da'b'$
Conclusion :
$m=da'b'$ En multipliant par $d$, on obtient $md=da'db'=ab$ (c.q.f.d)
IV.6 Nombres premiers entre eux
IV.6.1 Définitions
$a\ $ et $\ b$ deux entiers naturels, $a\ $ et $\ b$ sont dits premiers entre eux si $$pgcd(a,\ b)=1$$
IV.6.2 Propriétés
$\centerdot\ \ $ Si $d=pgcd(a,\ b)$ $\Rightarrow$ $\dfrac{a}{d}\ $ et $\ \dfrac{b}{d}$ sont premiers entre eux
IV.7 Théorème de Bezout et Théorème de Gauss
IV.7.1 Théorème de Bezout
$a\ $ et $\ b$ sont premiers entre eux si et seulement si il existe $u\ $ et $\ v$ tels que $au+bv=1$.
Preuve :
$\bullet\ \ $ Si $pgcd(a,\ b)=1$ alors $1=a.u+b.v$ d'après ce qui précède avec $d=1$
$\bullet\ \ $ Si $a.u+b.v=1$ alors tout diviseur commun à $a$ et à $b$ divise $a.u+b.v=1$ donc $pgcd(a,\ b)|1$, d'où $pgcd(a,\ b)=1$
Remarques :
Les nombres $u\ $ et $\ v$ ne sont pas uniques. Par exemple, $2\ $ et $\ 3$ sont premiers entre eux.
En effet, $3\times 1+2\times (-1)=1$ ou $3\times (-5)+2\times 8=1.$
IV.7.2 Théorème de Gauss
$a\;,\ b\ $ et $\ c$ trois entiers naturels. Si $a$ divise le produit $b.c$ et si $a$ est premier avec $b$, alors $a$ divise $c.$
Preuve :
$a$ divise $b.c$ donc il existe un entier $k$ tel que $b.c=k.a$
De plus d'après le théorème de Bézout, $a\ $ et $\ b$ étant premiers entre eux, il existe deux entiers $u\ $ et $\ v$ tels que $a.u+b.v=1$ ; en multipliant par $c$ on obtient $a.u.c+b.c.v=c$ puis $c=a.u.c+k.a.v$ soit $c=a.(u.c+k.v)$ d'où $a$ divise $c.$
IV.8 Equations diophantiennes
Exemple de résolution dans $\mathbb{Z}^{2}$ de $ax+by=d$ avec $d=pgcd(a,\ b)$
Un exemple :
Soit à résoudre dans $\mathbb{Z}^{2}$, l'équation $9x+6y=15$ $(E)$
$\bullet\ \ $ s'il existe une solution, $15$ est une combinaison linéaire de $9$ et de $6$ donc leur $PGCD$ divise $15.$
Or, $pgcd(9\;,\ 6)=3$ et $15=3\times 5$ donc, l'équation $(E)$ est équivalente à l'équation $(E')\ $ : $3x+2y=5$ où $3$ et $2$ premiers entre eux.
D'après le théorème de Bézout, il existe $u\ $ et $\ v$ tels que $3.u+2.v=1$.
Par exemple $u=3\ $ et $\ v=-4$ (les coefficients de Bézout ne sont pas uniques)
On obtient une solution particulière de $(E)$ en multipliant $u$ et $v$ par $5$ :
$x_{0}=5\times 3=15\ $ et $\ y_{0}=5\times (-4)=(-20)$ (on vérifie que $9\times 15+6\times (-20)=15$
Existe-t-il d'autres solutions ?
$\bullet\ \ $ si $(x,\ y)$ est un couple de solutions de $(E)$, on a $9x+6y=15$ or, $\ 9x_{0}+6y_{0}15$
Après soustraction membre à membre et simplification on obtient :
$3.(x-x_{0})=2.(y-y_{0})$
Donc, $2$ divise $3.(x-x_{0})$ et puisque $2$ et $3$ sont premiers entre eux, $2$ divise $(x-x_{0})$ (théorème de Gauss)
Il existe $k$ tel que $x=x_{0}+2.k$.
Si bien que $3.2k=2.(y_{0}-y)$, par suite $y=y_{0}-3.k$
$\bullet\ \ $ D'autre part, on vérifie immédiatement, que pour tout $k$ de $\mathbb{Z}$, le couple $(x,\ y)$ tels que $x=15+2.k\ $ et $\ y=-20-3.k$ où $k$ est un entier relatif.
Remarques :
Notons $d=pgcd(a,\ b)$
On considère l'équation $ax+by=c$.
Si $d$ ne divise pas $c$ alors, l'équation n'admet pas de solution.
Si $d$ divise $c$ alors, on simplifie par $d$ et on obtient une équation du type $a'x+b'y=c'$ avec $a'$ et $b'$ premiers entre eux.
V Congruence
V.1 Définitions
Lorsque deux entiers relatifs $a$ et $b$ ont le même reste dans la division euclidienne par un entier naturel $n$ non nul, on dit qu'ils sont congrus modulo $n$ et on note $a\equiv b\mod n$ ou $a\equiv b(n)\ $ $(a-b=kn).$
V.2 Propriétés
$\centerdot\ \ $ Soient $a\ $ et $\ b$ deux entiers et $n$ un entier naturel non nul.
Alors $a\ $ et $\ b$ ont le même reste dans la division euclidienne par $n$ si et seulement si $a-b$ est multiple de $n$.
Preuve :
$a=nk+r$, avec $0\leq r<n$ $b=nk'+r'$, avec $0\leq r'<n$ par différence on obtient :
$a-b=n(k-k')+(r-r')$, avec $-n<r-r'<n$
$\centerdot\ \ $ si $r=r'$ alors, $a-b$ est multiple de $n$.
$\centerdot\ \ $ si $a-b$ est multiple de $n$ alors, $r-r'$ est un multiple de $n$, or $-n<r-r'<n$ donc $r-r'=0$, soit $r=r'$.
$\centerdot\ \ a\equiv a(n)\ $ $0=0*n$ donc, $\equiv$ est réflexive
$\centerdot\ \ a\equiv b(n)$ $\Rightarrow$ $b\equiv a(n)$ donc, $\equiv$ est réflexive et symétrique
$\centerdot\ \ a\equiv b(n)\ $ et $\ b\equiv c(n)$ alors $a\equiv c(n)$ donc, $\equiv$ est transitive
Ainsi, $\equiv$ est une relation d'équivalence
En effet, $a\equiv b(n)$ $\Leftrightarrow$ $a-b=kn$ et $b\equiv c(n)$ $\Leftrightarrow$ $b-c=k'n$, ce qui donne $a-b+b-c=kn+k'n$ $\Rightarrow$ $a-c=n(k+k')=np$ et donc, $a\equiv c(n)$
$\centerdot\ \ a\equiv b(n)\ $ et $\ a'\equiv b'(n)$ $\Rightarrow$ $a+a'\equiv b+b'(n)$
$\centerdot\ \ a\equiv b(n)\ $ et $\ a'\equiv b'(n)$ $\Rightarrow$ $aa'\equiv bb'(n)$
$\centerdot\ \ a\equiv b(n)$ $\Rightarrow$ $a^{k}\equiv b^{k}(n)$
$\centerdot\ \ a\equiv b(n)$ $\Rightarrow$ $ka\equiv kb(n)$
V.3 Théorème de Fermat
Soient $n$ un entier naturel et $p$ un nombre premier, alors $n^{p}\equiv n(p)$.
Si de plus $p$ ne divise pas $n$ alors on a : $n^{p-1}\equiv 1(p)$
VI. Système de numération
Soit $b$ un entier naturel fixé ($b\geq 2$.
Par suite de l'unicité du quotient et du reste dans la division euclidienne, tout entier naturel $a$ s'écrit d'une manière et d'une seule sous la forme :
$$a=a_{n}b^{n}+a_{n-1}b^{n-1}+\ldots +a_{1}b+a_{0}$$
où $a_{0}, a_{1}, \ldots a_{n}$ sont des entiers naturels strictement inférieurs à $b$ et où $a_{n}$ est non nul.
On dit alors que l'écriture $\overline{a_{n}a_{n-1}\ldots a_{0}}^{b}$ est l'écriture de $a$ en base $b$, et on exprime pratiquement chaque nombre $a_{i}$ par un symbole (ou chiffre) d'une liste donnée de $b$ symboles.
Plus généralement, lorsque aucune confusion n'est possible, on omet l'indication de la base, et on écrit $\overline{a_{n}a_{n-1}\ldots a_{0}}$ et même sans surligner $a_{n}a_{n-1}\ldots a_{0}$.
Le système décimal est le système de numérotation de position où la base est dix.
Le système binaire est le système de numérotation de position où la base est deux :
L'alphabet est composé des deux seuls chiffres $0\ $ et $\ 1.$
Ce système est très utilisé, car les machines à deux états (machines électriques ou électroniques, par exemple) peuvent réaliser une représentation des nombres entiers par leur désignation binaire, les deux états de la machine étant, dans le code, la traduction du $0$ et du $1.$
Lorsque la base est supérieure à dix, il est nécessaire d'adjoindre aux chiffres habituels de nouveaux symboles.
Dans un système de numération à base $b$ on utilise les chiffres $0\;,\ 1\;,\ 2\;,\ ....,\ b-1$
Exemple :
En base $10$ on utilise $0\;,\ 1\;,\ 2\;, ....,\;9\;,$
$948=9*10^{2}+4*10^{1}+8*10^{0}\;,\quad 91455=9*10^{4}+1*10^{3}+4*10^{2}+5*10^{1}+5*10^{0}$
En base $2$ on utilise $0$ et $1$
En base $6$ on utilise $0\;,\ 1\;,\ 2\;,\ 3\;,\ 4\;,\ 5$
En base $12$ on utilise $0\;,\ 1\;,\ 2\;, ....,\;9\;,\ \alpha\;,\ \beta$.
En base $b$, $\ x=2*b^{3}+3*b^{2}+4*b+5$ s'écrit $x=\overline{2345}^{b}$
En effet, on a $\overline{2345}^{b}=2*b^{3}+3*b^{2}+4*b^{1}+5*b^{0}=2*b^{3}+3*b^{2}+4*b+5=x$.
En base $2$, on a $\overline{1011}^{2}=1*2^{3}+0*2^{2}+1*2+1=11$
VII. Des critères de divisibilité
Divisibilité par 3
Exemple :
$456=4\times 10^{2}+5\times 10+6$
Or, $10=3\times 3+1$ ; $10^{2}=3\times 33+1$
Donc, $456=4\times(3\times 33+1)+5\times(3\times 3+1)+6$
$456=4+5+6+(4\times 3\times 33+5\times 3\times 3)$
$456=15+3\times(4\times 33+5\times 3)$
Par suite, $456$ est divisible par $3$ car $15$ est divisible par 3 et réciproquement.
$n=\overline{a_{n}a_{n-1}\ldots a_{1}a_{0}}=a_{0}+a_{1}\times 10+\ldots +a_{n-1}\times 10^{n-1}+a_{n}\times 10^{n}$
On a : $10\equiv 1\bmod 3$ donc $10^{k}\equiv 1\bmod 3$ pour tout entier $k$.
Par suite : $n\equiv a_{n}+a_{n-1}+\ldots +a_{1}+a_{0}\bmod 3$
$n$ et $a_{n}+a_{n-1}+\ldots +a_{1}+a_{0}$ ont le même reste dans la division par $3.$
En particulier :
$n$ est divisible par $3$ si et seulement si $a_{n}+a_{n-1}+\ldots +a_{1}+a_{0}$ est divisible par $3.$
Auteur:
Diny Faye & Seyni Ndiaye
Commentaires
mr farid (non vérifié)
lun, 02/10/2020 - 18:39
Permalien
C omment en peut telecharger
YOUSSOUF Traoré (non vérifié)
mar, 11/09/2021 - 14:50
Permalien
Cette leçon c'est l'une de
Anonyme (non vérifié)
sam, 12/25/2021 - 01:34
Permalien
Cette leçon est très
Anonyme (non vérifié)
sam, 12/25/2021 - 01:34
Permalien
Cette leçon est très
Anonyme (non vérifié)
sam, 12/25/2021 - 01:34
Permalien
Cette leçon est très
Ajouter un commentaire