Find the pairs $(x,y) ; 0 \le x,y \le 18$ such that $19 \vert 3x+4y+5$
Solution 1
Since $19$ is a prime, we have
$$\begin{align} 3x+4y+5\equiv0\mod19 &\iff15x+20y+25\equiv0\mod19\\ &\iff4x+y+6\equiv0\mod19\\ &\iff y\equiv4x6\mod19 \end{align}$$
Hence each value of $x$ from $0$ to $18$ gives precisely one value of $y$ in the same range, e.g., $x=15\implies y\equiv54\equiv16$ mod $19$. So there are precisely $19$ elements of $S$ satisfying the equation.
Solution 2
Write $3x+4y+5=19z$
First we see that $1\leq z\leq 6$. Since $3\mid 19z4y5$ we have $3\mid zy+1$ and so $zy+1 = 3t$ for some integer $t$. From here we get:
\begin{eqnarray} y&=& z3t+1\\ x&=& 4t+5z3 \end{eqnarray} So \begin{eqnarray} 0\leq& z3t+1& \leq 18\\ 0\leq & 4t+5z3&\leq 18 \end{eqnarray}
Case 1: $z=1$ then $t= 0$ so $1$ solution $x= 2$ and $y=2$.
Case 2: $z=2$ then $2\leq t\leq 1$ so $4$ solution.
Case 3: $z=3$ then $?\leq t\leq ?$ so $?$ solution.
...
Solution 3
$$ 3x+4y \equiv 14 \pmod{19} $$
To find a solution we start by searching for a solution of $$ 3x \equiv 1 \pmod{19}\\ 4y \equiv 1 \pmod{19} $$ A solution is given by $x_0=13,y_0=5$. Then the solution of the original modular equation is given by: $$ x\equiv tx_0 \pmod{19}, \qquad y\equiv (14t)y_0 \pmod{19}, $$ for $0 \leq t\leq 18$. See relevant post.
For example for $t=0$ we get the pair $(0,13)$ as a solution and for $t=1$ we get $(13,8)$. Can you continue from here?
$$ t=0 \rightarrow (0,13)\\ t=1 \rightarrow (13,8)\\ t=2 \rightarrow (7,3)\\ t=3 \rightarrow (1,17)\\ \dots\\ $$
Related videos on Youtube
Jaideep Khare
Updated on August 01, 2022Comments

Jaideep Khare over 1 year
Let $\mathrm S ={(a,b) : a,b \in \mathbb Z, 0\le a,b \le 18}$. Find the number of elements in $\mathrm S$ such that $3x+4y+5$ is divisible by $19$.
I tried using congruences to simplify the problem.
We need $$3x+4y \equiv 5 \pmod{19} \equiv 14 \pmod{19}$$
I wrote $3x+4y \equiv 3(2)+4(2) \pmod{19}$. But I am not able to conclude anything from this. I know that if we find $(x,y)$ such that $x \equiv 2 \pmod {19}, y \equiv 2 \pmod{19}$ will satisfy the criteria, but will only these? I am stuck here. Please help me with proceeding in this solution or any other solution will also work.
Thanks!

user340297 about 6 yearsIf $(a,b)$ is in $S$, then $(a+7,b2)$ is also in $S$. So $S$ is either empty or it has inifinitely many elements.

user236182 about 6 years@user340297 $3\cdot 74\cdot 2=218=13$ is not divisible by $19$. Also notice $0\le a,b\le 18$.

Raffaele about 6 yearsThey are $19$ $$(0,\,13),\,(1,\,17),\,(2,\,2),\,(3,\,6),\,(4,\,10),\,(5,\,14),\,(6,\,18),\,(7,\,3),\,(8,\,7),\,(9,\,11),\,(10,\,15),\,(11,\,0),\,(12,\,4),\,(13,\,8),\,(14,\,12),\,(15,\,16),\,(16,\,1),\,(17,\,5),\,(18,\,9)$$


Aqua about 6 yearsGreat +1..........