Is every member of a group under multiplication modulo N, co prime to N?

Question

This is probably a very obvious bit of group theory for anyone who's actually studied it, I'm a theoretical physics student writing my masters project on Shor's algorithm and this seems to be a necessary but not solely sufficient way of quickly finding members of groups under multiplication modulo N.

I'm wondering if it is just a coincidence that the groups I've tested this on seem to fit this description, or at least that the order of the group is the same as the number of co primes to N (less than N).

If this is true and not just a coincidence, could anyone enlighten me on the deeper significance of this? I have a line in my project where I'm deriving Fermat's little theorem, I write:

"To derive Fermat's little theorem we simply state that under multiplication modulo P (with P being a prime number), that no numbers below P share a common factor with P and that means that all P-1 numbers less than P are co-prime to P and thus, all are inside G_P."

Is this statement true? And is it also true for composite modulo's?

Thank you for any help!

Answer 1

For every integer $N$, the elements that are invetible mod $N$ are exactly those which are prime to $N$. This is an easy application of Bézout relation. Next, the group $(\mathbb{Z}/N\mathbb{Z})^{*}$ of invertible elements mod $N$ is isomorphic to the product over primes dividing $N$ of $(\mathbb{Z}/p^\alpha\mathbb{Z})^{*}$ where $\alpha$ is the maximal power such that $p^\alpha$ divides $N$. One can show that $|(\mathbb{Z}/p^\alpha\mathbb{Z})^{*}|=p^\alpha-p^{\alpha-1}$, and hence $$|(\mathbb{Z}/N\mathbb{Z})^{*}|=\prod_{p\backslash N}(p^\alpha-p^{\alpha-1})=\phi(N).$$ The function $\phi$ is called Euler's totient function in the litterature.

Answer 2

In your group of multiplication modulo $N$, you need inverses to exist, so for any element $a$ you need an element $b$ such that $ab \equiv 1\pmod{N} \iff ab = 1 + Nm \iff ab -Nm = 1$.

But by Bezout, this implies $(a,N) = 1$. So they have to be coprime.

Answer 3

Let $\def\Z{\Bbb Z}A=\Z/n\Z$ denote the additive group of integers modulo$~n$. For every $k\in\Z$, the operation of multiplication by $k$ defines a map $m_k:A\to A$ (it is the unique homomorphism of groups that sends the class of$~1$ to the class of$~k$, that that will not be used here). Being a map from a finite set to itself, it is injective if and only if it is surjective (this related to the pigeonhole principle). Moreover when this is the case there exists (by surjectivity) an integer $l$ whose class in$~A$ is mapped to the class of$~1$, in other words $kl\equiv1\pmod n$ and $l$ is the inverse of$~k$ for multiplication modulo$~n$; conversely $kl\equiv1\pmod n$ implies that $m_k$ is bijective (with inverse$~m_l$). So the question is to find a condition on$~k$ corresponding to the fact that $m_k$ is surjective (or injective, or bijective, as they are all equivalent).

Now if $n$ and $k$ have a common divisor $d>1$, then the image of$~m_k$ is contained in the proper subgroup generated by the class of$~d$, so in particular $m_k$ is not surjective. Conversely if $m_k$ is not surjective, its image is a proper subgroup of $A$, and if $d>0$ is the minimal such that its class is in the image of$~m_k$, then $d\neq1$ and $d$ is a common divisor of $n$ and (since the class of $k$ is in the image of$~m_k$) of $k$. In conclusion $k$ has an inverse modulo$~n$ if and only if $n$ and$~k$ have no common divisors $d>1$, in other words if they are relatively prime.