# Linear Algebra Fields question

I have the following statement (which is false) and I'm trying to understand why, I can't find a concrete example.

If $a$ belongs to $Z_n$ and $a^2 = 1$ then $a=1$ or $a=-1$

Can someone give me a direction?

Guy

-
Try to utilize $x^2 - 1 = (x+1)(x-1)$ to try to derive a counterexample. You want $n|(x+1)(x-1)$ but it does not divide either of those two factors. – dinoboy Oct 29 '12 at 7:57
Try $n = 8$ ${}{}$ – Cocopuffs Oct 29 '12 at 8:00
This doesn't seem to fall under linear algebra or fields. – EuYu Oct 29 '12 at 8:01
Try picking $a$ before picking $n$. – Hurkyl Oct 29 '12 at 8:03
@dinoboy, I'm sorry but didn't understand how should I proceed from there. – SyndicatorBBB Oct 29 '12 at 8:03

We already have trouble at $n=8$. For $3^2$ and $5^2$ are each congruent to $1$ modulo $8$. So the elements "$3$" and "$5$" of $\mathbb{Z}_8$ each have square equal to $1$.

There is also trouble of a somewhat different kind at $n=15$. For example, $4^2\equiv 1\pmod{15}$, and $11^2\equiv 1\pmod{15}$.

We do a partial analysis for $n$ odd. If $n=p^k$, where $p$ is an odd prime, and $x^2-1\equiv 0\pmod n$, then $p^k$ divides $(x-1)(x+1)$. So $p$ divides at least one of $x-1$ and $x+1$. But $p$ cannot divide both, so $p^k$ divides $x-1$ or $p^k$ divides $x+1$, meaning that as an element of $\mathbb{Z}_n$, we have $x=1$ or $x=-1$. Thus we will find no counterexample among powers of odd primes.

If $n$ is odd and divisible by two distinct primes $p$ and $q$, let $n=p^k m$, where $p$ does not divide $m$. By the Chinese Remainder Theorem we can find an $x$ such that $x\equiv 1\pmod{p^k}$ and $x\equiv -1\pmod{m}$. Then $x$, as an element of $\mathbb{Z}_n$, is neither equal to $1$ nor to $-1$.

It turns out that if $n$ is odd and has $d$ distinct prime factors, then the equation $x^2=1$ has $2^d$ solutions in $\mathbb{Z}_n$.

I would suggest that based on the information above, you construct your own counterexamples.

A complete analysis for even $n$ is somewhat more complicated, but goes on roughly similar lines. The main difference is that if $n$ is a power of $2$ which is $\ge 2^3$, then the equation $x^2=1$ has $4$ solutions in $\mathbb{Z}_n$. For $n=2m$ where $m$ is odd and has $d$ distinct prime divisors, the equation $x^1=1$ has $2^d$ solutions in $\mathbb{Z}_n$. For $n=4m$, there are $2^{d+1}$, and for $n=2^am$ where $a\ge 3$, there are $2^{d+2}$.

-

The statement does hold when the structure is a field, i.e. when $n$ is prime. The statement is false for some composite $n$. For example, consider any $n$ of the form $x(x+2)$ for some $x\in\mathbb{N}^+$ then we will have $$(x+1)^2 \equiv x^2 + 2x + 1 \equiv n + 1 \equiv 1 \pmod n$$ so that $\pm(x+1)$ is a solution in addition to $\pm1$.

-
The formulation "otherwise, there will exist $n$" is a bit confusing, since "otherwise" refers to the case where the structure is not a field, i.e. $n$ is not a prime, but that implies that $n$ has already been fixed. I think it would be clearer to just say "The statement is false for some composite $n$." or something like that. – joriki Oct 29 '12 at 8:19
@joriki Hmm, it does sound a bit weird in hindsight. Let me try to rephrase it. – EuYu Oct 29 '12 at 8:20