WisFaq!

Modulo rekening

Ik moet x=55⁸³ (mod 167) oplossen en m.b.v. een computerprogramma krijg ik volgens mij x=1.
Hoe zou dit opgelost kunnen worden met de hand?
Groeten,

B.Boekhoudt
14-2-2004

Antwoord

Na wat rekenwerk zijn we tot de conclusie gekomen dat er x = 166 ofwel x = -1 uitkomt. Typefout wellicht?

In ieder geval is de manier van aanpak als volgt:

55¹ = 55 (mod 167)
55² = 55 * 55 = 19 (mod 167)
55⁴ = (55²)² = 19² (mod 167) = 27 (mod 167)
55⁸ = ... = 27² (mod 167) = 61 (mod 167)
55¹⁶ = ... = 61² (mod 167) = 47 (mod 167)
55³² = ... = 47² (mod 167) = 38 (mod 167)
55⁶⁴ = ... = 38² = 108 (mod 167)

83 = 1 + 2 + 16 + 64
Dus 55⁸³ = 55¹ * 55² * 55¹⁶ * 55⁶⁴ = 55 * 19 * 47 * 108 (mod 167) = -1 (mod 167)

Succes,

Erica
15-2-2004