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

1. Apr 3, 2012

### teddyayalew

1. The problem statement, all variables and given/known data
http://i44.tinypic.com/33z5js3.jpg

It is part b

2. Relevant equations
ae = 1 (mod m)

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

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

3. The attempt at a solution

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

So then a(eu) = ag + psi(m)= ag*apsi(m) = ag (mod m) from the above relation.

Also aeu = 1u = 1 mod(m)

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

I am having trouble then showing that g =psi(m) can someone help me.
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Apr 3, 2012

### 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.

3. Apr 4, 2012

### teddyayalew

Ahh I see! Thank you for your help.