Congruences

Cours maths Terminale S

Congruences :
Dans ce module, étude de la notion de congruence.
La congruence modulo n de deux entiers relatifs est tout d’abord définie,
ensuite la notion de classe et de représentant d’une classe, modulo n. Le cours de termine par le petit théorème de Fermat et son corollaire.
► Sommaire cours maths Terminale S

      A voir aussi :


► Sommaire par thèmes
► Sommaire par notions
 

1/ Division euclidienne
Division euclidienne dans :
Soient a  et b *
Il existe un unique couple ( q , r ) d’entiers naturels tels que :
a = b x q + r  avec   0 < r < b

q est le quotient, r le reste, b le diviseur et a le dividende.

Propriété :
« b divise a » si et seulement si «  le reste de la division euclidienne de a par b est nul ».
Division euclidienne dans :
Soient a et b *
Il existe un unique couple ( q , r ) d’entiers realtifs tels que :
a = b x q + r  avec   0 < r < lbl

Remarques :
1) si a et b sont des naturels, le couple obtenu dans les deux divisions est le même
2) dans tous les cas, r est un entier naturel


2/ Congruence : définition

Définition :
soient a et b deux entiers relatifs et n entier naturel, n > 2

On dit que « a est congru à b modulo n » ou que « a et b sont congrus modulo n » si :
a et b ont le même reste dans la division euclidienne par n.
On note

Remarques :
1) On dit aussi que a et b sont égaux modulo n.

2) La congruence modulo 1 ne présente aucun intérêt car dans la division e0uclidienne par 1, tout nombre a pour reste 0. Et donc deux nombres  quelconques sont égaux modulo 1.

3) Cette notion de congruence a déjà été rencontrée en trigonométrie, où l’on
       parle d’angles égaux modulo


De part sa définition, la relation de congruence présente trois propriétés évidentes :
a[n] (réflexivité)
Si a b[n]  alors  b a[n] (symétrie)
Si a b[n]  et b c[n] (transivité)
Exemple :
5 et 14 sont-ils congrus modulo 3 ?
Leurs divisions euclidiennes par 3 sont : 5 = 3 x 1 + 2          14 = 3
x 4 + 2
5 et 14 ont le même reste dans la division euclidienne par 3 donc : 5
14 [3]
congruence
Si on ajoute 3 à 5 alors la division euclidienne devient :
5 + 3 = 3 x 1 + 2 +3
8 = 3 x (1+1) + 2
Le reste de la division est inchangé donc 8 5[3]
Et l’on peut faire pareil avec le nombre trouvé.

Le résultat est également le même si au lieu d’ajouter 3, on enlève 3.

Comme tous ces nombres sont congrus à 5 modulo 3, par tansitivité,
ils sont congrus deux à deux modulo 3.

On peut remarquer que la différence entre deux de ces nombres est un multiple de 3.

Etendons cette remarque au cas général :
3/ Congruence : équivalence

Propriété :
soient a et b deux entiers relatifs et n entier naturel, 
n > 2
a b [n]   ⇔  n divise (a-b)
Démonstration :
Sens direct :
Soient a et b congrus modulo n.
Il existe q et r entiers relatifs tels que :  a = n x q + r  avec  0 < r < n
b ayant le même reste, il existe q’ entier relatif tel que : b =  n x q' + r

D'où a - b = n
x q - nq' = n x (q - q')
Donc n divise (a-b)

Sens réciproque :
Supposons que n divise (a-b). Alors il existe k entier relatif tel que : a-b = nk.

Soit r le reste dans la division euclidienne de a par n :

a = n x q + r avec  0 < r < n

Alors : b = a - nk = n x (q - k) + r

Avec 0 < r < n  et q-k entier relatif
donc r est le reste dans la division euclidienne de b par n.

a et b ont le même reste donc : a
b[n]

Remarque :
Pour montrer que deux nombres sont congrus modulo n, il suffira donc de montrer que leur différence est un multiple de n.

Conséquences :
a0[n] ⇔ n divise a
Remarque :
en particulier, n divise n et n divise 0 donc : n
0[n]  et 00[n]
ab[n] n divise (a-b) ⇔ a - b 0[n]

Quel que soit d entier naturel supérieur ou égal à 2 :
Si ab[n]  et d divise n alors ab[d]


Démonstration :
donc n divise (a-b) Or par transitivité : si d divise n alors d divise (a-b).
Par conséquent : ab[d]
4/ Congruence : restes et classes

En trigonométrie où il est question d’angles égaux modulo
, on parle de mesure principale,
comprise par exemple entre 0 et
exclu.
Cette idée de choisir un représentant pour un ensemble de nombres égaux modulo
est transposable au cas modulo n.

Propriété :
soient a entier relatif et n entier naturel, n > 2
Si r est le reste dans la division euclidienne de a par n alors ar[n]

Démonstration
:
En effet, si r est le reste dans la division euclidienne de a par n alors
il existe q entier relatif tel que : a = n x q + r  avec  0 < r < n
Donc n divise (a-r) et par conséquent a est congru à r modulo n.

Propriété réciproque
:
soient a entier relatif et n entier naturel,          .
Si a r[n] et 0 < r < n alors r est le reste dans la division euclidienne de a par n.
Démonstration :
Si a et r sont congrus modulo n alors n divise (a-r) et il existe donc k entier relatif tel que : a - r = n x 
D'où  a = n x k + r 
Or 0 < r < n
Donc il s’agit de la division euclidienne de a par n et r en est le reste.

Si 
a r[n] et 0 < r < n   alors r est le reste dans la division euclidienne de a par n.
Donc par unicité de la division euclidienne, chaque entier a ne peut être congru qu’à un seul entier
compris entre 0 et n exclu.

Cet entier étant le reste dans la division euclidienne de a par n.


Chacun des restes possibles dans la division euclidienne par n peut donc être considéré comme

le représentant d’un ensemble de nombres qui lui sont congrus modulo n.
Les restes possibles étant : 0, 1, …, n-1;   peut donc être découpé en n classes, modulo n.
Ces classes forment une partition de .
C’est à dire que leur union est égale à , et que leurs intersections, deux à deux, sont vides.
Exemple :
Considérons l’ensemble
modulo 2.
Les restes possibles dans la division euclidienne par 2 sont 0 et 1.
Donc quel que soit a entier relatif :
* Soit a 0[2] , ce qui est équivalent à 2 divise a ( a pair )
* Soit a 1[2] , ce qui est équivalent à  2 ne divise pas a. ( a impair )
Le terme de « classe » n’est pas explicitement au programme de la terminale
mais voir les choses de cette façon permet d’avoir une vision plus claire de la congruence.

Forts de ce découpage en classes, on pourra ramener la résolution de certains exercices

à une simple étude de n cas,
correspondants aux différents restes possibles dans la division euclidienne par n.
5/ Congruence et opérations

Les démonstrations des propriétés qui suivent peuvent faire l’objet d’un R.O.C.
Soient a, b, a’ et b’ quatre entiers relatifs et n entier naturel,  n > 2
congruence compatible avec l'addition
La congruence est compatible avec l’addition.

Conséquence :

La congruence est compatible avec l’addition.

Conséquences :

La congruence est compatible avec la multiplication.
La congruence est compatible avec la multiplication.

Conséquences :
La congruence est compatible avec la multiplication.


La congruence est compatible avec la multiplication.

Conséquence de 1 et 4 :

La congruence est compatible avec la multiplication et l'addition
Les démonstrations des propriétés 1 et 3 s’appuient sur l’équivalence ab[n] ⇔  n divise (a-b).
La propriété 4 peut être montrée par récurrence et les déductions 2 et 5 utilisent le fait que :
cc[n]

Grâce à ces propriétés nous allons pouvoir manipuler la congruence de façon assez intuitive
mais attention :
La congruence n’est pas compatible avec la division !
La congruence n’est pas compatible avec la division

En particulier parce que la congruence est une notion qui s’applique à des nombres relatifs

et que le rapport de deux relatifs n’est pas toujours un relatif.

Et même si les rapports sont des entiers, il faudra se méfier des simplifications abusives
en particulier lors de la résolution d’équations modulo n.
La congruence n’est pas compatible avec la division
En effet, par exemple :
45 et 63, multiples de 3 sont congrus à 0 modulo 3 donc : 63
45[3]                    .
En simplifiant par 9, on obtiendrait :7
5[3]
Or : 7-5 = 2 qui n’est pas un multiple de 3 et donc : 7 5[3]

Exemples de manipulations de la congruence :
Exercice n° 1 :
Montrer que le produit de deux nombres impairs est un nombre impair.
Soit n et m deux nombres impairs.
n impair ⇔ n
1[2]   et m impair  ⇔ m1[2]
Comme la congruence est compatible avec la multiplication : n x m 1 x 1[2]
n x m
1[2] donc nxm est impair.

Conclusion : le produit de nombres impairs est un nombre impair.

Exercice n° 2 : Déterminer le reste dans la division euclidienne de :
a ) 5416 par 3
b ) 2117 par 4
c ) 232 par 4
d ) (-39)3 par 7
e ) 12013par 11
L’idée est ici de trouver un représentant plus simple du nombre puis d’appliquer la puissance.
Dans la plupart des cas, on pourra se contenter de prendre comme représentant le reste dans la division euclidienne.

a ) 5416 par 3
Ce cas est extrêmement simple : 5+4 = 9 donc 3 divise 54.
D’où  540[3]
Et comme la congruence est compatible avec la puissance : 5416 016[3]
D’où : 5416 016[3] , le reste dans la division euclidienne de  5416 par 3 est donc 0.
b ) 2117 par 4
21 = 4 x 5 + 1   Donc :  21 1[4]
D’où : 2717117[4]
D’où :  2717117[4] , le reste dans la division euclidienne de  2717 par 4 est donc 1.
c ) 232 par 4
23 = 4 x 5 + 3 
Donc 233[4]
D’où : 23232[4]
Soit :  2329[4]
Or : 9 4 x 2 + 1
Donc :  91[4]
2321[4]Le reste dans la division euclidienne de 232 par 4 est donc 1.

d ) (-39)3 par 7
La division euclidienne est plus difficile à manipuler dans que dans .
Cherchons donc plutôt un multiple de 7 proche de (-39).

-39 = -42 + 3     
-42 est un multiple de 7 donc : -39
3[7]
Remarque :
une façon simple de travailler, par exemple modulo 7, est de se dire que :
• tout multiple de 7 compte pour 0,
de la même façon que nous éliminons tout multiple dedans la recherche de la mesure principale d’un angle.
D’où :  (-39)327[7]
Or : 27 = 3 x 7 + 6
Donc : (-39)36[7]
Le reste dans la division euclidienne de (-39)3 par 7 est donc 6.

e ) 12013 par 11
120 = 11 x 10 + 10
Donc : 12010[11]
Mais mettre 10 à la puissance 13 ne va pas faciliter la résolution du problème.
Il est donc ici plus judicieux d’utiliser un autre représentant de la classe :
en enlevant 11 à 10, on obtient que : 10-1[11]
D’où :  12013(-1)13[11]
Soit 12013-1[11]
Le reste dans la division euclidienne de  12013 par 11 est donc 10.

6/ Petit théorème de Fermat

Petit théorème de Fermat
:
Soient p un nombre premier et a un entier naturel non nul.
Si pgcd (a ; p) = 1   alors ap-11[p]
Remarques :
1) La démonstration de ce théorème, assez technique, est ici admise.

2) Ce théorème, quand il est nécessaire à la résolution d’un exercice de BAC, est souvent rappelé dans l’énoncé.
Mais pas systématiquement donc …

3) Rappel : si p est premier alors « a est premier avec p » si et seulement si « p ne divise pas a ».

Corollaire du petit théorème de Fermat
:
Soient p un nombre premier,
quel que soit  a entier naturel : apa[p]
Démonstration :
* Si a est un entier naturel non nul et si p ne divise pas a alors a et p sont premiers entre eux et d’après le petit théorème de Fermat :
ap-11[p]   D’où : a x ap-1
  • Une offre 100% satisfait

    Vous résiliez quand vous voulez et sans pénalités jusqu'au 4ème cours inclus

  • Une solution économique

    -50% sur tous nos cours, vous n'avancez plus l'avoir fiscal! Aucun impact sur votre niche fiscale

  • Des cours à partir de 14.90€

    Educastream vous propose toutes les formules pour tous les budgets

  • Parrainez vos proches

    Bon d'achat de 80 euros offert si vous parrainez vos proches

  • Webcam et casque offerts