How can I show that for all k ∈ {0, 1, 2, ..., 18}, ∃a,b ∈ {0, 1, 2, ... , 9} such that 3a + 2b ≡ k (mod 19)?

Question

I'm trying to show that we can pick a pair of integers $0 ≤ a, b ≤ 9 $ such that $3a + 2b$ gives us a residue modulo 19, and we can find at least one (a, b) for each residue modulo 19

So far I've found that it is possible for $3a + 2b ≤ 18$ except for the case where $3a + 2b = 1$ so instead there is 3(2) + 2(7) = 20 ≡ 1 (mod 19)

I don't really see any "pattern" here so I'm wondering if there's a clean way to show that this is possible other than listing out a possible combination for each residue class?

Answer 1

For the numbers other than 1, you can check whether the sum should be even or odd. If k is even, just choose a=0 and b=k/2. If it's odd, choose a=1, and b=(k-3)/2.

Answer 2

We can make $2(1)+3(0)=2$ and $2(0)+3(1)=3$ and $2(2)+3(0)=4$. From here we can, within the limits of the problem, add a suitable number of $3$'s to get to any natural number up to and including $29$. Then from the way we've written $28=2(2)+3(8)$ and $29=2(1)+3(9)$ we can add a suitable number of $2$'s to get to any natural number up to and including $43$. This ought to cover all congruence classes modulo $19$.

The number $44$ is impossible, as it is $2(9)+3(9)-1$, and just as there is no way within the limitations of the problem to get $1$, there is no way to subtract $1$ from $45$.