## Compute the number of units in ZZ/(n)

Prove that the number of elements of is , where denotes the Euler totient function.

By a previous theorem, the distinct elements of are precisely the classes . Recall that consists precisely of those residue classes such that there exists with . If and , we have such that , and thus . In particular, and are relatively prime. Conversely, if and are relatively prime, then there exist and such that , and thus . Hence, the elements of are precisely those residue classes whose representatives in the (integer) range are relatively prime to . By definition, there are of these.

### Like this:

Like Loading...

*Related*

or leave a trackback:

Trackback URL.

## Comments

Hi,

Am I missing something here?

It seems to me that we don’t yet know that the subset of units of Z/(n) is equal to the subset of relatively prime representatives. In fact, you will prove that equality in a few more exercises.

BTW, this is a wonderful resource for someone like me: I don’t have access to any academic help, but I need some help getting thru all this stuff. Thanks.

The definition given by D&F for is those classes for which there exists a class such that . Combined with Bezout’s identity, this is equivalent to having and be relatively prime.

This is one of the places where I would have ordered the exercises in D&F differently. I’m not sure how one would go about proving that without using the “relatively prime” characterization of the elements in .

I’m glad you find this useful!