• R appartient à {0 ; 1 ; 2 ;...;|A|-1 } et
• B = Q.A + R

R et Q sont appelés respectivement le RESTE et le QUOTIENT
de la Division Euclidienne de B par A.

Par exemple,

• si B = -10 et A = -3 , on a : 10 = 4*(-3) + 2. Donc , Q = 4 et R = 2.
• si B = -14 et A = 3 , on a : -14 = (-5)*3 + 1. Donc, Q = -5 et R = 1.
• si B = -72 et A = -10, on a : 70 = (8)*(-10) + 8. Donc Q = 8 et R = 8.

En revanche, l'écriture -10 = 3*(-3) - 1 n'est la division euclidienne de -10 par -3,
le "reste" n'étant pas compris entre 0 et 2.

On peut alors remarquer que

• B est divisible par A si et seulement si le reste de la division euclidienne de B par A est nul.
• Q est le quotient de la division euclidienne de B par A si et seulement si Q.A est le plus grand multiple de A inférieur à B.
• Q est la partie entière de B / A. Q = int(B / A). Par exemple, ent( 10 / -3) = - 4.

Pour déterminer alors simplement le reste et le quotient dans la division euclidienne de B par A à l'aide d'une machine programmable, pour des entiers A et B ne dépassant les capacités de cette machine, il suffit de calculer la partie entière Q de B / A , puis de calculer R = B - Q.A.

Par exemple, si on cherche la division euclidienne de 123456 par 123, on peut remarquer que:
123456 / 123 = 1003,7073..... Donc Q = 1003. D'où R = 123456 - 1003*123 = 87.
La division euclidienne obtenue est alors : 123456 = 1003*123 + 87.

Un exemple d'utilisation de la division euclidienne:
Les FRACTIONS CONTINUES
L'exemple qui suit est un cas particulier de l'écriture sous forme de fractions continues d'un nombre réel x.
Le principe est le suivant:
Si x est un nombre réel non nul, en notant ent(x) sa partie entière, on peut écrire alors que
x = ent(x) + a₀ , où a₀ est un réel appartenant à [0 ; 1[.
Si a₀ est nul, alors x est simplement un entier.
Sinon, posons  . b₀ est alors un réel > 1. Posons x₁ = ent(b₀).
On peut alors écrire que b₀ = x₁ + a₁  où a₁ est appartient à [0;1[.
Si a₁ est non nul, b₁ n'est pas un entier et en posons: , on peut alors écrire que

On construit donc une suite (x_n) ,une suite (a_n)  et une suite (b_n) définies par les relations suivantes:

• x₀ = ent(x) , a₀ = x - x₀ ,
• si a_n est non nul , alors        x_n+1 = ent(b_n)   ,      a_n = x_n+1 - b_n   ,      

L'écriture de x ainsi obtenue est alors:

C'est de ce que l'on appelle la décomposition en Fractions Continues de x.

On démontre alors sans problème que cette écriture peut se poursuivre ausi loin que l'on veut si et seulement si x n'est pas un nombre rationnel.

Si x est rationnel, cette écriture s'arrête à partir d'une valeur de n. Par exemple, pour

Comme 100 = 5*17 + 15, (division euclidienne de 100 par 17), on a :

On a donc écrit ce nombre sous forme de Fraction Continue.

On retrouvera l'utilisation de l'écriture d'un nombre rationnel sous forme de Fractions Continues dans le cadre des  équations de Bezout: ax + by = c
 

Conséquences de la Division Euclidienne

1. b est un mulitple de a si et seulement si le reste de la division euclidienne de b par a est 0.
2. b et b' ont même reste par la division euclidienne par a si et seulement si ( b - b' ) est un multiple de a.
      Pour le voir, il suffit de poser r = reste de la division de b par a et
      r ' = reste de la division de b '  par a. Il existe q et q' dans Z tels que
      b = q.a + r   et  b ' = q'.a + r'.   Donc : (b - b ' ) = (q - q').a + (r - r').
      On conclut en utilisant 1.
3. Principe de la Congruence ou MODULO a.
   Si le reste de la division euclidienne de b par a est r , on écrit alors:
   
   ou encore
   
   Pour deux entiers relatifs b et b', ont écrit
   b = b'  modulo a      ou       si et seulement si b et b' ont même reste par la division euclidienne par a.
   Par exemple:
   36 = 7.5 + 1     et   15 = 7.2 + 1   . Le reste de la division euclidienne de 36 et de 15 par 7 est r = 1.  On a donc : 36 = 15  [ 7]   . 36 et 15 sont identiques modulo 7.
   Propriété de la Congruence:
   
   
        La congruence modulo a est donc une relation compatible avec l'addition et la multiplication
         sur Z. Par exemple:
          11 = 4 [ 7 ]   et   23 = 2 [ 7 ]   donc 11+ 23  = 34 = 6 [ 7 ]  et  11.23 = 253 = 4.2 = 8 = 1 [ 7 ].
          C'est cette compatibilité permet de simplifier toutes une série de question.
          Voici un premier exemple d'utilisation.
          Un  résultat connu des éléves de primaire est:
          UN NOMBRE EST DIVISIBLE PAR 3 SI
          LA SOMME DE SES CHIFFRES EST ELLE-MEME DIVISIBLE PAR 3.
          Par le vérifier, remarquons qu'un nombre entier b , écrit en base 10, est de la forme
   
          b = a_k a_k-1a_k-2 ...a₀ ce qui permet d'écrire que
          b = a₀ + 10.a₁ + 10².a₂ + .... +  10^k.a_k
          où  a₀ , a₁ , a₂ , .... ,a_k sont des entiers appartenant à {0;1;2;...;9}.
          Comme 10 = 1 [3], on en déduit que, comme la congruence modulo 3 est compatible
          avec la multiplication , que pour tout n entier > 0 , 10ⁿ = 1 [3].
          Donc pour tout entier b, on a :
          b = a₀ + a₁ + .... + a_k [3].   
          b est donc divisible par 3 si et seulement si la somme de ses chiffres
          dans son écriture en base 10 est divisible par 3.
          Voici un second exemple d'utilisation.
          Quelle est le reste de la division de 5¹⁰⁰ par 7?
           Pour répondre à cette question, il suffit de faire "défiler" les restes des puissances de 5
           jusqu'à ce que l'on tombe sur un reste égal à 1.
           5 = 5 [ 7].        5² = 25 = 4 [ 7 ]      5³ = 5.4 = 20 = 6 [7]     5⁴ = 5.6 = 30 = 2 [ 7 ]
           5⁵ = 5.2 = 10 = 3 [ 7 ]     5⁶ = 5.3 = 15 = 1 [ 7 ]     5⁷ = 5.1 = 5 [7]
           On en déduit alors que pour tout entier naturel n,
           5⁶ⁿ⁺¹ = 5 [7]   ,   5⁶ⁿ⁺² = 4 [7]  , 5⁶ⁿ⁺³ = 6 [7]  , 5⁶ⁿ⁺⁴ = 2 [7]
           5⁶ⁿ⁺⁵ = 3 [7]   ,   5⁶ⁿ = 1 [7].
           Or 100 = 16.6 + 4  donc 5¹⁰⁰  = 2 [7].
           Le reste de la division de 5¹⁰⁰ par 7 est donc 2.
           
          Troisième exemple.
           Montrez que 100⁷ -100 est divisible par 7.
           C'est une petite variante du Petit Théorème de Fermat
           ( à ne pas confondre avec LE THEOREME DE FERMAT !!)
           On remarque que 100 = 2 [ 7 ].
           Or , 2² = 4 [7]   ,  2³ = 1 [7] , 2⁴ = 2 [7]  , 2⁵ = 4 [7]   ,  2⁶ = 1 [7]  et  2⁷ = 2 [7].
            Donc 100⁷ = 2 [7]
            On en déduit alors que 100⁷ - 100 = 2 - 2 = 0 [7].
            100⁷ - 100 est bien divisible par 7.
   
           Quatrième exemple.
           Si n est un entier impair somme de deux carrés ( n = a² + b² avec a et b entiers)
           Alors n est congru à 1 modulo 4  ou encore   n = 1 [4]  
         Ceci est un premier pas vers un autre résultat plus général qui sera vu plus loin.
           Si n = a² + b² , alors n = a² + b² modulo 4.
           Les carrés possibles modulo 4 sont :
           0² = 0   ,     1² = 1 [4]    ,   2² = 4 = 0 [4]   ,   3² = 9 = 1 [4].
           Comme n est impair, il ne peut être égal qu'à 1 ou 3 modulo 4.
           Donc, si n est impair et somme de deux carrés, il ne peut être égal, modulo 4,
           qu'à 0² + 1²   ou   0² + 3²   ou   2² + 1²   ou   2² + 3².
           Dans tous les cas, il est égal à 1 modulo 4.