# 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$. – Joffan Jan 20 '17 at 3:31
• @Joffan Modulus, not base, is far more common in elementary number theory. – Bill Dubuque Jan 20 '17 at 4:03
• @Joffan Our of curiosity, where did you learn the term "base" for the modulus? – Bill Dubuque Jan 20 '17 at 4:07
• @BillDubuque No idea really - I guess I was just wrong. – Joffan Jan 20 '17 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. – Bill Dubuque Jan 20 '17 at 4:20

$16+6x = k_1p$
$2x = 1 + k_2p$ =>
$16 = -3 + (k_1 - 3k_2)p$
=> $p|19$
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$