Why can't we have an $y$ such that $xy\equiv 1\; (mod\; n)$ when $n$ is not prime?

Question

I'm reading Avner's Fearless Symmetry:

Here he says that we can only have the cancelation law if the modulus is prime:

I got curious with the statement and then I kept reading the chapter:

Then I've checked the definition and made two tables, trying to look if I could really find the $y$ such that $xy \equiv 1 \; (mod \;n)$, with $n$ not a prime. My tiny experiment yields:

I'm very curious in two points:

• Why can't we have an $y$ such that $xy\equiv 1\; (mod\; n)$ when $n$ is not prime? The answer may be trivial, but I can't find it.
• Later in the book (see below), he tells that it is possible to have a field with a composite number of elements, in this case I guess that the statement made in the last question doesn't hold. So, considering the need of the existence of an $y$ such that $xy\equiv 1\; (mod\; n)$ when $n$ is not prime, how's it possible to have a composite number of elements?

Answer 1

First question: suppose that $n=pq$, where $p$ and $q$ are greater than $1$. Then, if $x$ is a multiple of $p$, $x=kp$, every multiple of $x$ will be a multiple of $p$. Hence, $xy$ will be a multiple of $p$ and $xy-1$ can't be a multiple of $n$. Of course there can be some numbers $x$ that has an inverse mod $n$, but these numbers must be relatively prime with $n$.

Second question: finite fields can have a composite cardinal because they needn't be cyclic (that is, the sequence $1, 1+1, 1+1+1, \ldots$ needn't contain every element of the field). Take, for example, the field $\Bbb F_4=\{0,1,x,x+1\}$, where $1+1=x+x=0$ and $x^2=1$. The former argument doesn't work here, since $x$ is not a "normal" number, neither a remainder of any division. It is an abstract "thing" like $i$, the imaginary unit.

These arguments are rather intuitive, because I felt that you are asking for this kind of arguments. I hope that they are useful to you.

Answer 2

There can certainly be some $x$ for which there is an $y$ with $xy \equiv 1 \,(\textrm{mod } n)$, even if $n$ is not prime. In fact, one can show for arbitrary $n$ that $$ \text{There is an $y$ with } xy \equiv 1 \,(\textrm{mod } p) \quad\Leftrightarrow\quad \textrm{gcd}(x,n) = 1 \text{.} $$

However, if $n$ is not prime, then there is always some $x < n$, $x \geq 1$ with $\textrm{gcd}(x,n) \neq 1$ (just pick one of the factors of $n$ as $x$), and so we never have that for all $x \neq 0$ there is an $y$ with $xy \equiv 1 \,(\textrm{mod }n)$. But we also always find some $x$ for which $\textrm{gcd}(x,n) = 1$ even $n$ isn't prime, take for example $x = n-1$. (This comes down to saying that $(-1)^2 \equiv 1 \,(\textrm{mod }n)$ for all $n$).

If, on the other hand, $n$ is prime, then $\textrm{gcd }(x,n) = 1$ for all $x < n$, $x \geq $, therefore in this case we indeed have that for all $x \neq 0$ there is an $y$ with $xy \equiv 1 \,(\textrm{mod }n)$.