3.3: Solution of the Homogeneous equation ax+by = 0

Last updated
Save as PDF

Page ID: 60310

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Proposition 3.5

The general solution of the homogeneous equation \(r_{1}x+r_{2}y = 0\) is given by

\[\begin{array} {ccc} {x = k \frac{r_{2}}{\gcd(r_{1}, r_{2})}}&{and}&{y = -k \frac{r_{2}}{\gcd(r_{1}, r_{2})}} \nonumber \end{array}\]

where \(k \in \mathbb{Z}\).

Proof

On the one hand, by substitution the expressions for \(x\) and \(y\) into the homogeneous equation, one checks they are indeed solutions. On the other hand, \(x\) and \(y\) must satisfy

\[\frac{r_{1}}{\gcd(r_{1}, r_{2})} x = - \frac{r_{2}}{\gcd(r_{1}, r_{2})} y \nonumber\]

The integers \(r_{i}\) (for \(i\) in \(\{1,2\}\)) have greatest common divisor equal \(\gcd(r_{1},r_{2})\) to \(1\). Thus Euclid’s lemma applies and therefore \(\frac{r_{1}}{\gcd(r_{1}, r_{2})}\) is a divisor of \(y\), while \(\frac{r_{2}}{\gcd(r_{1}, r_{2})}\) is a divisor of \(x\).

A different proof of this lemma goes as follows. The set of all solution in \(\mathbb{R}^{2}\) of \(r_{1}x+r_{2}y = 0\) is given by the line \(l(\xi) = \begin{pmatrix} {r_{2}}\\ {-r_{1}} \end{pmatrix} \xi\). To obtain all its lattice points (i.e., points that are also in \(\mathbb{Z}^2\)), both \(r_{2} \xi\) and \(-r_{1} \xi\) must be integers. The smallest positive number \(\xi\) for which this is possible, is

\[\xi = \frac{1}{\gcd(r_{1}, r_{2})} \nonumber\]

Here is another homogeneous problem that we will run into. First we need a small update of Definition 1.2.

Definition 3.6

Let \(\{b_{i}\}^{n}_{i=1}\) be non-zero integers. Their greatest common divisor, \(\mbox{lcm} (b_{1}, \cdots, b_{n})\), is the maximum of the numbers that are divisors of every \(b_{i}\); their least common multiple, \(\gcd(b_{1}, \cdots, b_{n})\), is the least of the positive numbers that are multiples of of every \(b_{i}\).

Surprisingly, for this more general definition, the generalization of Corollary 2.15 is false. For an example, see exercise 2.6.

Corollary 3.7

Let \(\{b_{i}\}^{n}_{i=1}\) be non-zero integers and denote \(B = \mbox{lcm} (b_{1}, \cdots b_{n})\). The general solution of the homogeneous system of equations \(x = _{b_{i}} 0\) is given by

\[x =_{B} 0 \nonumber\]

Proof: From the definition of \(\mbox{lcm} (b_{1}, \cdots, b_{n})\), every such \(x\) is a solution. On the other hand, if \(x \ne _{B} 0\), then there is an \(i\) such that \(x\) is not not a multiple of \(b_{i}\), and therefore such an \(x\) is not a solution.