Chapter 26
Notes for the ninth week: ax + by = c, fractions

Notes also available as PDF.

26.1 Linear Diophantine equations

In a few weeks, we will examine linear equations ax + by = c over real numbers. But many every-day applications require integer solutions. We can use the Euclidean algorithm to find one integer solution to ax + by = c or prove there are none. Then we can use the computed gcd to walk along the line to all integer solutions.

Some solvable problems:

Or:

Consider the latter problem. Rephrasing algebraically,

We start by solving

and then multiplying the base solutions by 100. This case has one easy solution, x = -1 and y = -1, with 3 ⋅-1 - 4 ⋅-1 = -3 + 4 = 1. Another solution is x = 3 and y = 2.

In fact, there are infintely many solutions to 3x - 4y = 1 given by

for any integer t. You can substitute these expressions into 3x - 4y to verify the result. Scaling the right-hand side by 100, solutions to 3x - 4y = 100 are given by

For x > 0 and y > 0, we need t > 33. So the first positive solutions are given by t = 34,35,\mathop{\mathop{…}} and are

(x,y) \{\mathop{\mathop{…}},(36,2),(40,5),(44,8),(48,11),(52,14),(56,17),(60,20),\mathop{\mathop{…}}\}.

26.1.1 In general\mathop{\mathop{…}}

Say we need to solve ax + by = c for integers a, b, and c to find integer solutions x and y. In general, equations over integers are called Diophantine equations after Diophantus of Alexandria (approx. 200AD-290AD). He was the first known to study these equations using algebra. The form ax + b = c describes linear Diophantine equations.

Let d = (a,b). Then, as before, d\mathrel{∣}ax + by for all integers x and y. So d\mathrel{∣}c for any solutions to exist. If d ∤ c, then there are no integer solutions. If a and b are relatively prime, then (a,b) = 1 and solutions exist for any integer c.

Consider solving ax + by = d. Because d\mathrel{∣}c, we can multiply solutions to ax + by = d by c∕d to obtain solutions of ax + by = c. To solve ax + by = d we work backwards after using the Euclidean algorithm to compute d = (a,b).

Say the algorithm required k steps, so d = {r}_{k-1}. Working backward one step,

So d = {r}_{k-1} = i ⋅ {r}_{k-3} + j ⋅ {r}_{k-4} where i and j are integers. Continuing, the gcd d can be expressed as an integer combination of each pair of remainders.

Returning to the example of (77,53), we found

Working from the second to the last,

To solve 53x + 77y = 22, we start with 53 ⋅ 16 + 77 ⋅ (-1) = 1. Multiplying by 22,

and x = 352, y = -22 is one solution.

But if there is one solution, there are infinitely many! Remember that d = (a,b), so a∕d and b∕d are integers. Given one solution x = {x}_{0} and y = {y}_{0}, try substituting x = {x}_{0} + t ⋅ (b∕d) and y = {y}_{0} - t ⋅ (a∕d) for any integer t. Then

Actually, all integer solutions to ax + by = c are of the form

where t is any integer, d = (a,b), and {x}_{0} and {y}_{0} are a solution pair.

Another example, consider solving 12x + 25y = 331. First we apply the Euclidian algorithm to compute (12,25) = 1:

Substituting back,

So we can generate any solution to 12x + 25y = 331 with the equations

Using these, we can find a “smaller” solution. Try making x non-negative with

Substituting t = 27,

Interestingly enough, this must be the only non-negative solution. A larger t will force y negative, and a smaller t forces x negative. But the solution for t = 26 is still “small”,

26.1.2 The other example

Our other posed problem:

So we need to solve 5x + 12y = 98, and start with 5x + 12y = 1.

Computing (12,5),

So (12,5) = 1. Because 1\mathrel{∣}98, there are infinitely many integer solutions. We need to find the non-negative solutions from those.

For a base solution,

So {x}_{0} = 5 and {y}_{0} = -2 solve 5x + 12y = 1. Multiplying by 98,

solve 5x + 12y = 98.

To find all solutions,

To find non-negative solutions, first consider how to make y positive. Here t = -40 makes y = 4. Trying x, x = 10. So one solution is

With t = -39, y is negative. And with t = -41, x is negative. So this is the only possible solution for the actual problem.

26.2 Into real numbers

We’ve used real numbers without much thought. For the next week and a half, we’ll fill in a few details.

• Rational numbers
  • Arithmetic and comparisons
  • Decimal expansion (and other bases)
  • Percentages
• Irrational numbers
  • Show that non-rational real numbers exist
  • Square roots, cube roots, and other radicals
• Computing
  • Floating-point arithmetic (arithmetic with restricted rationals)

This week will cover topics in rational numbers and hence fractions. For some people, this will be old hat. For others, this is a continuing thorn in their sides.

This presentation will be a bit different than the text’s more typical structure. I hope that this difference may help some who struggle with rationals and fractions by providing reasons for the rules.

26.2.1 Operator precedence

A quick aside on the order in which operations can be applied. Working with fractions stress operator precedence.

Operations generally don’t pass through straight lines, whether horizontal for fractions or vertical for absolute value.

Parentheses force an order. Work from the inner outwards.

The general order of precedence between operations:

1. exponents, then
2. multiplication and division (which really are the same thing), then
3. addition, subtraction, and negation (again, these are the same thing).

Within a class, operations proceed from left to right.

Go through a parenthetical clause and compute every exponent, then every multiplication from left to right, and then every addition from left to right.

When in doubt, use parentheses when you write expressions.

26.3 Rational numbers

Rational numbers are ratios of integers. In a fraction {n\over d}, n is the numerator and d is the denominator. The rational numbers form a set,

ℚ = \{{a\over b}\kern 1.66702pt |\kern 1.66702pt a J,b J,b\mathrel{≠}0\},

where J is the set of all integers. Let be the set of all real numbers, then J ⊊ ℚ ⊊ . The integer on top, a, is the numerator; the integer on the bottom, b, is the denominator.

Note that this is a very formal construction. We just plop one integer atop another and call it a number. Amazing that it works.

Fractions represent ratios and proportions. When you state that 1 in 10 people are attractive to mosquitos¹ , that’s a rational number. We won’t reach probability, where we learn to interpret these ratios correctly, but we will cover basic manipulations of rational numbers.

Two fun points:

• There are only as many rational numbers as there are non-negative integers (and hence integers)! Both sets are infinite, but you can construct a mapping from each non-negative integer to and from a corresponding fraction.
• Between any two real numbers of any sort, there is a rational number. The size of the separation does not matter! There always exists a rational number arbitrarily close to a given real. Consider taking a decimal/calculator expansion and chopping it off once it’s close enough.

26.4 Review of rational arithmetic

Rational arithmetic is based on integer arithmetic. The following properties will be inherited by multiplication and addition for rationals q, r, and s:

closure

q + r ℚ, qr ℚ

commutative

q + r = r + q, qr = rq,

associative

q + (r + s) = (q + r) + s, q(rs) = (qr)s, and

distributive

q(r + s) = qr + qs.

One homework question is to take the operation definitions below and verify some of these properties.

The following are somewhat formal definitions to show how to construct rationals along strict rules.

26.4.1 Multiplication and division

We start with multiplication and division. Let a,b,k,x,y J, so all the variables are integers. We will extend these variables to run over the rational numbers shortly.

The definition of multiplying fractions:

As an example

The definition of a relationship between division and fractions:

We need to be a little careful here. Integer division was defined only when b\mathrel{∣}a, so this expression formally only holds when b\mathrel{∣}a. We relax this restriction later to allow the variables to run over rational numbers.

An important consequence is that

for all a.

This leads to very useful technique, expressing 1 as a fraction:

for any k\mathrel{≠}0. Remember that in the divisibility form k = 1 ⋅ k + 0, so k\mathrel{∣}k and k∕k = 1.

Next we show what the text calls “the fundamental property of rational numbers”, which is not terribly fundamental. First we show that 1 is the multiplicative identity for rationals by using the fact that 1 is the multiplicative identity for integers,

Using this fact, we show that {a\over b} = {ak\over bk} for any k\mathrel{≠}0,

Now we introduce proper fractions. A proper fraction is a rational {a\over b} where the numerator a and denominator b are relatively prime. That is \mathop{gcd}(a,b) = 1 and they share no common factors. Every fraction is equal to some proper fraction. Given \mathop{gcd}(a,b) = d, we can factor out the common divisor,

So for 15 and 35, (15,35) = 5 and

A fraction that is not proper is improper. An improper fraction is a redundant representation, and keeping fractions improper sometimes helps speed operations.

Every rational number with a non-zero numerator has a multiplicative inverse. This uses only the expression for 1 and the relationship between integer division and fractions. Using that a∕a = 1 and commutativity of integer multiplication,

So if a\mathrel{≠}0, then {b\over a} is the multiplicative inverse of {a\over b}. As an example,

With a multiplicative inverse, we can define division of rationals analogously to the fractional form of division of integers,

For example,

26.4.2 Addition and subtraction

When adding rational numbers, you must ensure both ratios have the same denominators. This is the same as ensuring measurements are all in the same units; both numerators need measured by the same denominator.

The definition for adding fractions:

Later we will use the least common multiple of b and y to work with a smaller initial denominator. So

Rational numbers have additive identities:

We prefer there to be only one additive identity. We can use the “fundamental property” above to prove that all additive identities are equal to {0\over 1}:

Given that 1\mathrel{∣}0, {0\over 1} = 0∕1 = 0. So zero is the additive identity for rationals as well as integers.

Like integers, rationals have additive inverses:

Given the additive inverse exists, we can define the negation of a rational as

and then we define subtraction in terms of addition as

So

26.4.3 Comparing fractions

We start with some high-level definitions and find the common product rule for comparing fractions.

First, a quick review of integer ordering. We say an integer is negative if it has a negative sign, e.g. -1. An integer is positive if it is neither zero nor negative, or equivalently if the integer is also a counting number. We start an ordering of the integers by saying that a positive i > 0, a negative i < 0, and 0 = 0.

Then we can compare two integers i and j by their difference. There are three cases:

• If i - j > 0, then i > j.
• If i - j < 0, then i < j.
• Finally, if i - j = 0, then i = j.

This phrasing may help with the common confusion regarding comparisons and multiplication by negative numbers.

Consider two integers 3 < 5. That 3 < 5 implies 3 - 5 < 0 (and we know it is -2). Now multiply both sides here by -1. If 3 - 5 < 0, that implies 3 - 5 is negative, and in turn - 1 ⋅ (3 - 5) = 5 - 3 = 2 is positive. Thus multiplying both sides by -1 (and hence any negative number) requires reversing the comparison. Here - 1 ⋅ (3 - 5) = 5 - 3 > 0. But by the distributive property, - 1 ⋅ (3 - 5) = (-3) - (-5) as well, so (-3) - (-5) > 0 and - 3 > -5.

Returning to rationals, the integers are a subset, so an order on the rationals should respect the same ordering on the integer subset.

A positive fraction is equal to some fraction where both the numerator and denominator are positive integers. So both the numerator and denominator must have the same sign,

A negative fraction is equal to some fraction where the numerator is negative and the denominator is positive. Here the signs must be opposite,

As we saw with the additive identity, a zero fraction is equal to the integer zero and has a zero numerator. The sign of zero does not matter in rational arithmetic (although it may in a computer’s floating-point arithmetic).

Given two rationals r and q, r is strictly less than q, r < q, if q - r is positive. Thus

We can always move negative signs into the numerator, so we assume that {q}_{d} and {r}_{d} are positive. But remember to convert the fraction into having a positive denominator! Then the above relation

So

By symmetry, then we can compare two rational numbers by comparing appropriate products.

• If {q}_{n}{r}_{d} > {q}_{d}{r}_{n}, then {{q}_{n}\over {q}_{d}} > {{r}_{n}\over {r}_{d}} .
• If {q}_{n}{r}_{d} < {q}_{d}{r}_{n}, then {{q}_{n}\over {q}_{d}} < {{r}_{n}\over {r}_{d}} .
• If {q}_{n}{r}_{d} = {q}_{d}{r}_{n}, then {{q}_{n}\over {q}_{d}} = {{r}_{n}\over {r}_{d}} .

Consider comparing {1\over 2} and {1\over 3},

And for the negations {-1\over 2} and {-1\over 3} ,

As an example of why you need to force the denominator to be positive, consider {1\over 2} and {-1\over -3}.

This is because we are in essence multiplying both sides by the product of their denominators. That product is negative, so we would have to flip the sign. It’s just as easy to remember to make the denominator positive.

26.5 Complex fractions

So far, the numerator and denominator have been integers. We can loosen the definition slightly and allow complex fractions where the numerator and denominator are rational numbers. We extend the division definition to map complex fractions into fractions with integral numerators and denominators,

We could use this definition to show that all the arithmetic operations work as expected on complex fractions.

Working with complex fractions sometimes allows adding fractions without using a massive denominator.

Let L be the least common multiple of b and y. Then b\mathrel{∣}L and y\mathrel{∣}L, so L∕b and L∕y are integers. We can manipulate the addition definition slightly by introducing L,

With 75 =\mathop{ lcm}\nolimits (15,25),

Quite often there is less work in reducing the result into proper form if you use the least common multiple as the denominator.

26.6 Homework

Practice is absolutely critical in this class.

Groups are fine, turn in your own work. Homework is due in or before class on Mondays.

• Repeated, because I didn’t cover the material last week: Find two integer solutions to each of the following, or state why no solutions exist:
  • 64x + 336y = 32
  • 33x - 27y = 11
  • 31x - 27y = 11
• Problem set 6.1 (p354)
  • 2, 6, 11, 12
  • 32
• Problem set 6.2 (p375)
  • 6, 18, 13, 25
• Problem set 6.3 (p389)
  • 2
  • 8, 9
  • 12

Note that you may email homework. However, I don’t use Microsoft^TM products (e.g. Word), and software packages are notoriously finicky about translating mathematics.

If you’re typing it (which I advise just for practice in whatever tools you use), you likely want to turn in a printout. If you do want to email your submission, please produce a PDF or PostScript document.