Finding all solutions to $3x + 4y \equiv 1 \pmod 7$

Question

Find all solutions $\pmod 7$: $3x + 4y$ is congruent to $1 \pmod 7$.

I have tried writing out the various equations such as $3x + 4y = 1$, $3x + 4y = 8$, $3x + 4y = 15$, etc., but I do not know how to find the finite solution.

Answer 1

Consider the equation $$ 3x + 4y = 1 (\mod 7).$$ $ (3,4,1) = 1 | 7$, so there are $7\times 1 = 7$ solutions mod $7$. I’ll solve the equation using a reduction trick. The given equation is equivalent to $3x + 4y + 7z = 1$ for some $z$. Set $$ w=\frac {3x+4y}{(3,4)} $$. Then $(3,4)w + 7z = 1, w + 7z = 1$. $w_0 = -6, z_0 = 1$ is a particular solution. The general solution is $w = −6 + 7s, z = 1 − s$. Substitute for $w$: $$ \frac {3x+4y}{(3,4)} =-6+7s$$, $$\Rightarrow 3x + 4y = −6 + 7s$$ $x_0 = -2, y_0 = \frac{7s}{4}$, is a particular solution. The general solution is $x = -2 + 4t, y = \frac {7s}{4}-3t $. $t = 0, 1, . . ., 6$ will produce distinct values of y mod 7. Note, however, that $s$ and $s + r$ produce $7s$ and $7s + 7r$, which are congruent mod $7$. That is, adding a multiple of $1$ to a given value of $s$ makes the $7s$ term in $x$ repeat itself mod $7$. So I can get all possibilities for $x$ mod $7$ by letting $s = 0$. All together, the distinct solutions mod $7$ are:

$$ x = -2 + 4t, y = \frac{7s}{4}-3t$$

where $s = 0$ and $t = 0,1...6$. Hope it helps you.

Answer 2

Hint: for any $x,y $ we always have $3x+4y=3 (x+4)+4 (y-3) $.

So by induction:

$3x+4y\equiv 1 \mod 7 \implies 3 (x\pm 4k)+4 (y\mp 3k)\equiv 1 \mod 7$

So... if you know one solution, you know infinitely many.

The question is are there any not generated from your first solution? (I.e. can we make that $\implies $ into $\iff $?)