Division euclidienne : restes

Puisque le reste de la division euclidienne de $ n $ par $ 12 $ est $ 7 $, il existe un entier naturel $ q $ tel que :

$ n=12q+7 $

C'est à dire :

$ n=3\times 4q+7 $

Toutefois on ne peut pas en déduire que le reste de la division euclidienne de $ n $ par $ 3 $ est $ 7 $ puisque $ 7\geqslant 3 $. Mais $ 7=3\times 2+1 $ donc :

$ n=3\times 4q+3\times 2+1=3\left(4q+2\right)+1 $

Cette fois on obtient bien une formule du type $ n=bq^{\prime}+r^{\prime} $ avec $ q^{\prime}=4q+2 $ et $ r^{\prime}=1 < 3 $.

Le reste de la division euclidienne de $ n $ par $ 3 $ est donc $ 1 $.

De même :

$ n=4\times 3q+7=4\times 3q+4\times 1+3=4\left(3q+1\right)+3 $

Le reste de la division euclidienne de $ n $ par $ 4 $ est donc $ 3 $.

Le reste de la division euclidienne de $ n $ par $ 4 $ étant $ 3 $, il existe un entier naturel $ k $ tel que :

$ n=4k+3 $(1)

On voudrait maintenant obtenir une expression de la forme $ n=12q+r $, il va donc falloir remplacer $ k $ par $ 3q+\cdots $ dans (1).
D'où l'idée de diviser $ k $ par $ 3 $...

On raisonne alors par disjonction de cas :

• Si le reste de la division euclidienne de $ k $ par 3 est 0, alors :

  $ k=3q $

  donc $ n=4\times 3q+3=12q+3 $.

  Le reste de la division euclidienne de $ n $ par $ 12 $ est donc $ 3 $.

• Si le reste de la division euclidienne de $ k $ par 3 est 1, alors :

  $ k=3q+1 $

  donc $ n=4\times \left(3q+1\right)+3=12q+7 $.

  Le reste de la division euclidienne de $ n $ par $ 12 $ est alors $ 7 $.

• Si le reste de la division euclidienne de $ k $ par 3 est 2, alors :

  $ k=3q+2 $

  donc $ n=4\times \left(3q+2\right)+3=12q+11 $.

  Dans ce cas, le reste de la division euclidienne de $ n $ par $ 12 $ est $ 11 $.

Comme il n'y a pas d'autres possibilités, le reste de la division euclidienne de $ n $ par $ 12 $ est soit $ 3 $, soit $ 7 $, soit $ 11 $.