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.