NT: Linear Combinations

 Theorem 1. Given integers $a$, $b$, and $c$ with $a$ and $b$ not both $0$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=c$ if and only if $(a,b)|c$.

Proof. Left as an exercise. See Number Theory Problem Set 2 #4.

Corollary. Let $a$ and $b$ be integers. Then there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$ if and only if $(a,b)=1$ i.e. $a$ and $b$ are relatively prime.

Corollary. Let $a,a',b\in\mathbb{Z}$. If $(a,b)=1$ and $(a',b)=1$, then $(aa',b)=1$.

Proof. Since $(a,b)=1$ and $(a',b)=1$, there exist $x,y,x',y'\in\mathbb{Z}$ such that $ax+by=1$ and $a'x'+by'=1$. Now,
 \begin{align*}
  1&=(ax+by)(a'x'+by')\\
   &=aa'xx'+b(axy'+a'x'y+byy')
 \end{align*}
Hence, $(aa',b)=1$.

Theorem 2. If $a,b$ and $c$ are integers such that $(a,b)=1$ and $a|bc$, then $a|c$.

Proof. Since $(a,b)=1$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$. So, we obtain $acx+bcy=c$. Since $a|ac$ and $a|bc$, $a|c$.

Remark. $a|bc$ does not necessarily imply that $a|b$ or $a|c$. For example, $6|36=4\cdot 9$ but $6\not|4$ and $6\not|9$. However, the following theorem holds.

Theorem. If $p$ is a prime number and $p|ab$, then $p|a$ or $p|b$.

Proof. Let $p$ be a prime number and $p|ab$. Suppose that $p\not|a$ and $p\not|b$. Since $p$ is prime and $p\not|a$, $(p,a)=1$ and so $px+ay=1$ for some $x,y\in\mathbb{Z}$. Now, $p|pbx+aby=b$ but this is a contradiction to the assumption that $p\not|b$. Therefore, $p|a$ or $p|b$.

The following proof is essentially the same as the above proof. But instead of proving the statement indirectly by contradiction, it proves the statement directly. It is always good to practice different ways of proving a statement.

Proof. Let $p$ be a prime number and $p|ab$. If $p|a$, we are done. Suppose that $p\not|a$. Then since $p$ is prime, $(p,a)=1$ and so $px+ay=1$ for some $x,y\in\mathbb{Z}$. Now, $p|pbx+aby=b$. This completes the proof.

Theorem. If $a$ and $b$ are integers and $(a,b)=d$, then $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime.

Proof. Since $(a,b)=d$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=d$. Dividing the equation by $d$, we obtain
 $\frac{a}{d}x+\frac{b}{d}y=1$. By theorem 1, this implies that $\left(\frac{a}{d},\frac{b}{d}\right)=1$.

Example. Consider the equation $9x+24y=15$. Since $(9,24)=3$ and $3|15$, from theorem 1, we know that a solution exist. First, we can find a solution to $9x+24y=3$ using the Euclidean algorithm as seen before.
 \begin{align*}
  24&=9\cdot 2+6\\
   9&=6\cdot 1+3\\
   6&=3\cdot 2+0
 \end{align*}
Thus,
\begin{align*}
   3&=9-6\cdot 1\\
    &=9-(24-9\cdot 2)\cdot 1\\
    &=9\cdot 3+24\cdot(-1)
\end{align*}
Hence, $x'=3$ and $y'=-1$ is a solution to $9x+24y=3$ and thereby $x=5x'=15$ and $y=5y'=-5$ is a solution to $9x+24y=15$. Finding a solution is not a big deal. But there are other solutions. For instance, $x=-1$ and $y=1$ is also a solution to $9x+24y=15$. How do we find other solutions? We now turn our attention to this question.

Suppose that $(x_0,y_0)$ is a solution to
$$
 ax+by=c \tag{1}
$$
Then
$$
 ax_0+by_0=c \tag{2}
$$
Subtracting (2) from (1), we obtain
$$
a(x-x_0)=b(y_0-y) \tag{3}
$$
Let $d=(a,b)$. Dividing (3) by $d$, we obtain
$$
\frac{a}{d}(x-x_0)=\frac{b}{d}(y_0-y) \tag{4}
$$
This means that $\frac{a}{d}|\frac{b}{d}(y_0-y)$. Since $\left(\frac{a}{d},\frac{b}{d}\right)=1$, by theorem 2, $\frac{a}{d}|y_0-y$ and so, $y_0-y=\frac{a}{d}t$ for some $t\in\mathbb{Z}$. From (4) we also obtain $x-x_0=\frac{b}{d}t$. Therefore, $x$ and $y$ are written as
$$
  x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t \tag{5}
$$
where $t\in\mathbb{Z}$. Conversely, any $(x,y)$ in the form (5) satisfies the equation (1).
$$a\left(x_0+\frac{b}{d}t\right)+b\left(y_0-\frac{a}{d}t\right)=ax_0+by_0=c$$

Theorem 3. Suppose that $a\ne 0$, $b\ne 0$, and $c$ are integers. Let $(x_0,y_0)$ be a particular solution to $ax+by=c$. Then all solutions to $ax+by=c$ are given by
 $$x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$$
 where $t\in\mathbb{Z}$ and $(a,b)=d$.

Example. In preceding example, we found $(x_0,y_0)=(15,-5)$. So by theorem 3, all solutions to $9x+24y=15$ are given by
$$x=15+8t,\ y=-5-3t$$
where $t\in\mathbb{Z}$.

Example. Find all positive integers $x,y$ such that $4x+6y=100$.

Solution. $(4,6)=2$ and $2|100$, so a solution exists.
$6=4\cdot 1+2$ i.e. $2=4\cdot (-1)+6\cdot 1$. $x_0=-50$ and $y_0=50$ is a particular solution to $4x+6y=100$. By theorem 3, all solutions are given by
$$x=-50+3t,\ y=50-2t$$
where $t\in\mathbb{Z}$. Since $x$ and $y$ are required to be positive, we find that $17\leq t\leq 24$. The following table shows all those solutions.
$$
\begin{array}{|c||c|c|c|c|c|c|c|c|}
\hline
t & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24\\
\hline
x & 1 & 4 & 7 & 10 & 13 & 16 & 19 & 22\\
\hline
y & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 2\\
\hline
\end{array}
$$

Example. A man paid 11.37 dollars for some 39-cent pens and 69-cent pens. How many of each did he buy?

Solution. The problem is equivalent to solving the equation
$$
39x+69y=1137 \tag{6}
$$
where $x$ and $y$ are nonnegative integers. $(39,69)=3$ and $3|1137$, so the equation has a solution. Solving the equation (6) is equivalent to solving
$$
13x+23y=379 \tag{7}
$$
where $x$ and $y$ are nonnegative integers. Since $(13,23)=1$, by the Euclidean algorithm, one can find a solution $x'=-7$ and $y'=4$ to $13x+23y=1$. $x_0=379x'=-2653$ and $y_0=379\cdot y'=1516$ is then a solution to (7). By theorem 3, all integer solutions to (7) are given by
$$x=-2653+23t,\ y=1516-13t,\ t\in\mathbb{Z}$$
From the conditions $x\geq 0, y\geq 0$, we obtain the inequality $115\frac{8}{23}\leq t\leq 116\frac{8}{23}$. There is only one integer $t=116$ that satisfies the inequality. $x=-2653+23\cdot 116=15$ and $y=1516-13\cdot 116=8$. So, the man bought 15 39-cent pens and 8 69-cent pens.