2
$\begingroup$

Hi I was solving a question and now I'm stuck at this part .

$-6x\equiv 16 \pmod p $

$2x\equiv 1 \pmod p $

where $p$ is a prime number.

I need to find all prime numbers that satisfy these congruences.

I think that Chinese remainder theorem might help somehow but I don't see it.

$\endgroup$
6
  • $\begingroup$ Generally the Chinese remainder theorem would be applicable when you have multiple bases. Here you only have base $p$. $\endgroup$
    – Joffan
    Jan 20, 2017 at 3:31
  • 1
    $\begingroup$ @Joffan Modulus, not base, is far more common in elementary number theory. $\endgroup$ Jan 20, 2017 at 4:03
  • $\begingroup$ @Joffan Our of curiosity, where did you learn the term "base" for the modulus? $\endgroup$ Jan 20, 2017 at 4:07
  • $\begingroup$ @BillDubuque No idea really - I guess I was just wrong. $\endgroup$
    – Joffan
    Jan 20, 2017 at 4:10
  • $\begingroup$ @Joffan It might be due to a language translation error, or some other mistake that has been propagated on the web. The only mention I saw in the first few pages of a Google search was on a Tutors in China site which defines "congruence modulo n" as "Arithmetics where 2 quantities differing by a multiple of the chosen base n are considered the same..." I don't recall ever seeing "base" used before. $\endgroup$ Jan 20, 2017 at 4:20

3 Answers 3

2
$\begingroup$

$16+6x = k_1p$

$2x = 1 + k_2p$ =>

$16 = -3 + (k_1 - 3k_2)p$

=> $p|19$

$\endgroup$
1
  • 1
    $\begingroup$ Thank you but please , give a hint next time :C $\endgroup$
    – asddf
    Jan 19, 2017 at 20:58
2
$\begingroup$

Eliminate $\,x,\ $ e.g. $\ {\rm mod}\ p\!:\,\ 16 \equiv -3(\color{#c00}{2x})\equiv -3(\color{#c00}{\bf 1})\,\Rightarrow\, 16\!+\!3\equiv 0\,\Rightarrow\,p\mid 19$

$\endgroup$
1
$\begingroup$

We are given the two congruences: $$-6x\equiv 16\ (\mathrm{mod}\ p)\qquad(*)$$ $$2x\equiv 1\ (\mathrm{mod}\ p)\qquad(**)$$ We multiply $(**)$ by $3$ and add the resulting to $(*)$, to get $$0\equiv 19\ (\mathrm{mod}\ p)$$ This is possible only when $p=19$ or $p$ is a factor of $19$, which is not possible. Hence, the only value of $p$ satisfying the congruences is $19$.

If this doesn't seem good to you, then we have $$16\equiv-6x\equiv -3(2x)\equiv-3 (\mathrm{mod}\ p)$$ $$\implies0\equiv19\ (\mathrm{mod}\ p)$$ which is the same as above.

Hope it helps :)

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