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

Congruence dans ℤ

Déjà plus de

1 million

d'inscrits !

Congruence et division euclidienne

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)

Propriétés : lien entre congruence et division euclidienne

  • Tout nombre est congru modulo nn au reste de sa division euclidienne par nn.
  • 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 nn exclu 0r<n0 ≤ r < n alors rr est le reste de la division euclidienne de aa par nn.

Transitivité

Propriétés : transitivité

  • 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]
  • aabb[n]a-a'\equiv b-b'[n]
  • Si on a ab [n]a\equiv b\ [n] et ab[n]a'\equiv b' [n] alors aabb[n]aa'\equiv bb'[n]
  • 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]
  • 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 b

Propriété :

Soit bb élément de N{0 ;1}\mathbb N\setminus\lbrace 0\ ;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}\lbrace 0\ ;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