How to solve the congruence equation $6x+y \equiv 19 \pmod {26}$?

Question

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?

score 3 · Accepted Answer · answered May 02 '19 at 14:48

3

$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}$

answered May 02 '19 at 14:48

lab bhattacharjee

274,582

So, there are $12+1$ possibilities – lab bhattacharjee May 02 '19 at 14:54
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 – AleWolf May 02 '19 at 15:15
@Ale, we can write $$6x+y-19=26k\iff y=2(13k-3x+9)+1$$ for some integer $k$ – lab bhattacharjee May 02 '19 at 15:22
Thanks so much, very clear now :) – AleWolf May 02 '19 at 15:36
ps: is it by intuition the way you proceded ? – AleWolf May 02 '19 at 15:40
1

@Ale, when the modulus is composite, try taking modulus of the prime factors & their powers – lab bhattacharjee May 02 '19 at 20:06

How to solve the congruence equation $6x+y \equiv 19 \pmod {26}$?

1 Answers1