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

This is my approach, but I think I'm wrong.

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

So, I observed 720 = 6!, so this must mean that:
n^2 ≡ 1 mod 6, and
n^2 ≡ 1 mod 5, and
n^2 ≡ 1 mod 4, and
n^2 ≡ 1 mod 3, and
n^2 ≡ 1 mod 2.

But here the modulos aren't relatively prime, so 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
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.

I have a strong feeling I completely screwed this up. Any help?

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.

Apart from that, everything looks good.

Ahh, thanks. 16 it is.