Division euclidienne dans  , unicité du quotient et du reste.Applications.

Pre requis :

Toute partie non-vide et majorée de  admet un plus grand élément.
 

I) Division euclidienne dans  :

Théorème :

Soit (a,b) ^* ,alors :  ! (q,r) tels que :

a = bq + r avec 0r| b |
 

Preuve :

1) Existence :

• Si b > 0 :

alors on pose E = { k tq bka }

- E est une partie de  non-vide car si a0 , 0 E

si a<0 , aE.

- E est majorée par max(0,a)
alors E admet un plus grand élément q qui vérifie bqa

D'autre part, q+1E  donc b(q+1) > a

On a bqa <b(q+1)
On pose r =a - bq et 0 r < b avec b = | b |

• Si b < 0 :

Et d'après ce qui précède, q',tq b'q'a < b'(q'+1)

-bq'a < -b(q'+1)
On pose q = -q' alors bq a < bq - b

On pose r = a -bq donc 0r < -b
-b = | b |
 

2) Unicité :

Supposons que :
 tout d'abord : ( q₁ , r₁ )  , a = bq₁ + r₁
puis que : ( q₂ , r₂ )  , a = bq₂ + r₂

 avec 0 r₁ < | b |
et 0r₂ < | b |

On a donc :

| r₁ - r₂ | = | b | | q₁ - q₂ |

0| r₁ - r₂ | < | b |

Donc :

0| b | | q₁ - q₂ | < | b |

Or | q₁ - q₂ |  donc q₁ = q₂

Et par suite : r₁ = r₂

Définitions :

• Déterminer ( q, r ) c'est effectuer la division euclidienne de a par b .
• a, b ,q ,r sont respectivement appelés : dividende ,diviseur,quotient et reste .

• r = 0  b | a
• q = 0  0a < | b |
• Si (a,b)^* ,alors q

II) Applications :

1) Système de numération (écritures d'un entier dans une base b )

Théorème :

Soit b^* avec b2

 : x^* ,  ! n,  ! ( a_i )_{0i n} tq :

x = a_ibⁱ    ,avec a_n  0

0a_i <b, i [| 0;n |]

Définition :

( a_i ) _{i[| 0;n |]} est appelée représentation de n en base b .

Exercice : a) Montrer que 147 = ⁸
b) Ecrire un programme effectuant un changement de base à partir de la base 10 .
 

2) Recherche du PGCD de deux entiers par l'algorithme d'Euclide .

3) Congruence

4) Sous-groupes de 
 

2)

Rque :

Si a = 0 et b0 alors pgcd(a,b) = b

Lemme :

a = bq + r avec 0r < b, alors pgcd(a,b) = pgcd(b,r)

Théorème :

On définit ( a_n )_n0 et ( b_n )_n0 par :

a₀ = a et b₀ = b

et n , a_n+1 = b_n

b_n+1 est le reste de la division euclidienne de a_n par b_n .

Alors  p , b_p = 0 donc : pgcd(a,b) = a_p  .

Démo :

On a : n , 0b_n+1 < b_n

( b_n ) est une suite strictement décroissante de  tant qu'elle ne prend pas la valeur 0 .

Donc :  p tel que b_p = 0

pgcd( a,b ) = pgcd( a₀,b₀ ) = pgcd( a₁,b₁ ) =... = pgcd( a_p,b_p ) = a_p

Exo : a) Calcul de pgcd(123,45)
  b) Ecrire un programme qui calcule le pgcd de deux entiers.
 

3)

Déf :
Soit (x,y)² , n^* , x est congru à y modulo n si :

n divise ( x-y ) .

Notation : xy [n]

Théorème :

( x,y )  , xy [n] x et y ont même reste dans la division euclidienne par n .

Démo :

x = nq₁ + r
y = nq₂ + r

D'où : x - y =n(q₁ -q₂) c'est-à-dire : n | x-y

Donc : xy [n]

Si xy [n] alors n | (x-y) ,donc  k, x-y = kn

Or x = nq₁ + r₁ , 0r₁ < n
et y = nq₂ + r₂  , 0r₂ < n

(q₁ - q₂ )n + (r₁ - r₂ ) = kn

| r₁ - r₂ | = n | k - q₁ + q₂ |
Donc :
n divise | r₁ - r₂ | avec 0 | r₁ - r₂ | < n
et | r₁ - r₂ | 

Donc : r₁ = r₂

4) Sous-groupes de ( , + ) :
 

H est un sous-groupe de ( , + )   n , tq H =n

Démo :

( Sens trivial )
 

Soit H un sous-groupe de ( , + )

• Si H = { 0 } alors H = 0
• Si H  { 0 } alors H^*  

H^*

Donc , H^* admet un plus petit élément n .

Montrons que    H = n :

:

Soit h n alors :  k , h = nk

• Si k = 0 , h = 0 donc h  H
• Si k > 0 , h = n + n +...+ n ( k fois ), hH
• Si k < 0 , h = -n + -n +...+ -n ( - k fois ), h H

Donc n H

Soit hH :
alors  (q , r )  tq : h = nq + r avec 0r < n
D'où r = h - nq  H

Si r0 , rH* avec r < n
Contradiction avec n plus petit élément de H*

D'où r = 0 et h = nq  n ,d'où Hn

Par conséquent :
 

H = n