Partager |

Calculer un reste à l'aide de congruences

Situation

On cherche à déterminer le reste de la division euclidienne d'un très grand entier par un autre entier.
Par exemple, on recherche le reste de la division euclidienne de 12 345^(2000) par 7.
Une calculatrice ne permet pas de répondre (les nombres sont trop grands) mais il est possible de résoudre le problème en utilisant les congruences.

Méthode

Pour trouver le reste de la division euclidienne de a^b par n on va utiliser la caractérisation du reste à l'aide de congruence :
r et le reste de la division euclidienne de m par n <=> syst(r==m..[n];0 <= r < |n|)
et on va chercher à remplacer a et b par deux autres entiers plus petits u et v tels que a^b==u^v..[n]

1.On utilise la propriété :
a==u..[n] => a^b==u^b..[n]
pour remplacer a par un entier u plus petit, par exemple le reste de la division euclidienne de a par n
2.On calcule ensuite les puissances successives de u (u^2, u^3, . . . ) et on cherche un entier k tel que u^k==1..[n] (un tel entier existe si u et n sont premiers entre eux - l'exemple 2 traite un cas où il n'est pas possible de trouver un tel entier)
On effectue alors la division euclidienne de b par k :
b=kq+v
donc :
u^b=u^(kq+v)=u^(kq)*u^(v)=[u^k]^q*u^(v)
u^b==[u^k]^q*u^(v)==1^q*u^(v)==u^(v)..[n]
3.On peut conclure :
a^b==u^b==u^(v)..[n]
Donc a^b et u^(v) ont le même reste dans la division par n. Ce reste est alors facile à calculer car u et v sont "petits".

Exemple 1

On recherche le reste de la division euclidienne de 12 345^(2000) par 7.

1.On effectue tout d'abord la division euclidienne de 12 345 par 7. Le quotient est 1763 et le reste est 4.
Donc 12 345==4..[7] et 12 345^(2 000)==4^(2 000)..[7]
2.
4^2=16==2..[7]
4^3=64==1..[7]
On effectue la division euclidienne de 2 000 par 3 : 2 000 = 666*3+2
Donc :
4^(2 000)=4^(666*3+2)=[4^3]^666*4^2==1^666*4^2=16..[7]
3.Le reste de la division euclidienne de 12 345^(2000) par 7 est donc le même que le reste de la division euclidienne de 16 par 7 c'est à dire 2.

Exemple 2

On recherche le reste de la division euclidienne de 12 344^(2000) par 6.

1.On effectue tout d'abord la division euclidienne de 12 344 par 6. Le quotient est 2057 et le reste est 2.
Donc 12 344==2..[6] et 12 345^(2 000)==2^(2 000)..[6]
2.
2^2==4..[6]
2^3=8==2..[6]
2^4=16==4..[6]
etc.
Ici on ne peut pas trouver d'entier k tel que 2^k==1..[6] mais on remarque que 2^k==2..[6] si k est impair et 2^k==4..[6] si k est pair (ce résultat peut se démontrer facilement par récurrence; faites-le!)
Donc :
2^(2 000)==4..[6]
Le reste de la division euclidienne de 12 344^(2000) par 6 est donc 4.
Partager |

Copyright 2007-2012 - Maths-cours.fr