$a^2\equiv1 \pmod n$ iff $a\equiv\pm\,1\pmod p$ for all $p\mid n$

Question

(Not)if $a$ is an integer and $n$ a postive integer, then $a\equiv\pm 1\pmod p$ for all primes dividing n if and only if $$a^2\equiv 1\pmod n$$

$\Longrightarrow $ is wrong,Tonyk note count-example $a=4,p=3,n=9$

if $a^2\equiv 1\pmod n,\Longrightarrow (a,n)=1,$,since $p|n$,then we have $$a^2\equiv 1\pmod p$$then we have $$a\equiv \pm 1\pmod p?$$

My solution is right? if not,then How prove it?

Answer 1

How about using the definition of modular arithmetic:

Let $p$ be an odd prime.

So, we have $a^2 \equiv 1 \bmod p$. Let's subtract 1, we get: $$a^2-1 \equiv 0 \bmod p$$

We can use the basic rules of factoring here, and the definition of modular arithmetic:

$$p | a^2-1 \implies p | (a-1)(a+1)$$

Now, let us assume that we are dealing with an odd prime p, and it is easy to convince yourself that p cannot divide both $a+1$ and $a-1$, in which case it is one or the other. Either way, you are left with the result:

$$a \equiv \pm 1 \bmod p$$