2
$\begingroup$

I have the following congruence equation: $x^{3} \equiv 3 \bmod(357035)$ which I'm having troubles solving.

The prime factorisation of $35705$ is $5\cdot 7 \cdot 101^{2}$. I thought I would solve the congruences \begin{align}x^{3} & \equiv 3 \bmod(5) \\ x^{3} & \equiv 3 \bmod(7) \\ x^{3} & \equiv 3 \bmod(101^{2})\end{align} using the Chinese Remainder Theorem, but I somehow ended up with the solution $x^{3} \equiv 3 \bmod(357035)$ which doesn't help me. Some hints or a detailed answer would be much appreciated.

$\endgroup$
  • $\begingroup$ You're right, that's wrong. That was sloppy of me, I'll make an edit. $\endgroup$ – Auclair Oct 6 '15 at 11:43
2
$\begingroup$

Not my strong suit, but just by testing, it appears the second condition is impossible. If $x\equiv0\pmod7, x^3\equiv0\pmod7$. Otherwise, by Fermat's Little Theorem

$$x^6\equiv1\pmod7$$ $$(x^3+1)(x^3-1)\equiv0\pmod7$$ $$x^3\equiv-1,1\pmod7$$

Therefore, there are no solutions.

$\endgroup$
  • $\begingroup$ Maybe I'm just slow today, but how did you arrive at $x \equiv 0 \bmod(7)$? $\endgroup$ – Auclair Oct 6 '15 at 11:50
  • $\begingroup$ @Auclair I think you missed the "if". If $x$ is a multiple of $7$, so is $x^3$. $\endgroup$ – Mike Oct 6 '15 at 11:56
  • $\begingroup$ Of course, yes I did miss it. Thank you, it makes much more sense to me now. $\endgroup$ – Auclair Oct 6 '15 at 17:03
2
$\begingroup$

It is easy verify that the cubes of $\mathbb {Z/7Z}$=$\mathbb F_7$ are just the $3$ elements $0,1,-1$. Hence $x^3\equiv 3$ has no solution.

$\endgroup$

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.