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!

  • $\begingroup$ Do you know the Chinese remainder theorem? $\endgroup$ – saulspatz Apr 3 '18 at 19:16
  • $\begingroup$ Yes I do know the theorem. $\endgroup$ – Longti Apr 3 '18 at 19:16
  • $\begingroup$ 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$. $\endgroup$ – saulspatz Apr 3 '18 at 19:17
  • $\begingroup$ 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}$. $\endgroup$ – 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$$

We find by trial that

$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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.