# Linear equations ordered pairs LCM trick

I'm sorry for bad English. I am student in Turkey. In here, there is a trick for linear equations' ordered pairs, mentioned many textbooks. I want to explain:

If x and y are natural numbers

ax+by=c

c/a and c/b integers

Number of ordered pairs that satisfy this equation can be find with that way:

[c/LCM(a, b)]+1

If x and y are positive integers

[c/LCM(a, b)]-1

For example

x and y are natural numbers

3x+5y=120

How many ordered pairs (x, y) integers for given equation?

[120/LCM(3, 5)]+1=[120/15]+1=9

If x and y would be positive integers

[120/LCM(3,5)]-1=7

I assume that $$a,b,c$$ are all supposed to be positive integers in

$$ax + by = c \tag{1}\label{eq1}$$

Let $$(x_0,y_0)$$ be a solution and let $$(x_1,y_1)$$ be the solution with the next larger integer value of $$x_1$$. Thus,

$$ax_0 + by_0 = c \tag{1}\label{eq2}$$ $$ax_1 + by_1 = c \tag{2}\label{eq3}$$

Next, \eqref{eq3} - \eqref{eq2} gives

$$a(x_1 - x_0) + b(y_1 - y_0) = 0 \tag{4}\label{eq4}$$

This shows that any factors of $$b$$ which are not a factor of $$a$$ must divide $$x_1 - x_0$$. The set of these factors is $$\frac{\text{lcm}(a,b)}{a}$$. Thus, the smallest positive value which $$x_1 - x_0$$ is

$$x_1 - x_0 = \frac{\text{lcm}(a,b)}{a} \tag{5}\label{eq5}$$

Substituting this into \eqref{eq4} gives

$$y_1 - y_0 = -\frac{\text{lcm}(a,b)}{b} \tag{6}\label{eq6}$$

This shows the values of $$x$$ increase by $$\frac{\text{lcm}(a,\, b)}{a}$$ for each next solution (while $$y$$ decreases by $$\frac{\text{lcm}(a,\, b)}{b}$$). Thus, if $$x_{\text{min}}$$ is the minimum value, and $$x_{\text{max}}$$ is the maximum value, of $$x$$ which are solutions for the equation, you can determine the total number of solutions as being $$x_{\text{max}} - x_{\text{min}}$$ divided by $$\frac{\text{lcm}(a,\, b)}{a}$$, and add $$1$$ (as the values are inclusive).

Since $$\frac{c}{b}$$ is an integer, this means that if $$y = \frac{c}{b}$$, then \eqref{eq1} gives that $$x = 0$$. Thus, among non-negative integers, $$x_{\text{min}} = 0$$. Similarly, since $$\frac{c}{a}$$ is also an integer, then $$x = \frac{c}{a}$$ gives that $$y = 0$$ in \eqref{eq1}. Thus, $$x_{\text{max}} = \frac{c}{a}$$. As such, the number of solutions would be

$$\frac{c/a}{\text{lcm}(a,b)/a} + 1 = \frac{c}{\text{lcm}(a,b)} + 1 \tag{7}\label{eq7}$$

If you only allow positive value solutions, then neither the smallest value of $$x = 0$$ is not allowed, nor the largest value of $$x$$ (as it causes $$y$$ to be $$0$$), are included, meaning there are $$2$$ less solutions, giving the total number then as being

$$\frac{c}{\text{lcm}(a,b)} - 1 \tag{8}\label{eq8}$$

• Thank you very much – Rogue Apr 7 at 10:21
• @Rogue You are welcome. If you think it's resolved your question, please consider clicking on the check mark beside this answer to indicate it's your accepted answer. Thanks. – John Omielan Apr 7 at 10:24