# Find the number of solutions to a congruence equation

Problem: Find the number of solutions to the congruence equation $x^3 \equiv 1 \pmod{280}$.

Attempt: Since $280 = 2^3 \cdot 5 \cdot 7$, we know $x^3 \equiv 1 \pmod{280} \iff x^3 \equiv 1 \pmod{2^3}, x^3 \equiv 1 \pmod{5}$ and $x^3 \equiv 1 \pmod{7}$. I think we can say something about the number of solutions to each of the congruence equations using the fact that there exist primitive roots for $2^3, 5$ and $7$ respectively. However, I am not sure how the argument would go exactly... any help is appreciated!

• Do you know the Chinese remainder theorem? – saulspatz Apr 3 '18 at 19:16
• Yes I do know the theorem. – Longti Apr 3 '18 at 19:16
• Well by the Chinese remainder theorem, if you have a set of solutions to the 3 congruences, it gives rise to exactly one solution mod $280$. – saulspatz Apr 3 '18 at 19:17
• Yes that's what I did in the "Attempt" section. What I am trying to figure out is how many solutions I have for, for example, $x^3 \equiv 1 \pmod{5}$. – Longti Apr 3 '18 at 19:25

As you observed, $$x^3\equiv 1\pmod{280}\implies x^3\equiv 1\pmod k, k=5,7,8$$
$x^3\equiv 1\pmod 8$ has $4$ solutions
$x^3\equiv 1\pmod 5$ has $1$ solution
$x^3\equiv 1\pmod 7$ has $3$ solutions
By the Chinese remainder theorem, each combination of these solutions gives rise to a unique solution modulo 280, so there are $4\cdot1\cdot3=12$ solutions.