0
$\begingroup$

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 don't understand why. I can not prove this formula. Please help me.

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Thank you very much $\endgroup$ – Rogue Apr 7 at 10:21
  • $\begingroup$ @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. $\endgroup$ – John Omielan Apr 7 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.