Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
2  
Try $n = 8$ ${}{}$ –  Cocopuffs Oct 29 '12 at 8:00
2  
This doesn't seem to fall under linear algebra or fields. –  EuYu Oct 29 '12 at 8:01
1  
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

2 Answers 2

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

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.