"arithmétique bis"

Mathematiques > sujets expliqués - Question simple

	"Arithmétique bis" revenir au plan			docs
		J'ai déjà envoyé(...)
		On cherche n tel que a^n ait p lire

On cherche n tel que a^n ait pour reste r dans la division par d.
Le principe n'est pas de calculer a^n (trop grand) mais seulement
a^n - K*d. En effet a^n et a^n-K*d ont même reste dans la division
par d. On procède sonc ainsi

On pose r(k) = a^k - K(k)*d de sorte que 0 <= r(k) < d. k est le
reste de a^k divisé par d.

r(k+1) = a^(k+1) - K(k+1)*d
= a^k * a - K(k+1)*d
= (r(k) + K(k)*d)* a - K(k+1)*d [on remplaxe a^k par r^k + ...]
= r(k)*a + K(k)*d*a - K(k+1)*d
= r(k)*a + (K(k)*a - K(k+1))*d
= a*r(k) + facteur * d

Le reste de a^(k+1) divisé par d se déduit du reste de a^k divisé
par d en le multipliant par a et en lui retranchant ce qu'il faut
de fois d.

Dans notre cas
_ facteur choisi pour avoir 0 <= r(k) < 77
/
r(1) / = 5
r(2) = 5r(1) - 0*77 = 25
r(3) = 5r(2) - 1*77 = 48
r(4) = 5r(3) - 3*77 = 9
r(5) = 5r(4) - 3*77 = 45
r(6) = 71
r(7) = 47
r(8) = 4
r(9) = 20
...

On montre ensuite que c'est périodique. (On retombe fatalement deux fois sur un même reste
puisqu'il y a une infinité de k >= 0 et seulement 77 restes possibles, et dès qu'un reste
revient tout se ré-enchaîne pareillement.)


"

Documents attachés :

aucun document joint.