1
$\begingroup$

I'm trying to solve $$x^2 - 3x - 5 \equiv 0 \pmod{343}$$

I've tried to look up similar problems on the Internet [1] but most of them use Hensel's Lemma which I cannot use as it wasn't introduced by my professor.

The problem is that I cannot transform $x^2 - 3x - 5$ into any familiar form I'd be able to solve. Plus, I've found that $x\in\{1,2\}$ for $x^2 - 3x - 5 \equiv 0 \pmod{7}$. How can I approach this congruence?

$\endgroup$
  • 1
    $\begingroup$ Try completing the square! $\endgroup$ – JavaMan Jun 15 '17 at 19:21
  • 1
    $\begingroup$ @JavaMan Good hint! I forgot about it. $\endgroup$ – Mateusz Piotrowski Jun 15 '17 at 19:22
  • 1
    $\begingroup$ So, in the first case $x \equiv 1\pmod{7}$, write $x = 1+7a$, so then $343 \mid (49a^2 + 14a + 1) - (3 + 21a) - 5 = 49a^2 - 7a - 7$. Thus $49 \mid 7a^2 - a - 1$ so $7 \mid -a-1$ which tells you $a \equiv 6\pmod{7}$, and therefore $x \equiv 43 \pmod{49}$. Then, similarly, you can write $x = 43 + 49b$ and substitute to figure out what $x$ is congruent to $\pmod{343}$. $\endgroup$ – Daniel Schepler Jun 15 '17 at 19:25
  • 1
    $\begingroup$ Then repeat for the case $x \equiv 2\pmod{7}$. $\endgroup$ – Daniel Schepler Jun 15 '17 at 19:26
  • 1
    $\begingroup$ See my answer here for how to solve quadratic congruences in general. In this case, though, we get $(2x-3)^2\equiv 29\pmod{7^3}$, which doesn't seem to make the problem easier. $29$ is a quadratic residue mod $7^3$. $\endgroup$ – user236182 Jun 15 '17 at 20:25

Your Answer

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

Browse other questions tagged or ask your own question.