Maths-cours

Cours & exercices de mathématiques

  • Troisième
  • Seconde
  • Première
  • Terminale
  • Tle Complément.
  • Tle Expert
  • Quiz
  • 3ème
  • 2nde
  • 1ère
  • Tle
  • Tle Comp
  • Tle XP
  • Quiz

Tle Expert

Cours

Divisibilité et congruences

1. Division euclidienne

Définition

Soient aaa et bbb deux entiers relatifs tels qu'il existe un entier relatif kkk tel que a=bka=bka=bk.

On dit alors que :

  • bbb divise aaa ;

  • bbb est un diviseur de aaa ;

  • aaa est un multiple de bbb.

Ceci se note b∣ab|ab∣a

Exemple

15=3×515=3\times 515=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.

  • aaa et −a-a−a ont les mêmes diviseurs.

Propriétés

  • Si aaa divise bbb et bbb divise aaa, alors aaa et bbb sont égaux ou opposés.

  • Si aaa divise bbb et bbb divise ccc, alors aaa divise ccc.

  • Si ccc divise aaa et ccc divise bbb, alors ccc divise toute combinaison linéaire de aaa et bbb (c'est-à-dire tout nombre de la forme au+bv;u∈Z,v∈Zau+bv ; u\in \mathbb{Z}, v\in \mathbb{Z}au+bv;u∈Z,v∈Z).

Théorème et définitions

Division euclidienne dans Z\mathbb{Z}Z

Soient aaa et bbb deux entiers relatifs avec b≠0b\neq 0b≠0.

Il existe un et un seul couple d'entiers relatifs (q,r)\left(q,r\right)(q,r) tels que :

a=bq+ra=bq+ra=bq+r et 0⩽r<∣b∣0 \leqslant r < |b|0⩽r<∣b∣.

qqq et rrr s'appelle respectivement le quotient et le reste de la division euclidienne de aaa par bbb.

Exemple

-14=3×\times ×(-5)+1 et 0⩽\leqslant ⩽1< < <3

La division euclidienne de -14 par 3 donne un quotient de -5 est un reste de 1.

Remarques

  • Attention ! Ne pas oublier la condition 0⩽r<∣b∣0 \leqslant r < |b|0⩽r<∣b∣. La seule égalité a=bq+ra=bq+ra=bq+r ne suffit pas à prouver que qqq et rrr sont les quotient et reste dans la division euclidienne de aaa par bbb.

  • aaa est divisible par bbb si et seulement si le reste de la division de aaa par bbb est égal à zéro.

2. Congruences

Définition

On dit que deux entiers relatifs aaa et bbb son congrus modulo nnn ( n∈N∗n\in \mathbb{N}^*n∈N​∗​​ ) et l'on écrit a≡b[n]a\equiv b \left[n\right]a≡b[n] si et seulement si aaa et bbb ont le même reste dans la division par nnn.

Exemple

18≡23[5]18\equiv 23 \left[5\right]18≡23[5] car 18 et 23 ont tous les deux 3 comme reste dans la division par 5.

Propriétés

  • a≡b[n]a\equiv b \left[n\right]a≡b[n] si et seulement si nnn divise a−ba-ba−b en particulier a≡0[n]a\equiv 0 \left[n\right]a≡0[n] si et seulement si nnn divise aaa.

  • Si a≡b[n]a\equiv b \left[n\right]a≡b[n] et b≡c[n]b\equiv c \left[n\right]b≡c[n], alors a≡c[n]a\equiv c \left[n\right]a≡c[n].

Propriétés (Congruences et opérations)

Soient quatre entiers relatifs a,b,c,da, b, c, da,b,c,d tels que a≡b[n]a\equiv b \left[n\right]a≡b[n] et c≡d[n]c\equiv d \left[n\right]c≡d[n]. Alors :

  • a+c≡b+d[n]a+c\equiv b+d \left[n\right]a+c≡b+d[n] et a−c≡b−d[n]a-c\equiv b-d \left[n\right]a−c≡b−d[n].

  • ac≡bd[n]ac\equiv bd \left[n\right]ac≡bd[n].

  • ka≡kb[n]ka\equiv kb \left[n\right]ka≡kb[n] pour tout entier relatif kkk.

  • am≡bm[n]a^{m}\equiv b^{m} \left[n\right]a​m​​≡b​m​​[n] pour tout entier naturel mmm.

Propriété

rrr est le reste de la division euclidienne de aaa par bbb si et seulement si :

{r≡a[b]r<∣b∣\left\{ \begin{matrix} r\equiv a \left[b\right] \\ r < |b| \end{matrix}\right.{​r≡a[b]​r<∣b∣​​

Exemple

On cherche à déterminer le reste de la division euclidienne de 200920092009^{2009}2009​2009​​ par 5.

2009≡−1[5]2009\equiv -1 \left[5\right]2009≡−1[5] car 2009-(-1)=2010 est divisible par 5.

Donc :

20092009≡(−1)2009[5]2009^{2009}\equiv \left(-1\right)^{2009} \left[5\right]2009​2009​​≡(−1)​2009​​[5] c'est-à-dire 20092009≡−1[5]2009^{2009}\equiv -1 \left[5\right]2009​2009​​≡−1[5]

Or −1≡4[5]-1\equiv 4 \left[5\right]−1≡4[5] donc 20092009≡4[5]2009^{2009}\equiv 4 \left[5\right]2009​2009​​≡4[5]

Comme 0⩽4<50\leqslant 4 < 50⩽4<5, le reste de la division euclidienne de 200920092009^{2009}2009​2009​​ par 5 est 4.

  Format PDF      Signaler une erreur

Dans ce chapitre...

Exercices

  • facileDivision euclidienne d'entiers négatifs
  • moyenArithmétique - Bac S Amérique du Nord 2013 (spé)
  • moyenCodage - Bac Nle Calédonie 2013
  • moyenDivision euclidienne : restes
  • moyenSolutions entières d'équations
  • difficileCongruences - Puissances de 2 et de 3
  • difficileDivisibilité et récurrence
  • difficileSomme de puissances et congruences

Méthodes

  • Calculer un reste à l'aide de congruences

VOIR AUSSI...

  • tableau de signe
  • loi de probabilité
  • fonction trigonométrique
  • suite géométrique
  • théorème de thalès
  • polynôme second degré
  • limites
  • fonction affine
  • théorème de pythagore
  • fonction exponentielle
  • division euclidienne
  • trigonométrie
  • python en seconde
  • fonction paire
  • loi normale
  • algorithme de dijkstra
  • tableau de variation
  • fonction dérivée

© 2021 - Maths-cours.fr - Nous contacter