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
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
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$.