Division euclidienne dans Z. Unicité et existence du quotient et du reste. Applications à l’arithmétique.

• Raisonnement par récurrence
• Majorant, maximum, minimum
• Toute partie non vide et majorée de Z possède un plus grand élément
• Suite strictement décroissante
• Groupes et sous-groupes, groupes engendrés
• Formule du binôme de Newton

Division euclidienne dans Z

Théorème fondamental

Pour tout couple (a,b)ÎZ´Z^*, il existe un unique couple (q,r)ÎZ´N tel que a=bq+r et 0£ r < |b|

a, b, q, r sont respectivement appelés dividende, diviseur, quotient et reste de la division euclidienne de a par b.

Effectuer la division euclidienne de a par b, c’est déterminer q et r.

Remarques
Si r=0, on dit que a est multiple de b ou que b divise a et on note a|b.
La démonstration, ci dessus, montre que l’on peut définir une division euclidienne dans N, pour laquelle (a,b)ÎN´N^* et (q,r)ÎN´N.

Ce théorème prouvant l’existence et l’unicité du couple (q,r), sans fournir un moyen pratique de les calculer, il peut être intéressant de se pencher sur cette question.

Détermination du quotient et du reste

Cas où (a,b)ÎN´N^* (Méthode de descente de Fermat)

Si a<b alors le couple (0,a) répond à la question

Sinon a³b
Soit q₁ÎN^* tel que bq₁£a. On pose r₁=a-bq₁
Si r₁<b, (q₁,r₁) est le couple cherché
Sinon b£r₁
Soit q₂ÎN^* tel que bq₂£r₁. On pose r₂=r₁-bq₂
Si r₂<b, (q₁+q₂,r₂) convient.

On construit ainsi deux suites (q_n) et (r_n) définies par la relation de récurrence :
Si r_n³b alors q_n+1 est tel que : bq_n+1£r_n et r_n+1=r_n-bq_n+1

La suite (r_n) étant strictement décroissante dans N, il existe nécessairement un rang m pour lequel r_m<b (donc (r_n) suite finie) et (q₁+…+q_m,r_m) est le couple recherché.

Une fois introduit le système de numération décimale, on pourra s’interroger sur le lien entre ce procédé et la méthode classique consistant «à poser» la division.

Sous-groupes de Z

Forme des sous-groupes de Z

Après avoir remarqué que pour tout entier relatif a, aZ est un sous-groupe de Z, on peut énoncer la proposition suivante

Tout sous-groupe de (Z,+) est de la forme aZ avec aÎN.

PGCD, PPCM, Théorème de Bezout

Soient a et b deux entiers relatifs.
On appelle PGCD de a et b, l’entier naturel d qui engendre le sous-groupe aZ+bZ.
On appelle PPCM de a et b, l’entier naturel m qui engendre le sous-groupe aZÇbZ.

Remarques
L’hypothèse «entier naturel» permet d’assurer l’unicité.
On peut vérifier de plus que aZ+bZ est le plus petit sous-groupe contenant aZ et bZ, tandis que aZÇbZ est le plus grand sous-groupe contenant aZ et bZ.
L’algorithme d’Euclide repose également sur la division euclidienne dans Z et permet une détermination pratique du PGCD(a,b)

Théorème de Bezout

Soient a et b deux entiers relatifs
PGCD(a,b)=1 Û $(u,v)ÎZ² tel que au+bv=1

Cas particulier du théorème suivant
Soit (a,b)ÎZ^*´Z^*. Soit D=PGCD(a,b). $(u,v)ÎZ² tel que au+bv=D (égalité de Bezout)

Applications à l’arithmétique

Systèmes de numération

Soit bÎN tel que b³2
Pour tout entier naturel non nul a, il existe un unique entier n et un unique (n+1)-uplet (a₀,…,a_n) d’entiers strictement inférieurs à b tel que : a_n¹0 et a=a_nbⁿ+a_n-1b^n-1+…+a₁b+a₀

Le (n+1)-uplet (a₀,…,a_n) s’appelle écriture de a en base b et on note a=a_na_n-1…a₀^b
Les ai sont les chiffres de a en base b.

Critères de divisibilité en base b

Si a=a_n…a₀^b et k³1

1. b^k|a Û l’écriture de a se termine par k zéros
2. (b-1)|a Û (b-1)|å(i=0,n,a_i)
3. (b+1)|a Û (b+1)|å(i=0,n,(-1)ⁱa_i)

Exemples en base 10
2|a Û a₀Î{0,2,4,6,8}
3|a Û 3|å(k=0,n,a_k)
4|a Û 4|a₁a₀
5|a Û a₀Î{0,5}
6|a Û 2|a et 3|a
8|a Û 8|a₂a₁a₀

Pratique de l’algorithme de division en base 10

Soit a³b>0 et 10^n-1£a<10ⁿ, 10^p-1£b<10^p
a=a_n-1…a₀ et a_n-1¹0
Si a_n-1…a_n-p³b, on pose n-p=k
Sinon n-p-1=k et a_n-1…a_k=a’
a’=bq₁+r₁, q₁ est un nombre à un chiffre non nul et on reprend la division de (10r₁+a_k-1) par b
Si k-1³0, a=(q₁10^k+q₂10^k-1+…+q_k+1)b+r_k+1
Donc q=q₁q₂…q_k+1 et r=r_k+1

Exemple
a=127, b=11
On a: n=3, p=2, k=1
On trouve : q₁=1, q₂=1, r₁=1, r₂=6
Finalement: q=11 et r=6