# How can I find a prime that satisfies these two congruences?

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.

• Generally the Chinese remainder theorem would be applicable when you have multiple bases. Here you only have base $p$. Jan 20, 2017 at 3:31
• @Joffan Modulus, not base, is far more common in elementary number theory. Jan 20, 2017 at 4:03
• @Joffan Our of curiosity, where did you learn the term "base" for the modulus? Jan 20, 2017 at 4:07
• @BillDubuque No idea really - I guess I was just wrong. Jan 20, 2017 at 4:10
• @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. Jan 20, 2017 at 4:20

$16+6x = k_1p$

$2x = 1 + k_2p$ =>

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

=> $p|19$

• Thank you but please , give a hint next time :C Jan 19, 2017 at 20:58

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$

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 :)