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\\ &\iff-4x+y+6\equiv0\mod19\\ &\iff y\equiv4x-6\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 19z-4y-5$ we have $3\mid z-y+1$ and so $z-y+1 = 3t$ for some integer $t$. From here we get:

\begin{eqnarray} y&=& z-3t+1\\ x&=& 4t+5z-3 \end{eqnarray} So \begin{eqnarray} 0\leq& z-3t+1& \leq 18\\ 0\leq & 4t+5z-3&\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 (14-t)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
Author by

Jaideep Khare

Updated on August 01, 2022


  • Jaideep Khare
    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.


    • user340297
      user340297 about 6 years
      If $(a,b)$ is in $S$, then $(a+7,b-2)$ is also in $S$. So $S$ is either empty or it has inifinitely many elements.
    • user236182
      user236182 about 6 years
      @user340297 $3\cdot 7-4\cdot 2=21-8=13$ is not divisible by $19$. Also notice $0\le a,b\le 18$.
    • Raffaele
      Raffaele about 6 years
      They 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
    Aqua about 6 years
    Great +1..........