Number of ordered pairs $(x, y)$ such that $0 \leq x, y\leq 18$ and $3x+4y+5$ is divisible by $19$

Question

The problem would have been much simpler if there was no constant term, (like $3x+4y$ divisible by 19) because then all the solutions could have been generated from just the solution to $3x+4y=19$.

I tried many things, one of which was painful enumeration. The following are the solutions to $3x+4y+5=19k$ as ordered triplets $(x, y, k)$

( 0, 13, 3 ) ( 1, 17, 4 ) ( 2, 2, 1 ) ( 3, 6, 2 ) ( 4, 10, 3 ) ( 5, 14, 4 ) ( 6, 18, 5 ) ( 7, 3, 2 ) ( 8, 7, 3 ) ( 9, 11, 4 ) ( 10, 15, 5 ) ( 11, 0, 2 ) ( 12, 4, 3 ) ( 13, 8, 4 ) ( 14, 12, 5 ) ( 15, 16, 6 ) ( 16, 1, 3 ) ( 17, 5, 4 ) ( 18, 9, 5 )

Clearly there are 19 ordered pairs, one for each $x$ from $0$ to $18$. Why is this so? I mean, why is it that there is one and only one ordered pair for each $x$ ? I think there is one ordered pair for a particular $x$ in every $19$ consecutive numbers for $y$, for example $1$ in $0$ to $18$ another in $2$ to $20$ ...

Moreover, how can we conclude that there will always be some ordered pair for every $x$ ?

Also I saw that this is not special to $19$, it happens for all numbers. I feel like I'm missing something big here.

Any help would be appreciated.

Answer 1

Hint: We are looking for solutions of $3x+4y+5\equiv 0\pmod{19}$. Equivalently (multiply by $5$) we are solving $15x+y=\equiv -6\pmod{19}$, or equivalently $y\equiv 4x-6\pmod{19}$. Now it is clear that for every $x$ there is a unique $y$ in the interval $0$ to $18$ for which the congruence holds. It is the remainder when $4x-6$ is divided by $19$.

Answer 2

Note that $3x+4y+5$ is divisible by $19$ if and only if $5(3x+4y+5)=15x+20y+25$ is divisible by $19$, if and only if $15x+y+6$ is divisible by $19$. So given $x$, you can compute $y$ by computing $4x+13$ modulo $19$ to get $y$.

You can do this because $4$ is relatively prime to $19$. In general, given $a,b,n$, if $b$ and $n$ are relatively prime then the number of pairs $0\leq x,y<n$ such that $ax+by+c$ is divisible by $n$ is $n$.

That's because there is a $b'$ so that $bb'=1+nk$ for some $k$ and $ax+by+c$ is divisible by $n$ if and only if $ab'x+bb'y+cb'$ is divisible by $n$ if and oly if $y+(ab'x+cb')$ is divisible by $n$. So there is exactly one $y$ for each $x$.