Proving no primitive root mod mn, where m&n prime

[razmtaz]

Homework Statement

if m, n are distinct odd primes, show that the set of units mod mn has no primitive root.

Homework 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 [itex]\equiv[/itex] b mod mn iff a[itex]\equiv[/itex] b mod m and a [itex]\equiv[/itex] b mod n

The Attempt at a Solution

Not sure where to start with this one. I am 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?

 

[mighty2000]

To show that for a unit a, a((m-1)(n-1))/2 = 1, we can use the fact that a is a unit mod mn, which means that it has an inverse mod mn. This inverse can be written as a' = a^-1 (mod mn). Therefore, we have:

aa' = 1 (mod mn)

Multiplying both sides by a^(m-1)(n-1)/2, we get:

a^(m-1)(n-1)/2 * aa' = a^(m-1)(n-1)/2 (mod mn)

Using the property of congruence classes mentioned in the hint, we can write this as:

a^(m-1)(n-1)/2 * a (mod m) * a^(m-1)(n-1)/2 * a (mod n) = a^(m-1)(n-1)/2 (mod mn)

Since m and n are distinct odd primes, we know that (m-1)(n-1)/2 is an integer. This means that we can apply Euler's theorem, which states that a^(phi(m)) = 1 (mod m) and a^(phi(n)) = 1 (mod n). Therefore, we have:

a^(m-1)(n-1)/2 (mod m) = 1 (mod m) and a^(m-1)(n-1)/2 (mod n) = 1 (mod n)

Substituting these into the previous equation, we get:

1 * 1 (mod m) * 1 * 1 (mod n) = a^(m-1)(n-1)/2 (mod mn)

This simplifies to:

a^(m-1)(n-1)/2 = 1 (mod mn)

Which is what we wanted to show. This means that for any unit a, a^(m-1)(n-1)/2 = 1 (mod mn), and therefore, there can be no primitive root mod mn.