Multiplicative inverses

[colerelm]

This problem is in my discrete math book and I have no idea where to start. Can anyone help me?

Show that if m is not prime, then at least square root of m elements of Z_m do not have multiplicative inverses.

 

[daon2]

What have you tried? What can you use? Do you know what condition must be satisfied to be a unit modulo m?

One way would be to consider the prime divisors of m.

 

[HallsofIvy]

This problem is in my discrete math book and I have no idea where to start. Can anyone help me?

Show that if m is not prime, then at least square root of m elements of Z_m do not have multiplicative inverses.

Look at a simple example: say m= 4, the smallest non-prime (other than 1). \(\displaystyle Z_4\) has, of course, four elements, 0, 1, 2, and 3. which of those do NOT have multiplicative inverses? If that doesn't make it clear, try m= 9.