# Homework Help: Proving no primitive root mod mn, where m&n prime

1. Nov 5, 2011

### razmtaz

1. The problem statement, all variables and given/known data
if m, n are distinct odd primes, show that the set of units mod mn has no primitive root.

2. Relevant equations

[ hint: phi(mn) = (m-1)(n-1) so we can show for a, a unit mod mn, a((m-1)(n-1))/2 = 1
]
and a $\equiv$ b mod mn iff a$\equiv$ b mod m and a $\equiv$ b mod n

3. The attempt at a solution

Not sure where to start with this one. Im thinking its fairly fundamental to understanding congruence classes and such, but the hint is throwing me off. In particular how can I show that for a unit a, a((m-1)(n-1))/2 = 1 ?

after that, I know that a is a primitive root mod m if ord(a) = phi(m). this would give a(m-1)(n-1) = 1. If I could get to the point in the hint, then I would have a contradiction here and could conclude that there is no primitive root mod mn. So (assuming this is the correct approach) how can I get to a((m-1)(n-1))/2 = 1?

Last edited: Nov 5, 2011