Linear Congruences and Diophantine Equations

Linear Congruences#

Recall from Bezouts Identity and the Extended Euclidean Algorithm the method for finding the inverse of an integer $a$ in $\mathbb{Z}_n$:

• Find $\gcd(a,n)$. If it is not $1$, there is no inverse.
• Find integers $x$ and $y$ such that $1 = ax + ny$, e.g. via the extended Euclidean algorithm.
• The inverse of $a$ in $\mathbb{Z}_n$ is the value of the coefficient $x$, reduced modulo $n$.

That method solves the congruence $ax \equiv 1 \pmod n$. The natural next question is the more general linear congruence

$$ax \equiv c \pmod n,$$

for given integers $a$ and $c$ and positive integer $n$; i.e. instead of asking "what undoes $a$", we are asking "what does $a$ send to $c$". We will look at two hands-on approaches first, and then build a general method that runs on the same EEA machinery as the inverse method.

Checking All Multiples#

This one is just brute force, so I'm not gonna say much; since $x$ only matters modulo $n$, there are only $n$ candidates to test, namely $x \in \{0, 1, \dots, n-1\}$.

Example. Find all solutions to the linear congruence $6x \equiv 4 \pmod 7$.
Testing every residue modulo $7$:

The only residue that works is $x = 3$, since $6 \times 3 = 18 = 2 \times 7 + 4$. Therefore, the congruence has exactly one solution, $x \equiv 3 \pmod 7$.

Example. Find all solutions to the linear congruence $6x \equiv 4 \pmod 8$.
Testing every residue modulo $8$:

This time two residues work. Therefore, the solutions are $x \equiv 2$ and $x \equiv 6 \pmod 8$; notice that these can be packaged as the single statement $x \equiv 2 \pmod 4$.

Example. Find all solutions to the linear congruence $6x \equiv 4 \pmod 9$.
Testing every residue modulo $9$:

The outputs only ever cycle through $\{0, 3, 6\}$ and never hit $4$. Therefore, this congruence has no solutions.

Notice how the same left-hand side against three different moduli produced one, two and zero solutions. Look at which values each table can reach: for $n=7$ we hit everything, for $n=8$ we only hit the even residues, and for $n=9$ we only hit the multiples of $3$. In each case the reachable values are exactly the multiples of $\gcd(6,n)$ (which is $1$, $2$ and $3$ respectively); this observation is basically the entire theory of linear congruences, and we will state it as a theorem shortly.

Using Rules of Modular Arithmetic#

Brute force dies quickly as $n$ grows, so the second approach is to massage the congruence using the standard rules of modular arithmetic; adding multiples of the modulus to either side, replacing numbers by anything congruent to them, and cancelling common factors (carefully).

Example. Solve the same three congruences again, this time using rules of modular arithmetic.
For the modulus $7$, notice that $6 \equiv -1 \pmod 7$, so

$$\begin{align*} 6x &\equiv 4 \pmod 7 \\ -x &\equiv 4 \pmod 7 \\ x &\equiv -4 \pmod 7 \\ x &\equiv 3 \pmod 7. \end{align*}$$

For the modulus $8$, every term and the modulus share a factor of $2$, so we may divide the whole congruence (modulus included) through by $2$, and then use $3 \equiv -1 \pmod 4$:

$$\begin{align*} 6x &\equiv 4 \pmod 8 \\ 3x &\equiv 2 \pmod 4 \\ -x &\equiv 2 \pmod 4 \\ x &\equiv -2 \pmod 4 \\ x &\equiv 2 \pmod 4, \end{align*}$$

which is $x \equiv 2$ or $6 \pmod 8$, agreeing with the table.
For the modulus $9$, suppose a solution existed. Then $9 \mid 6x - 4$, i.e. $6x - 9k = 4$ for some integer $k$. But $3 \mid 6x$ and $3 \mid 9k$, so $3$ divides the left-hand side, forcing $3 \mid 4$; this is false, so there are no solutions. Therefore, the three answers match the brute-force tables, with far less work.

It is important to remember that you can only cancel a common factor from both sides of a congruence if you also divide the modulus by the gcd of that factor and the modulus. Cancelling as if the modulus were untouched is probably the single most common error in this topic; here is what goes wrong.

Example. Find all solutions to $4x \equiv 8 \pmod{12}$.
The tempting (wrong) move is to cancel the $4$ and write $x \equiv 2 \pmod{12}$. But check $x = 5$:

$$\begin{align*} 4 \times 5 &= 20 \\ &= 12 + 8 \\ &\equiv 8 \pmod{12}, \end{align*}$$

so $x = 5$ is a perfectly good solution that the naive answer misses. The correct move: the factor being cancelled is $4$, and $\gcd(4, 12) = 4$, so the modulus must be divided by $4$ as well;

$$\begin{align*} 4x &\equiv 8 \pmod{12} \\ x &\equiv 2 \pmod 3. \end{align*}$$

As residues modulo $12$, this is $x \equiv 2, 5, 8, 11 \pmod{12}$. Therefore, there are four solutions modulo $12$, and the naive cancellation silently threw away three of them.

Existence and Number of Solutions#

The pattern spotted in the tables above is completely general.

Basically, $ax \equiv c \pmod n$ is just the statement that $ax + ny = c$ for some integer $y$; i.e. that $c$ is an integer linear combination of $a$ and $n$. We already know from Bezouts Identity and the Extended Euclidean Algorithm that the reachable values of such combinations are precisely the multiples of $d = \gcd(a,n)$; so if $d \nmid c$, the value $c$ is simply unreachable (this is exactly why the $6x \equiv 4 \pmod 9$ table never hit $4$: every output was a multiple of $3$).

As for the count: the solutions form one class $x \equiv x_0 \pmod{\frac{n}{d}}$, and a single class modulo $\frac{n}{d}$ splits into $d$ separate classes modulo $n$, namely

$$x_0, \quad x_0 + \tfrac{n}{d}, \quad x_0 + 2\tfrac{n}{d}, \quad \dots, \quad x_0 + (d-1)\tfrac{n}{d}.$$

You can see this in the $6x \equiv 4 \pmod 8$ example: $d = 2$, the answer was one class $x \equiv 2 \pmod 4$, and modulo $8$ that class splits into the $d = 2$ solutions $2$ and $6$.

A General Method for Solving Linear Congruences#

To solve $ax \equiv c \pmod n$ in general, first consider simplifying with the rules of modular arithmetic as above; if the numbers are too large for that to be practical, the following method always works:

• Find $d = \gcd(a,n)$. If $d \nmid c$, there is no solution; stop.
• Divide the congruence through by $d$ (modulus included) to get $\frac{a}{d}x \equiv \frac{c}{d} \pmod{\frac{n}{d}}$.
• Find the multiplicative inverse $x'$ of $\frac{a}{d}$ modulo $\frac{n}{d}$.
• The general solution is $x \equiv \frac{c}{d}x' \pmod{\frac{n}{d}}$.

Equivalently, run the EEA directly on $a$ and $n$ to find integers $x'$ and $y'$ such that $d = ax' + ny'$; dividing that identity by $d$ gives $1 = \frac{a}{d}x' + \frac{n}{d}y'$, which says precisely that this same $x'$ is the inverse of $\frac{a}{d}$ modulo $\frac{n}{d}$. Either way,

$$\boxed{x \equiv \frac{c}{d}x' \pmod{\frac{n}{d}}.}$$

If we want to list all $d$ solutions in the original modulus $n$, take the solution $\frac{c}{d}x'$ and repeatedly add $\frac{n}{d}$ until there are $d$ different values;

$$x \equiv \frac{c}{d}x' + \frac{n}{d}k \pmod n, \quad k \in \{0, 1, 2, \dots, d-1\}.$$

Reading Everything Off the EEA Table#

Almost all the information the method needs is already sitting in the EEA table for $a$ and $n$:

Usually we have $a < n$, so in practice the table is seeded with $n$ first and the roles of the two bottom rows swap. The safe habit is to identify $x'$ via the column property $r_i = (\text{first seed})x_i + (\text{second seed})y_i$; $x'$ is whichever entry multiplies $a$, not whichever row you memorised.

Notice also why the last column is always $\pm\frac{n}{d}$ and $\mp\frac{a}{d}$: that column has $r_i = 0$, so its entries satisfy $ax_i + ny_i = 0$, and after dividing by $d$ the smallest integer pair achieving $\frac{a}{d}x_i = -\frac{n}{d}y_i$ is $x_i = \pm\frac{n}{d}$, $y_i = \mp\frac{a}{d}$ (since $\frac{a}{d}$ and $\frac{n}{d}$ are coprime). This makes the last column a free arithmetic check on the whole table.

Example. Solve $111x \equiv 75 \pmod{321}$.
Run the EEA on $321$ and $111$:

So $d = \gcd(111, 321) = 3$, and $3 \mid 75$, so solutions exist. The second-last column gives

$$3 = 321 \times 9 + 111 \times (-26),$$

and since $x'$ is the coefficient of $a = 111$, we have $x' = -26$. (Quick check on the last column: $-37 = -\frac{111}{3}$ and $107 = \frac{321}{3}$, as promised.) Therefore,

$$\begin{align*} x &\equiv \frac{75}{3} \times (-26) \pmod{\frac{321}{3}} \\ &\equiv 25 \times (-26) \pmod{107} \\ &\equiv -650 \pmod{107} \\ &\equiv -650 + 7 \times 107 \pmod{107} \\ &\equiv 99 \pmod{107}. \end{align*}$$

Sanity check: $111 \times 99 = 10989 = 34 \times 321 + 75$. $\checkmark$ Therefore, the general solution is $x \equiv 99 \pmod{107}$; as the $d = 3$ separate solutions modulo the original modulus, $x \equiv 99, 206, 313 \pmod{321}$.

Alternatively, the rules of modular arithmetic crack this one with almost no work. Divide through by $d = 3$ (which divides the modulus too):

$$\begin{align*} 111x &\equiv 75 \pmod{321} \\ 37x &\equiv 25 \pmod{107} \\ 111x &\equiv 75 \pmod{107}, \text{ (multiplying by 3; fine since } \gcd(3,107)=1) \\ 4x &\equiv 75 \pmod{107}, \text{ (as } 111 \equiv 4 \pmod{107}) \\ 4x &\equiv 396 \pmod{107}, \text{ (adding } 3 \times 107 \text{ to reach a multiple of } 4) \\ x &\equiv 99 \pmod{107}, \end{align*}$$

cancelling the $4$ in the last step is legal because $\gcd(4, 107) = 1$. Same answer; it is always worth scanning for shortcuts like this before committing to a full table.

Example. Find all solutions to $14x \equiv 21 \pmod{35}$.
Here $d = \gcd(14, 35) = 7$ and $7 \mid 21$, so solutions exist and there will be seven of them modulo $35$. Divide everything through by $7$:

$$\begin{align*} 14x &\equiv 21 \pmod{35} \\ 2x &\equiv 3 \pmod 5 \\ x &\equiv 3 \times 3 \pmod 5, \text{ (as } 2^{-1} \equiv 3 \pmod 5\text{, since } 2\times 3 = 6 \equiv 1) \\ x &\equiv 9 \pmod 5 \\ x &\equiv 4 \pmod 5. \end{align*}$$

Sanity check: $14 \times 4 = 56 = 35 + 21$. $\checkmark$ Listing the solutions modulo the original modulus by repeatedly adding $\frac{35}{7} = 5$:

$$x \equiv 4, 9, 14, 19, 24, 29, 34 \pmod{35},$$

exactly $d = 7$ solutions, matching the existence theorem. Therefore, the general solution is $x \equiv 4 \pmod 5$.

Linear Diophantine Equations#

Basically, over the reals $ax + by = c$ is just a line with infinitely many points on it; the Diophantine question is which points on that line have both coordinates integers. The integer restriction is the entire difficulty (and the entire point).

The existence half is exactly the solvability theorem from Bezouts Identity and the Extended Euclidean Algorithm (the reachable values of $ax + by$ are precisely the multiples of $d$), so we only prove the description of the solution family.

Proof. First, every member of the family really is a solution; the two shifts cancel exactly:

$$\begin{align*} a\left(x_0 + \tfrac{b}{d}k\right) + b\left(y_0 - \tfrac{a}{d}k\right) &= ax_0 + by_0 + \tfrac{ab}{d}k - \tfrac{ab}{d}k \\ &= ax_0 + by_0 \\ &= c. \end{align*}$$

Conversely, no solutions are missed. Suppose $(x_1, y_1)$ is any solution; then subtracting $ax_0 + by_0 = c$ from $ax_1 + by_1 = c$,

$$\begin{align*} a(x_1 - x_0) + b(y_1 - y_0) &= 0 \\ a(x_1 - x_0) &= -b(y_1 - y_0) \\ \frac{a}{d}(x_1 - x_0) &= -\frac{b}{d}(y_1 - y_0), \text{ (dividing by } d). \end{align*}$$

Now $\frac{b}{d}$ divides the right-hand side, so it divides the left-hand side; but $\gcd\left(\frac{a}{d}, \frac{b}{d}\right) = 1$, so $\frac{b}{d}$ must divide $x_1 - x_0$ itself. Writing $x_1 - x_0 = \frac{b}{d}k$ for some $k \in \mathbb{Z}$ and substituting back,

$$\begin{align*} \frac{a}{d} \cdot \frac{b}{d}k &= -\frac{b}{d}(y_1 - y_0) \\ y_1 - y_0 &= -\frac{a}{d}k. \quad \blacksquare \end{align*}$$

Basically, once you have found one lattice point on the line, all the others are evenly spaced along it, with the $x$-coordinates stepping by $\frac{b}{d}$ and the $y$-coordinates stepping by $\frac{a}{d}$ in the opposite direction. So a full answer to a Diophantine question always has two ingredients: a particular solution, and the step sizes.

The general method for finding the integer solutions of $ax + by = c$ is:

• Consider the equation modulo $b$ (this eliminates the $by$ term, since $by \equiv 0 \pmod b$).
• Solve the resulting linear congruence $ax \equiv c \pmod b$.
• Write the solution for $x$ in terms of an arbitrary integer parameter $k$.
• Substitute this $x$ back into the original equation and solve for $y$ in terms of $k$.

Of course, we could equally consider the equation modulo $a$ and solve for $y$ first; pick whichever coefficient gives the easier congruence.

Example. Find all integer solutions to $6x + 9y = 4$.
Here $d = \gcd(6,9) = 3$, and $3 \nmid 4$; the left-hand side is always a multiple of $3$ no matter which integers are substituted, and $4$ is not. Therefore, there are no integer solutions. (Notice this is the same obstruction as the congruence $6x \equiv 4 \pmod 9$ from earlier; taking the equation mod $9$ produces exactly that unsolvable congruence.) Do not start hunting for particular solutions before the divisibility check passes.

Example. Find all integer solutions to $6x + 7y = 4$.
Now $\gcd(6,7) = 1$, which certainly divides $4$, so solutions exist. Consider the equation modulo $7$:

$$6x \equiv 4 \pmod 7,$$

which we solved at the start of this note; $x \equiv 3 \pmod 7$, i.e. $x = 3 + 7k$ for arbitrary $k \in \mathbb{Z}$. Substituting back into the original equation:

$$\begin{align*} 6(3 + 7k) + 7y &= 4 \\ 18 + 42k + 7y &= 4 \\ 7y &= -14 - 42k \\ y &= -2 - 6k. \end{align*}$$

Check with $k=0$: $6 \times 3 + 7 \times (-2) = 18 - 14 = 4$. $\checkmark$ Therefore, the complete set of solutions is

$$(x, y) = (3 + 7k, \; -2 - 6k), \quad k \in \mathbb{Z}.$$

(Taking the equation mod $6$ instead gives $7y \equiv 4 \pmod 6$, i.e. $y \equiv 4 \pmod 6$, and substituting back produces the same family; mod out by whichever coefficient you prefer.)

Solving Linear Diophantines with the EEA#

Just as with congruences, the EEA table for $a$ and $b$ contains everything at once: the gcd $d$ for the divisibility check, a Bézout pair $(x', y')$ with $d = ax' + by'$ in the second-last column, and the step sizes $\frac{b}{d}$ and $\frac{a}{d}$ sitting in the last column. Scaling the Bézout identity by $\frac{c}{d}$ gives the particular solution, and the theorem above gives the family:

$$\boxed{x = \frac{c}{d}x' + \frac{b}{d}k \quad \text{and} \quad y = \frac{c}{d}y' - \frac{a}{d}k, \quad k \in \mathbb{Z}.}$$

Example. Find all integer solutions to $6x + 7y = 4$, using the EEA instead.
The table is short enough to do by inspection: $7 - 6 = 1$, so

$$1 = 6 \times (-1) + 7 \times 1,$$

giving $d = 1$, $x' = -1$, $y' = 1$. Multiplying through by $\frac{c}{d} = 4$:

$$\begin{align*} 4 &= 6 \times (-4) + 7 \times 4, \end{align*}$$

so $(x_0, y_0) = (-4, 4)$ is a particular solution, and the steps are $\frac{b}{d} = 7$ and $\frac{a}{d} = 6$. Therefore,

$$(x, y) = (-4 + 7k, \; 4 - 6k), \quad k \in \mathbb{Z}.$$

This looks different from the answer in the previous section, but it is the same set; two correct general solutions can look completely different, differing only by a shift of the parameter. Replacing $k$ by $k+1$ here gives $(3 + 7k, -2 - 6k)$, exactly the earlier family. To confirm two families agree, check that they share a particular solution and have the same step sizes.

Example. Solve $533x + 182y = 481$ over the integers.
Run the EEA on $533$ and $182$:

So $d = \gcd(533, 182) = 13$, and $481 = 13 \times 37$, so solutions exist with $\frac{c}{d} = 37$. The second-last column gives

$$13 = 533 \times (-1) + 182 \times 3,$$

i.e. $x' = -1$ and $y' = 3$, and the last column confirms the steps $\frac{b}{d} = \frac{182}{13} = 14$ and $\frac{a}{d} = \frac{533}{13} = 41$. Scaling by $37$:

$$\begin{align*} x_0 &= 37 \times (-1) \\ &= -37, \\ y_0 &= 37 \times 3 \\ &= 111. \end{align*}$$

Check: $533 \times (-37) + 182 \times 111 = -19721 + 20202 = 481$. $\checkmark$ Therefore, the complete set of solutions is

$$(x, y) = (-37 + 14k, \; 111 - 41k), \quad k \in \mathbb{Z}.$$

Alternatively, by the congruence method: taking the equation modulo $182$,

$$\begin{align*} 533x &\equiv 481 \pmod{182} \\ 169x &\equiv 117 \pmod{182}, \text{ (reducing both numbers mod } 182) \\ 13x &\equiv 9 \pmod{14}, \text{ (dividing by } 13 = \gcd(169,182), \text{ modulus included}) \\ -x &\equiv 9 \pmod{14}, \text{ (as } 13 \equiv -1 \pmod{14}) \\ x &\equiv -9 \pmod{14} \\ x &\equiv 5 \pmod{14}, \end{align*}$$

so $x = 5 + 14k$. Substituting back:

$$\begin{align*} 533(5 + 14k) + 182y &= 481 \\ 2665 + 7462k + 182y &= 481 \\ 182y &= -2184 - 7462k \\ y &= -12 - 41k. \end{align*}$$

Therefore, $(x,y) = (5 + 14k, \; -12 - 41k)$; the same set as before, since replacing $k$ by $k + 3$ in the first family gives exactly this one.

One Congruence, Two Ways#

It is important to note that linear congruences and linear Diophantine equations are the same problem wearing different clothes; $ax \equiv c \pmod n$ says precisely that $ax + ny = c$ for some integer $y$. So any congruence can be attacked as an equation, and vice versa, and the answers must agree.

Example. Solve $5x \equiv 3 \pmod{11}$ (a) using a multiplicative inverse, and (b) as a Diophantine equation, and confirm the answers match.
(a) Since $\gcd(5,11) = 1$, the inverse of $5$ exists; by inspection $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$, so $5^{-1} \equiv 9$. Multiplying both sides by $9$:

$$\begin{align*} x &\equiv 9 \times 3 \pmod{11} \\ &\equiv 27 \pmod{11} \\ &\equiv 5 \pmod{11}. \end{align*}$$

(b) Rewrite the congruence as the equation $5x + 11y = 3$. By inspection (or a two-line EEA), $5 \times (-2) + 11 \times 1 = 1$; multiplying through by $3$ gives the particular solution $(x_0, y_0) = (-6, 3)$, and the steps are $\frac{b}{d} = 11$, $\frac{a}{d} = 5$. So

$$(x, y) = (-6 + 11k, \; 3 - 5k), \quad k \in \mathbb{Z}.$$

The $x$-values $-6 + 11k$ are exactly the congruence class $x \equiv 5 \pmod{11}$ (take $k = 1$), matching part (a). $\checkmark$ Therefore, both methods give $x \equiv 5 \pmod{11}$.

The decision between them: if the question only asks for $x$, the congruence machinery is leaner (you never compute or carry $y$); if the question is stated as an equation, or you genuinely need both unknowns, work with the Diophantine form. Either way the underlying computation is the same EEA table, so choose whichever bookkeeping you find harder to fumble.

Restrictions on Solutions#

Linear Diophantine equations often arise in contexts where the otherwise infinite solution set is restricted further; by far the most common restriction is that only positive (or non-negative) solutions make sense. The strategy is not to change the method at all: solve normally to get the complete family in terms of $k$, then impose the restrictions, which turn into inequalities on $k$; typically only finitely many integers $k$ survive.

Example. Find all positive integer solutions to $2x + 5y = 17$.
Since $\gcd(2,5) = 1 \mid 17$, solutions exist. Take the equation modulo $2$:

$$\begin{align*} 5y &\equiv 17 \pmod 2 \\ y &\equiv 1 \pmod 2, \text{ (as } 5 \equiv 1 \text{ and } 17 \equiv 1 \pmod 2), \end{align*}$$

so $y = 1 + 2k$. Substituting back:

$$\begin{align*} 2x + 5(1 + 2k) &= 17 \\ 2x &= 12 - 10k \\ x &= 6 - 5k. \end{align*}$$

The complete integer family is $(x,y) = (6 - 5k, \; 1 + 2k)$. Now impose positivity;

$$\begin{align*} x \geq 1 &\implies 6 - 5k \geq 1 \implies k \leq 1, \\ y \geq 1 &\implies 1 + 2k \geq 1 \implies k \geq 0, \end{align*}$$

so $k \in \{0, 1\}$, giving $(x,y) = (6,1)$ and $(1,3)$. Check: $2 \times 6 + 5 \times 1 = 17$ and $2 \times 1 + 5 \times 3 = 17$. $\checkmark$ Therefore, there are exactly two positive solutions, $(6, 1)$ and $(1, 3)$.

Example. A parcel requires exactly $\$1.35$ of postage, and you only have $20$c stamps and $25$c stamps. In how many ways can you make up the postage?
Working in cents, we need non-negative integer solutions to $20x + 25y = 135$. First, $\gcd(20, 25) = 5$ and $5 \mid 135$, so solutions exist; divide the whole equation by $5$ to keep the numbers small:

$$4x + 5y = 27.$$

Take this modulo $4$:

$$\begin{align*} 5y &\equiv 27 \pmod 4 \\ y &\equiv 3 \pmod 4, \text{ (as } 5 \equiv 1 \text{ and } 27 \equiv 3 \pmod 4), \end{align*}$$

so $y = 3 + 4k$. Substituting back:

$$\begin{align*} 4x + 5(3 + 4k) &= 27 \\ 4x &= 12 - 20k \\ x &= 3 - 5k. \end{align*}$$

Both stamp counts must be non-negative;

$$\begin{align*} x \geq 0 &\implies 3 - 5k \geq 0 \implies k \leq 0, \\ y \geq 0 &\implies 3 + 4k \geq 0 \implies k \geq 0, \end{align*}$$

which forces $k = 0$, i.e. $(x, y) = (3, 3)$. Check: $3 \times 20 + 3 \times 25 = 60 + 75 = 135$ cents. $\checkmark$ Therefore, there is exactly one way: three $20$c stamps and three $25$c stamps.

Example. How many positive integer solutions does $7x + 11y = 300$ have?
Since $\gcd(7,11) = 1 \mid 300$, solutions exist. Take the equation modulo $7$:

$$\begin{align*} 11y &\equiv 300 \pmod 7 \\ 4y &\equiv 6 \pmod 7, \text{ (as } 11 \equiv 4 \text{ and } 300 = 42 \times 7 + 6) \\ y &\equiv 2 \times 6 \pmod 7, \text{ (as } 4^{-1} \equiv 2 \pmod 7\text{, since } 4 \times 2 = 8 \equiv 1) \\ y &\equiv 12 \pmod 7 \\ y &\equiv 5 \pmod 7, \end{align*}$$

so $y = 5 + 7k$. Substituting back:

$$\begin{align*} 7x + 11(5 + 7k) &= 300 \\ 7x &= 245 - 77k \\ x &= 35 - 11k. \end{align*}$$

Imposing positivity;

$$\begin{align*} x \geq 1 &\implies 35 - 11k \geq 1 \implies k \leq \tfrac{34}{11} \implies k \leq 3, \\ y \geq 1 &\implies 5 + 7k \geq 1 \implies k \geq -\tfrac{4}{7} \implies k \geq 0, \end{align*}$$

so $k \in \{0, 1, 2, 3\}$, giving the solutions

$$(x, y) = (35, 5), \; (24, 12), \; (13, 19), \; (2, 26).$$

Check one: $7 \times 24 + 11 \times 12 = 168 + 132 = 300$. $\checkmark$ Therefore, there are exactly $4$ positive integer solutions.

Notice how in all of these, the restriction step is pure bookkeeping; once the family is parametrised, convert every condition into a bound on $k$, intersect the bounds, and count the surviving integers. When rounding the bounds on $k$, remember that $k \leq \frac{34}{11}$ means $k \leq 3$ (round the upper bound down) and $k \geq -\frac{4}{7}$ means $k \geq 0$ (round the lower bound up); rounding these the wrong way quietly adds or deletes a solution.