-1

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!

Jaideep Khare
  • 19,293
  • 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. – user340297 Oct 30 '17 at 19:04
  • 1
    @user340297 $3\cdot 7-4\cdot 2=21-8=13$ is not divisible by $19$. Also notice $0\le a,b\le 18$. – user236182 Oct 30 '17 at 19:14
  • 1
    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)$$ – Raffaele Oct 30 '17 at 19:49

3 Answers3

2

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.

Barry Cipra
  • 79,832
1

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.

...

nonuser
  • 90,026
1

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

Kal S.
  • 3,781