Partager |

Arithmétique : Divisibilité et congruences

Objectifs de ce chapitre

savoir ce qu'est un diviseur, un multiple
connaître les propriétés élémentaires de la relation de divisibilité
connaître la formule et le vocabulaire de la division euclidienne dans
connaître la définition de la congruence modulo n
connaître les propriétés de la congruence dans
savoir utiliser les congruences pour montrer qu'un entier est divisible par un autre entier
savoir utiliser les congruences pour déterminer le reste d'une division euclidienne

Définition

Soient et deux entiers relatifs tels qu'il existe un entier relatif tel que a=bk .
On dit alors que :

divise
est un diviseur de
est un multiple de

Ceci se note b|a

Exemple

15=3*5 donc :

3 divise 15
3 est un diviseur de 15
15 est un multiple de 3

Remarques

0 est un multiple de tout entier relatif
1 et -1 sont des diviseurs de tout entier relatif
et ont les mêmes diviseurs

Propriétés

Si divise et divise , alors et sont égaux ou opposés
Si divise et divise , alors divise
Si divise et divise , alors divise toute combinaison linéaire de et (c'est-à-dire tout nombre de la forme )

Théorème et définitions

Division euclidienne dans
Soient et deux entiers relatifs avec b!=0 .
Il existe un et un seul couple d'entiers relatifs (q,r) tels que :
a = bq + r et 0 <= r < |b|
et s'appelle respectivement le quotient et le reste de la division euclidienne de par .

Exemple

-14 = 3(-5)+1 et 013
La division euclidienne de -14 par 3 donne un quotient de -5 est un reste de 1.

Remarques

Attention ! Ne pas oublier la condition . La seule égalité ne suffit pas à prouver que et sont les quotient et reste dans la division euclidienne de par
est divisible par si et seulement si le reste de la division de par est égal à zéro

Définition

On dit que deux entiers relatifs et son congrus modulo ( n in NN^star ) et l'on écrit a==b..[n] si et seulement si et ont le même reste dans la division par

Exemple

18==23..[5] car 18 et 23 ont tous les deux 3 comme reste dans la division par 5

Propriétés

si et seulement si divise en particulier si et seulement si divise
si et , alors

Propriétés

Congruences et opérations

Soient quatre entiers relatifs a, b, c, d tels que a==b..[n] et c==d..[n] . Alors :

et
pour tout entier relatif
pour tout entier naturel

Propriété

et le reste de la division euclidienne de par si et seulement si :
syst(r==a..<strong>;0 <= r < |b|)

Exemple

On cherche à déterminer le reste de la division euclidienne de 2009^2009 par 5.
2009==-1..[5] car 2009-(-1)=2010 est divisible par 5.
Donc :
2009^2009==(-1)^2009..[5] c'est-à-dire 2009^2009==-1..[5]
Or -1==4..[5] donc 2009^2009==4..[5]
Comme 0<=4<5 , le reste de la division euclidienne de par 5 est 4.