If $N$ is not a power of a prime, why does 1 have -1 as a root modulo $N$?

73 Views Asked by At

If integer $N$ is not a power of a prime, it is the product of two coprime integer numbers greater than 1. As a consequence of the Chinese remainder theorem, the number 1 has at least four distinct roots modulo $N$, two of them being $1$ and $-1$. (From Wikipedia: Shor's_algorithm)

Can anyone explain why does 1 have -1 as a root modulo $N$? Thanks.

2

There are 2 best solutions below

0
On

$-1$ is always a square root of $1$, since $(-1)(-1)=1$. It's also a fourth root, sixth root, eight root, etc., for the same reason.

2
On

The statement is false. Note that the congruence $x^2\equiv 1\pmod{6}$ has only two solutions. The same is true for all numbers of the form $2p^k$, where $p$ is an odd prime and $k\ge 1$.