Médaille
N°1 pour apprendre & réviser du collège au lycée.
Congruence dans ℤ

Déjà plus de

1 million

d'inscrits !

Introduction :

La notion de congruence fait souvent peur aux étudiants mais elle est indispensable en spécialité maths du bac S. Nous verrons dans un premier temps les définitions indispensables à sa compréhension. Ensuite, nous verrons le lien avec la division euclidienne. Les propriétés nous amèneront à une application : l’écriture des nombres en base bb.

Définitions

bannière definition

Définition

Congruence :

nn désigne un entier naturel non nul, aa et bb sont des entiers relatifs.

On dit que aa et bb sont congrus modulo nn lorsque la différence aba - b est un multiple de nn.

Notations : ab mod na\equiv b\ \text{mod}\ n ou ab[n]a\equiv b [n] ou encore ab (n)a\equiv b\ (n)

bannière à retenir

À retenir

  • On peut ajouter ou multiplier membre à membre des congruences.
  • La relation de congruence est symétrique, c’est-à-dire que si ab[n]a\equiv b [n] on a aussi ba[n]b\equiv a [n]. Autrement dit, si aba-b est un multiple de nn, bab-a est aussi un multiple de nn.
  • Dernier point, la relation de congruence est réflexive, c’est-à-dire qu’on a toujours aa[n]a\equiv a [n]
bannière exemple

Exemple

  • 19(4)=15-19-(-4)=-15
    Le nombre 15-15 est un multiple de 55 donc 19-19 et 4-4 sont congrus modulo 55 : 194 [5]-19\equiv -4\ [5]
  • 19+3=16-19+3=-16 et 4+3=1-4+3=-1 Donc 16-16 et 1-1 sont congrus modulo 55 : 161 [5]-16\equiv -1\ [5] ou 116 [5] -1\equiv-16\ [5]
  • 816=88-16=-8
    Le nombre 8-8 n’est pas un multiple de 55 donc 88 et 1616 ne sont pas congrus modulo 55 : 8≢16 [5]8 \not \equiv 16\ [5]
bannière à retenir

À retenir

Quelques raccourcis à connaître :

  • Un nombre est congru à 00 modulo nn si, et seulement si, ce nombre est un multiple de nn. Par exemple 2525 est congru à 00 modulo 55 : 250 [5]25\equiv 0\ [5].
  • Tout nombre pair est congru à 00 modulo 22 et tout nombre impair est congru à 11 modulo 22 :
  • donc 12351 235 est congru à 11 modulo 22 : 12351 [2]1 235\equiv 1\ [2]
  • et 12361 236 est congru à 00 modulo 22 : 12360 [2]1 236\equiv 0\ [2].
  • Tout nombre est congru à son chiffre des unités modulo 1010. Donc 35 79435\ 794 est congru à 44 modulo 1010 : 35 7944 [10]35\ 794\equiv 4\ [10].

Lien entre congruence et division euclidienne

Maintenant que nous savons ce qu’est la congruence, voyons le lien avec la division euclidienne vue dans le cours précédent.

bannière propriete

Propriété

Tout nombre est congru modulo nn au reste de sa division euclidienne par nn.

bannière demonstration

Démonstration

Si on fait la division euclidienne de aa par nn, on sait qu’il existe qq appartenant à l’ensemble des entiers relatifs Z\mathbb Z et rr appartenant à l’ensemble des entiers naturels N\mathbb N tels que a=qn+ra=qn+r avec 0r<n0≤ r < n.

On a alors ar=qna-r=qn. Donc ara-r est un multiple de nn et ainsi a est congru à rr modulo nn.

Par conséquent, il advient la propriété suivante :

bannière propriete

Propriété

  • aa et bb sont congrus modulo nn si et seulement si aa et bb ont le même reste dans la division euclidienne par nn.
  • Si ar [n]a\equiv r\ [n] avec rr compris entre zéro inclus et nn exclu 0r<n0 ≤ r < n alors rr est le reste de la division euclidienne de aa par nn.
bannière exemple

Exemple

Avec la division euclidienne de 551551 par 2626, on obtient : 551=21×26+5551=21\times26+5 donc 551551 est congru à 55 modulo 26 5515 [26]26\ 551\equiv 5\ [26]

bannière exemple

Exemple

Avec la division euclidienne de 189189 par 3535, on obtient : 189=5×35+14189=5\times35+14 donc 189189 est congru à 1414 modulo 3535 18914 [35]189\equiv 14\ [35]

Propriétés

bannière propriete

Propriété

  • Si on a ab [n]a\equiv b\ [n] et bc [n]b\equiv c\ [n] alors ac [n]a\equiv c\ [n]. C’est la transitivité.
  • Si on a ab [n]a\equiv b\ [n] et ab [n]a'\equiv b'\ [n] alors :
  • a+ab+b[n]a+a'\equiv b+b'[n]
  • et aabb[n]a-a'\equiv b-b'[n]
bannière exemple

Exemple

  • 138 [5]-13\equiv -8\ [5] et 4621 [5]46\equiv 21\ [5] ; on a alors 3313 [5]33\equiv 13\ [5] et 5929 [5]-59\equiv -29\ [5]
bannière propriete

Propriété

Si on a ab [n]a\equiv b\ [n] et ab[n]a'\equiv b' [n] alors aabb[n]aa'\equiv bb'[n]

bannière attention

Attention

Ce n’est pas valable avec la division ! Par exemple 255 [10]25\equiv 5\ [10] mais 5≢1 [10]5\not \equiv1\ [10]

bannière propriete

Propriété

  • Si on a ab [n]a\equiv b\ [n] alors pour tout kZk∈\mathbb Z, on a  : kakb [n]ka\equiv kb\ [n]
  • Si on a ab [n]a\equiv b\ [n] alors pour tout pNp∈\mathbb N^*, on a : apbp [n]a^p\equiv b^p\ [n]
bannière exemple

Exemple

72 [5]7\equiv 2\ [5] donc 7222 [5]7^2 \equiv 2^2\ [5], c’est à dire 724 [5]7^2\equiv 4\ [5].

bannière astuce

Astuce

Si on a a1 [n]a\equiv -1\ [n] alors ap(1)p [n]a^p\equiv(-1)^p\ [n]

Application : écriture des nombres en base bb

En mathématiques, l’écriture des nombres se fait en base 10. Cette base est celle utilisée dans notre société. Mais il existe d’autres bases d’écriture de nombres.

Voyons en détail l’écriture en base 10, aussi appelé le système décimal.

Dans ce système, on utilise 10 chiffres : 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9.

On fait un regroupement par 10 : c’est-à-dire qu’on forme une dizaine avec 10 unités, une centaine avec 10 dizaines, etc.

bannière exemple

Exemple

3249=3×1000+2×100+4×10+9×1=3×103+2×102+4×101+9×100\begin{aligned}\begin{array}{rl} &&3249\ &=&3\times1000+2\times100+4\times10+9\times1\ &=&3\times10^3+2\times10^2+4\times10^1+9\times10^0 \end{array}\end{aligned}

De la même manière, on peut faire des groupements par 5 ; ce qui donne un système en base 5 où on utilise 5 chiffres : 0, 1, 2, 3 et 4.

bannière exemple

Exemple

13025\overline{1302}^5 en base 5 correspond à :

1×53+3×52+0×51+2×50=1×125+3×25+0×5+2×1\begin{aligned}\begin{array}{rl} &&1\times5^3+3\times5^2+0\times5^1+2\times5^0\ &=&1\times125+3\times25+0\times5+2\times1 \end{array}\end{aligned}

Ce qui donne 202202 en base 10.

bannière propriete

Propriété

Soit bb élément de N{0 ;1}\mathbb N\setminus\lbrace0\ ;1\rbrace :

  • Tout entier naturel nn peut s’écrire d’une manière unique : n=npbp+np1bp1++n1b1+n0b0n=npb^p+n{p-1}b^{p-1}+…+n1b^1+n0b^0

Avec np0np≠0 et pour tout ii de {0 ;1 ;;P}\lbrace0\ ;1\ ;…;P\rbrace, 0ni<b0 ≤ n_i < b.

  • De plus, les chiffres de l’écriture en base bb de nn sont les nombres np, np1,, n1 et n0np,\ n{p-1},…,\ n1\text{ et }n0.

L’écriture en base bb de nn est : npnp1n1n0b\overline{npn{p-1}…n1n0}^b

bannière exemple

Exemple

  • Écrire n=4027n=\overline{402}^7 en base 10.

    n=4027=4×72+0×71+2×70=4×49+2=198n=19810\begin{aligned}\begin{array}{rl} n=\overline{402}^7&=4\times7^2+0\times7^1+2\times7^0 \ &=4\times49+2\ &=198\ n&=\overline{198}^{10}\ \end{array}\end{aligned}

  • Écrire n=53410n=\overline{534}^{10} en base 8.

On peut utiliser la division euclidienne :

534=8×66+6534=8\times66+6 donc 6 éléments isolés ;

66=8×8+266=8\times8+2 donc 2 groupements du 1er ordre isolés ;

8=8×1+08=8\times1+0 donc 0 groupement du 2e ordre isolé ;

8=8×0+08=8\times0+0 donc 1 groupement du 3e ordre.

La condition d’arrêt est que le quotient soit nul.

  • On peut donc écrire 534=10268534=\overline{1026}^8