L’incontournable du chapitre

Congruences

Congruences dans $\mathbb{Z}$

 

Définition

 

Soit un entier $n$ supérieur à 2 et soient $a$ et $b$, deux entiers relatifs.

On dit que $a$ est congru à $b$ modulo $n$ si et seulement si $b-a$ est divisible par $n$.

On écrit $a\equiv b[n]$.

Propriétés 

 

Soient $a$, $b$ et $c$ des entiers relatifs, $n$ et $p$ des entiers supérieurs ou égaux à 2 :

$a\equiv a[n].$

Si $a\equiv b[n]$ et $b\equiv c [n]$ alors $a \equiv c[n]$.

Si $a \equiv b[n]$ alors $a+c \equiv b+c[n]$.

Si $a \equiv b[n]$ alors $ac\equiv bc[n]$.

Si $a \equiv b[n]$ alors $a^p\equiv b^p[n]$.

Exemple

Trouver le reste de la division euclidienne de $200^{539}$ par 17

 

étape 1 : On pose la division euclidienne de 200 par 17.

$200= 11 \times 17 +13$

étape 2 : On utilise la définition de la congruence.

$200-13 = 11\times 17$ donc $200$ est congru à $13$ modulo $17$.

On note $200\equiv 13[17]$

étape 3 : Avec un peu d’astuce, et en remarquant que $539 = 269\times 2 +1$, on a :

$200^{539}= (200^2)^{269} \times 200$

On sait que $200\equiv 13[17]$ .

Or la congruence est compatible avec les puissances. Ainsi :

$200^2\equiv 13^2[17]$

$200^2\equiv 169 [17]$

On donne la division euclidienne de $169$ par $17$ : $169 = 9\times 17 +16$. Ainsi :

$200^2 \equiv 16 [17]$

Ou encore $200^2 \equiv (-1) [17]$.

étape 4 : On utilise les résultats précédents et on essaie d’aboutir à une congruence positive.

On a : $200^2 \equiv (-1) [17]$ et $539 = 2 \times 269 +1$.

Ainsi $200^{539}=(200^2)^{269}\times 200$ et en utilisant les résultats précédents :

$200^{539} \equiv(-1)^{269} \times 13 [17]$

$200^{539} \equiv(-1) \times 13 [17]$

$200^{539} \equiv -13 [17]$

$200^{539} \equiv 4 [17]$

Conclusion : Le reste de la division euclidienne de $200^{539}$ par 17 vaut 4

Divisibilité et division euclidienne

Divisibilité et division euclidienne

 

Divisibilité dans $\mathbb{Z}$

 

Définition

Soient $a$ et $b$, deux entiers relatifs, avec $b$ non nul.

On dit que $b$ divise $a$ si et seulement si il existe un entier relatif $k$ tel que $a=kb$.

On note $b|a$.

 

Propriétés

Pour $a$ non nul, $a|a$.

Pour $a$, $b$ et $c$ non nuls, si $a|b$ et $b|c$ alors $a|c$.

 

Exemple

Montrer que $N=a(a^2-1)$ est divisible par 6 lorsque $a \in \mathbb{N}$.

 

étape 1 : $N$ est divisible par 6 si et seulement si il est divisible par 2 et par 3.

étape 2 : On réécrit $N$ grâce à une identité remarquable pour faire apparaître un produit de trois nombres consécutifs.

$N=a(a^2-1)$

$N=a(a-1)(a+1)$

$N=(a-1)a(a+1)$

étape 3 : Si $a$ est pair, on remplace $a$ par $2k$ ($k \in \mathbb{N}$).

$N=(2k-1)2k(2k+1)$

étape 4 : $N$ s’écrit sous la forme d’un produit d’un entier et de 2, donc $N$ est pair.

étape 5 : Si $a$ est impair, on remplace $a$ par $2k+1$.

$N=(2k+1)2k(2k+2)$

On arrive à la mÍme conclusion et $N$ est donc divisible par 2 dans tous les cas ($a$ pair ou impair).

étape 6 : Si $a$ est multiple de 3, alors $a=3k$. On remplace $a$ par $3k$.

$N=(3k-1)3k(3k+1)$ On en conclut que $N$ est multiple de 3.

étape 7 : On répËte la mÍme opération avec $a=3k+1$ puis avec $a=3k+2$.

Dans ces deux cas, on verra apparaître un multiple de 3. On en conclut que $N$ est divisible par 3.

$N$ est divisible par 2 et 3 donc $N$ est divisble par 6.

 

Division euclidienne dans $\mathbb{Z}$

 

Définition

Soient $a$ et $b$, deux entiers naturels et $b$ non nul.

Effectuer la division euclidienne de $a$ par $b$ revient à déterminer l’unique couple $(q;r)$ d’entiers naturels tels que :

$a=bq+r$ avec $0\leqslant r<b$.

On nomme $q$ le quotient et $r$ le reste.

Exemple

Déterminer le quotient $q$ et le reste $r$ de la division euclidienne de 753 par 82.

 

On a : $753=82\times 9+15$.

On obtient donc : $q=9$ et $r=15$. On vérifie que 15 est strictement inférieur à 82

 

Les nombres premiers

Les nombres premiers

 

Définition

Soit $n$ un nombre entier supérieur ou égal à 2.

$n$ est premier si et seulement si $n$ admet deux diviseurs : 1 et lui-même.

 

Théorème

Tout $n\in \mathbb{N}$ avec $n\geq 2$ admet au moins un diviseur premier.

Si $n$ n’est pas premier et $n\geq 2$ alors il admet un diviseur premier compris entre 2 et $\sqrt{n}$

 

Décomposition en facteurs premiers

 

Théorème

Tout entier naturel $n$ supérieur ou égal à 2 se décompose en produit de nombres premiers.

Cette décomposition est unique à l’ordre près des facteurs.

$\;n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times ……… p_r^{\alpha_r}\;$   

Avec  ${p_i}, {i \in \{1;r\}}$ sont des nombres premiers distincts et $\alpha_i, {i \in \{1;r\}}$ des entiers.

 

Exemple

On décompose 96 en produit de facteurs premiers :

étape 1 : On cherche à diviser 96 par un nombre premier.

étape 2 : On commence par le plus simple, à savoir 2.

étape 3 : On continue tant qu’on peut diviser par 2 ou par les entiers premiers suivants.

étape 4 : On s’arrête lorsque le reste vaut 1.

étape 5 : On peut donc réécrire 96 comme une décomposition de facteurs premiers :

$96=2^5 \times 3$

PPCM - PGCD

PGCD et PPCM

 

Définition

Soient \(a\) et \(b\), deux entiers naturels supérieurs ou égaux à 2. On suppose que :

\(a = p_1^{\alpha_1} \times p_2^{\alpha_2} \times … \times p_n^{\alpha_n}\)

\(b = p_1^{\beta_1} \times p_2^{\beta_2} \times … \times p_n^{\beta_n}\)

On note \(m = min (\alpha_i : \beta_i)\) avec \(i\) entier naturel non nul.

\(M = max (\alpha_i : \beta_i)\)

Le PGCD de deux entiers est le plus grand diviseur commun de ces deux entiers.

Le PPCM de deux entiers est le plus petit commun multiple de ces deux entiers.

 

On a : 

\(PGCD (a ; b) = p_1^{m_1} \times p_2^{m_2} \times … \times p_n^{m_n}\)

\(PPCM (a ; b) = p_1^{M_1} \times p_2^{M_2} \times … \times p_n^{M_n}\)

 

Propriétés du PGCD

 

Soit $a$, $b$ et $r$ entiers non nuls.

1) $PGCD(a;b)\geq 1$

2) $PGCD(a;b) = PGCD(b;a)$

3) $PGCD(a;a)=\vert a\vert$

4) $PGCD(a;b) =PGCD(-a;b) =PGCD(a;-b)$

5) Si $b\mid a$, $PGCD(a;b)=\vert b \vert$

6) Si $a=bq+r$ alors, $PGCD(a;b) =PGCD(b;r)$

Théorèmes de Bezout - Gauss

Théorèmes de Bezout et Gauss

Définition

Deux entiers sont premiers entre eux lorsque leur PGCD vaut $1$.

 

Théorème de Bezout

Soient $a$ et $b$, deux entiers naturels non nuls.

Si on note $d=PGCD(a;b)$, alors il existe 2 entiers relatifs $u$ et $v$ tels que :

$au+bv=d$

$a$ et $b$ sont premiers entre eux si et seulement si :

$au+bv=1$.

Exemple

Montrer que (2n + 1) et (3n + 2) sont premiers entre eux $\forall n \in \mathbb{N}$.

 

Il s’agit de trouver des coefficients $u$ et $v$ pour que

$u(2n + 1) + v(3n + 2) = 1$.

On choisit astucieusement $u$ et $v$ pour faire disparaître les termes en $n$.

$-3(2n + 1) + 2(3n + 2) = -6n – 3 + 6n + 4 = 1$

$\forall n \in \mathbb{N}$, il existe $u = -3$ et $v = 2$ tel que

$u(2n + 1) + v(3n + 2) = 1$.

Les entiers $(2n + 1)$ et $(3n + 2)$ sont donc premiers entre eux.

 

Théorème de Gauss

Soient $a$, $b$ et $c$, trois entiers relatifs non nuls.

Si $a$ divise $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.

 

Exemple 

Trouver (s’ils existent) les couples $(x;y)$ d’entiers solutions de l’équation : $5(x – 1) = 7y$.

5 divise $7y$, or $PGCD(5;7) = 1$, donc d’après le théorème de Gauss, 5 divise $y$.

Il existe donc un entier $k$ tel que : $y = 5k$.

En remplaçant dans l’équation, on a :

$5(x – 1) = 7 \times  5k \iff x – 1 = 7k \iff x = 7k + 1$

Les solutions sont donc de la forme :   $x=7k + 1$ et $y=5k$

On les note $S=\left\{(7k+1 ; 5k) ; k\in \mathbb{Z}\right\}$.

Équations diophantiennes

Equation Diophantienne

 

Définition

Une équation diophantienne est une équation algébrique de la forme $ax+by=c$ (E) avec $a$, $b$ et $c$ entiers ($a$ et $b$ non nuls).

On cherche des couples $(x;y)$ d’entiers solutions.

Existence de solutions

(E) admet des solutions $\iff$ $PGCD(a,b)$ divise $c$

Dans l’équation suivante : (E) $4x-2y=1$, on a :

$PGCD(4;2)=2$ 

Or, 2 ne divise pas 1 donc l’équation n’a pas de solutions.

 

Exemple

Résoudre $41x-27y=1$   (E) dans $\mathbb{Z}^2$.

 

étape 1 : On cherche le $PGCD$ des nombres du membre de gauche. On effectue l’algorithme d’Euclide.

$41=27 \times 1 + 14 $

$27= 14 \times 1 + 13$

$14= 13 \times 1 + 1$ 

Ainsi : $PGCD (41 ; 27)=1$.

41 et 27 sont premiers entre eux.

 

étape 2 : On vérifie que le $PGCD (41 ; 27)$ divise le membre de droite, soit 1.

L’équation (E) admet donc des solutions.

 

étape 3 : On cherche une solution particulière.

$41=27 \times 1 + 14 $

$27= 14 \times 1 + 13$

$14= 13 \times 1 + 1$

On multiplie les deux membres de la première égalité par 2 et on remonte l’algorithme d’Euclide:

$13=14-1$ dans la deuxième égalité

$41=27 \times 1 + 14 \times 2$

$27= 14 \times 1 + 14-1$ car $13=14-1$

On a:

$41 \times 2 =27 \times 2 + 14 \times 2 $

$27= 14 \times 1 + 14-1$

On a ainsi:

$41 \times 2 =27 \times 2 + 14 \times 2$

$27 +1= 14 \times 2 $ et :

$41 \times 2 =27 \times 2 + 27 +1$

$41 \times 2 =27 \times 3 +1$

On déduit:

$41 \times 2 -27 \times 3 =1$

On repère ici une solution particulière de l’équation : le couple $(2 ; 3)$.

 

étape 4 : On cherche à présent l’ensemble des solutions de l’équation.

On sait que $41x-27y=1$ et que $41 \times 2 -27 \times 3 =1$.

On en déduit que $41x-27y=41 \times 2 -27 \times 3 $ et que $41(x-2)=27(y-3)$.

On note que $41$ divise $27(y-3)$ et que $27$ divise $41(x-2)$.

Comme $41$ et $27$ sont premiers entre eux, d’après le théorème de Gauss :

$41$ divise $(y-3)$ et $27$ divise $(x-2)$.

Il existe donc deux entiers $k$ et $k’$ tels que :

$y-3 = 41k$ et $x-2= 27k’$.

En effectuant un travail sur la réciproque de l’existence de ces solutions, on montre que $k=k’$.

Conclusion : L’ensemble des couples $(x;y)$ solutions de l’équation \textit{(E)} sont de la forme :

$S=\left(27k+2;41k+3\right)$ avec $k$ entier.

Tu veux réviser 2x plus vite ?

Découvre les offres des Bons Profs avec :