0
$\begingroup$

I have the congruence equation:

$$6x+y \equiv 19 \pmod{26}$$

One way to solve it is to start from:

$$y \equiv 19-6x \space \pmod{26}$$

and try all the $y\in \left \{ 0,\dots,25 \right \}$. However my book states that there exist only $12$ possibilities for $x$, so I think the congruence equation $6x+y \equiv 19 \pmod{26}$ can be simplified. However I didn't succeed in doing it, can you help me?

$\endgroup$
3
$\begingroup$

$6x+y-19$ is to be divisible by $26$

hence $6x+y\equiv19\pmod2$

$\implies y\equiv1\pmod2$

If $y=2z+1, 6x+2z+1\equiv19\pmod{26}$

$\iff z\equiv9-3x\pmod{13}$

$\endgroup$
6
  • $\begingroup$ So, there are $12+1$ possibilities $\endgroup$ – lab bhattacharjee May 2 '19 at 14:54
  • $\begingroup$ I'm very sorry but I started today studying modular arithmetic and I don't understand the passages of your calculations, can you add more details? Thanks so much $\endgroup$ – AleWolf May 2 '19 at 15:15
  • $\begingroup$ @Ale, we can write $$6x+y-19=26k\iff y=2(13k-3x+9)+1$$ for some integer $k$ $\endgroup$ – lab bhattacharjee May 2 '19 at 15:22
  • $\begingroup$ Thanks so much, very clear now :) $\endgroup$ – AleWolf May 2 '19 at 15:36
  • 1
    $\begingroup$ @Ale, when the modulus is composite, try taking modulus of the prime factors & their powers $\endgroup$ – lab bhattacharjee May 2 '19 at 20:06

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.