Annale – Divisibilité, congruence

Le symbole sigma

Le symbole Sigma $LargeSigma$ permet de désigner la somme d’une famille finie de termes. 

 

Par exemple $ sumlimits_{k = p}^q U_k=U_p + U_{p + 1} + … + U_q$.

En effet, ici on souhaite calculer la somme des $U_k$ où $k$ est l’indice de sommation, pour $k$ variant de $p$ à $q$, avec $p, q in mathbb{N}$ et $p leq q$.

 

Considérons un exemple concret : $ sumlimits_{i = 1}^5 3^i$ qui se lit somme de $3^i$ pour $i$ variant de 1 à 5

$ sumlimits_{i = 1}^5 3^i=3^1 + 3^2 + 3^3 + 3^4 + 3^5$.

$ sumlimits_{i = 1}^5 3^i=3+9+27+81+243=363$

 

On remarquera que l’indice de sommation est muet, il n’intervient pas dans le résultat final : on peut donc prendre la lettre que l’on souhaite ($k, i, …$). 

Ainsi, $ sumlimits_{i = 1}^5 3^i= sumlimits_{k = 1}^5 3^k=  sumlimits_{j = 1}^5 3^j$

 

Autre exemple :

$ sumlimits_{i = 0}^3 2i-1= (2times 0 -1)+(2times 1 -1)+(2times 2 -1)+(2times 3 -1)$

$ sumlimits_{i = 0}^3 2i-1=-1+1+3+5=8$

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 $aequiv b[n]$.

Propriétés 

 

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

$aequiv a[n].$

Si $aequiv b[n]$ et $bequiv 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 $acequiv bc[n]$.

Si $a equiv b[n]$ alors $a^pequiv 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 = 11times 17$ donc $200$ est congru à $13$ modulo $17$.

On note $200equiv 13[17]$

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

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

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

Or la congruence est compatible avec les puissances. Ainsi :

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

$200^2equiv 169 [17]$

On donne la division euclidienne de $169$ par $17$ : $169 = 9times 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 $0leqslant 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=82times 9+15$.

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