Originally Posted by

**elemental** How many integers n are there such that 0 ≤ n ≤ 720 and n^2 ≡ 1 (mod 720)?

I prime factorized 720 and did:

n^2 ≡ 1 mod 16, and

n^2 ≡ 1 mod 9, and

n^2 ≡ 1 mod 5.

(Since 16*9*5 = 720)

Taking the modular square root, we observe that:

n ≡ 1 mod 16 OR n ≡ 15 mod 16, and What about n ≡ 7 and n ≡ 9 (mod 16)?

n ≡ 1 mod 9 OR n ≡ 8 mod 9, and

n ≡ 1 mod 5 OR n ≡ 4 mod 5.

We are guaranteed solutions from the CRT, since 16, 9, and 5 are coprime.

So we have 2*2*2 = 8 general solutions modulo 720, and hence

8 solutions under 720.