Vous êtes ici

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)$ ).

$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$ :

$n$ est divisible par

$2$ ,

$n$ n'est pas premier et c'est fini.

Sinon, on divise par

$3.$

$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}$

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$ )

$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$ .

$d$ ne divise pas

$c$ alors, l'équation n'admet pas de solution.

$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

C omment en peut telecharger voss cours? merci

répondre

YOUSSOUF Traoré (non vérifié)

mar, 11/09/2021 - 14:50

Permalien

Cette leçon c'est l'une de

Cette leçon c'est l'une de leçon qu'est spécial à tse

répondre

Anonyme (non vérifié)

sam, 12/25/2021 - 01:34

Permalien

Cette leçon est très

Cette leçon est très intéressante

répondre

Anonyme (non vérifié)

sam, 12/25/2021 - 01:34

Permalien

Cette leçon est très

Cette leçon est très intéressante

répondre

Anonyme (non vérifié)

sam, 12/25/2021 - 01:34

Permalien

Cette leçon est très

Cette leçon est très intéressante

répondre

Ajouter un commentaire

form.antibot { display: none !important; } You must have JavaScript enabled to use this form.

Vous êtes ici

Arithmétique - T S1

Formulaire de recherche

Introduction

I. Rappels

Exemple :

Exemple :

Les trois axiomes fondamentaux

II. Diviseurs et multiples d'un entier

II.1 Définitions

II.2 Propriétés

III. Les nombres premiers

III.1 Définitions

Exemple :

III.2 Propriétés

Exemple :

III.3 Décomposition en produits de facteurs premiers

Exemple :

IV. Plus grand et commun diviseur - Plus petit commun multiple

IV.1 Division euclidienne

Remarques :

IV.2 Algorithme d'Euclide

Exemple :

IV.3 Définitions

IV.4 Propriétés

Théorème

Preuve :

Exemple :

Exercices d'application :

IV.5 Plus petit commun multiple (PPCM)

IV.5.1 Définitions

IV.5.2 Propriétés

IV.5.3 Relation entre ppcm(a, b) ppcm(a,\ b)\ et pgcd(a, b)\ pgcd(a,\ b)

Preuve :

Conclusion :

IV.6 Nombres premiers entre eux

IV.6.1 Définitions

IV.6.2 Propriétés

IV.7 Théorème de Bezout et Théorème de Gauss

IV.7.1 Théorème de Bezout

Preuve :

Remarques :

IV.7.2 Théorème de Gauss

Preuve :

IV.8 Equations diophantiennes

Un exemple :

Remarques :

V Congruence

V.1 Définitions

V.2 Propriétés

Preuve :

V.3 Théorème de Fermat

VI. Système de numération

Exemple :

VII. Des critères de divisibilité

Divisibilité par 3

Exemple :

En particulier :

Commentaires

C omment en peut telecharger

Cette leçon c'est l'une de

Cette leçon est très

Cette leçon est très

Cette leçon est très

Ajouter un commentaire

Plain text

IV.5.3 Relation entre $ppcm(a,\ b)\$ et $\ pgcd(a,\ b)$