Show that the e = order of a modulo m is equal to psi(m)

[teddyayalew]

Homework Statement

http://i44.tinypic.com/33z5js3.jpg

It is part b

Homework Equations

a^e = 1 (mod m)

a^(psi(m)) = 1 (mod m)

eu - psi(m)v = gcd(e, psi(m)) = g

The Attempt at a Solution

I know that eu = g + psi(m)v

So then a^(eu) = a^{g + psi(m)}= a^g*a^psi(m) = a^g (mod m) from the above relation.

Also a^eu = 1^u = 1 mod(m)

So then we know a^g = 1 mod(m) . Because g divides e , g≤e . and because e is the smallest possible number s.t a^e = 1 (mod m) e≤g so g =e.

I am having trouble then showing that g =psi(m) can someone help me.

 

[Robert1986]

Well, from where you are, you could try to prove that e divides g, but I wouldn't do it (and don't know if it can be done.)

Use the division algorithm to note that you can write phi(m) = eq + r where 0 \leq r < e and show that r must be zero.

 

[teddyayalew]

Ahh I see! Thank you for your help.