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

$16+6x = k_1p$

$2x = 1 + k_2p$ =>

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

=> $p|19$

$\endgroup$
  • 1
    $\begingroup$ Thank you but please , give a hint next time :C $\endgroup$ – asddf Jan 19 '17 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$

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.