Numbers and Arithmetic IV

Un-Repeat Machines and Fractions

Having defined multiplication in terms of repeating, we define division in terms of un-repeating. Just as subtraction led us to introduce negative numbers, division will lead us to introduce fractional numbers.

We begin by considering the concept of division for non-negative whole numbers. The first step is to show that for p > 0, the repeat machine, Rp, has an un-machine. Recall that an input/output machine has an un-machine if the machine always produces different outputs when fed different inputs.

Suppose p is a positive whole number then for any n, (p x n) < (p x (n + 1)).

Proof: Since p is positive, (p x n) < (p x n) + p

(p x n) + p = (p x n) + (p x 1), because 1 is the identity for multiplication

(p x n) + (p x 1) = p x (n + 1) by the distributive law.

So (p x n) < (p x (n+1))

.

From the result above it follows that for p > 0, p x 0 < p x 1 < p x 2 < p x 3 < …and so on

And in general, for p > 0, if m < n then p x m < p x n.

(This would be formally proved using Mathematical Induction.)

And from this it follows that if m is not equal n (so either m < n or n < m), (p x m) is not equal to (p x n).

As usual we assume that I₀ , I₁, I₂, … are the natural number instructions for a DO-IT machine and that for m not equal to n, I_m is not equal to I_n . Suppose p is a positive whole number and that m is not equal to n. We want to show that (p * I_m ), the instruction “repeat I_m p times”, is not equal to (p * I_n ), the instruction “repeat I_m p times”. Now (p * I_m) = I_pxm and (p * I_n) = I_pxn . Since m is not equal to n, by the remark above, (p x m) is not equal to (p x n) and so I_pxm is not equal to I_pxn .

From this it follows that for natural number instructions, the Repeat p machine, R_p , produces different output for different input and so R_p has an un-machine we will call D_p , where the “D” stands for divide.

For p > 0 we define the divide by p machine, D_p = Un-R_p

“Divide by p” undoes “repeat p times”. We can represent the outputs of input/output machines for different input using the same kinds of arrow diagrams we used in article II to show the results of executing instructions for different starting states. Below is the arrow diagram for R₂ for non-negative whole number instructions.

On input I₀ , R₂ outputs (I₀ ; I₀) = I₀. For input I₁, R₂ outputs (I₁ ; I₁) = I₂. For I₂ the output is (I₂;I₂) = I₄ and so on as indicated below. The output instruction is obtained by repeating the input instruction twice. Taking the unit instruction to be “Stack One Block” for example, we see that the output of R₂ for the instruction “Stack 5 blocks” is equivalent to “Stack 10 blocks”.

The arrow diagram for divide-by 2, D₂, is obtained by reversing the arrows for R₂. Thus D₂ takes I₂ to I₁, I₄ to I₂, I₆ to I₃ and so on. The output of D₂ is obtained by “halving” the input; “halving” undoes “repeating twice”

What does D₂ produce for input I₁, I₃, I₅, and so on? In our current interpretation which only considers natural number instructions, these are not possible outputs for R₂ and so are not acceptable inputs for D₂. Shortly we will consider interpretations of numbers to allow for “fractional” instructions which will extend the outputs of R_n and thus the acceptable inputs of D_n, for n not equal to 0, to include all whole numbers.

For R₃ and D₃ the arrow diagrams look like:

For the block stacking machine the possible outputs for R₃ and thus the acceptable inputs for D₃ are I₀, I₃, I₆, etc.

It’s easy to construct pulley machines to represent divide machines. Recall that a pulley machine representing R_n consists of two pulleys, one, the input pulley, having diameter n times the diameter of the other, output pulley. The pulleys are connected by a belt. One turn of the input pulley results in n turns of the output pulley. So if we simply turn the machine around, making the output pulley the input pulley, and vice versa, we have a machine for which n turns of the input pulley results in 1 turn of the output pulley which is exactly the behavior required of D_n. Below is a pulley machine representing D₃.

A D₃ machine

Below we show the successive states of the D3 pulley machine after 0,1,2, and 3 turns.

0 Turns

1 Turn

3Turns

Having returned to the original state after three turns the sequence will repeat so that every three turns of input will result in one additional turn of output.

Since D_n = un-R_n, we have R_n*D_n, the result of connecting R_n to D_n, is equivalent to the R₁, the identity machine.

R_n * D_n = R₁

For example, R₃ * D₃ = R₁ . Each turn of the R3 input pulley results in 3 turns of the R3 output pulley which results in 3 turns of the D3 input pulley which results in 1 turn of the D3 output pulley. The effects of the two pulley machines cancel so that 1 turn of input results in 1 turn of output.

What happens when we multiply D_m and D_n for some m and n? D_m = un-R_m and D_n = un-R_n, so D_m*D_n = (un-R_m)*(un-R_n) = un-(R_n * R_m) = un-R_mxn = D_mxn .

D_m * D_n = D_{m x n}

For example D₂ * D₃ = D_{2 x 3} = D₆

D₂ * D₃

0 Turns

1 Turn

2 Turns

3 Turns

4 Turns

5 Turns

6 Turns

The diagrams above show the results of 6 input turns to a machine consisting of a D₂ connected to a D₃ machine. Every 2 turns of input results in one turn of output of the D₂ machine and thus one turn of input to the D₃ machine. 4 turns of input results in 2 turns of input to the D₃ machine and 6 turns of input results in 3 turns of input to the D₃ machine and thus one turn of output of the compound machine. Thus the compound machine converts 6 turns of input to 1 turn of output. It is thus a D₆ machine.

What can a dividing machine do for us? D_n is the un-R_n machine. So we can use D_n to solve problems where we know the output of some R_n and we want to find the input. One kind of problem we can solve this way is how to distribute some number of items equally among some number of receivers of the items.

For example, suppose I have 20 oranges and I want to distribute them equally among 5 people. How many oranges should I give to each person? There are at least two ways to look at this problem.

Here’s one. We take our DO-IT machine to be an orange giver. Our unit instruction is “give out an orange.” So the instruction I_m , means “give out m oranges”. (Note that this machine doesn’t care who gets the oranges. We can imagine each of the 5 people coming up separately to accept the oranges from the machine.) Let’s call the number of oranges we give to each person m. If we are going to give m oranges to each of the 5 people then we are going to repeat the instruction “give out m oranges” 5 times. The result will be that we will give out a total of 20 oranges. So we have the following picture:

So here is an example where we have the output of the repeat machine and want to know the input. This we can solve by feeding the output into the un-machine. The un-machine for R₅ is D₅. We have.

So we will put 4 oranges in each basket. And indeed,

Another approach we can take to this problem is to actually “build” a machine which will carry out the equal distribution of the oranges. We’ll call this the “Ferris Wheel” interpretation of division.

Here’s the idea. We will put 5 baskets equally spaced around a pulley of radius 5.

Ferris Wheel

We start the wheel with one basket at the top. Each time we turn input wheel the next basket will rotate to the top. After 5 turns of the input wheel each basket will have been to the top exactly once. Note that 5 turns of the input pulley result in one turn of the output pulley so in addition to being a component of our orange distribution system this is a D₅ machine. The other component of our orange distribution system consists of a hopper containing our 20 oranges above a conveyor belt leading to a chute down which the orange will roll into a waiting basket.

Each complete turn of the crank advamces the next basket to the chute where it receives an orange. Here are pictures of the state of the baskets after the first 6 turns of the crank.

We observe that every complete turn of the wheel holding the baskets results in distributing one additional orange to each basket. So the number of oranges in each basket after 20 turns of the crank will be the same as the number of complete turns of the basket wheel after 20 turns of the crank. As we observed earlier the basket rotator is a D₅ machine and so the number of complete turns will be 20 divided by 5.

Fractional Instructions

The following discussion should be reminiscent of the discussion motivating us to introduce negative numbers. Recall that in that discussion we had introduced a new kind of instruction called a “negative” instruction, I_-n, defined as the un-instruction for I_n. We noted that for some machines, machines without negative states, not all states are acceptable for negative instructions and on some machines all states are acceptable for negative instructions. On this basis we admitted negative numbers to the class of numbers, interpreting -n as I_-n with the understanding that for a given application involving negative numbers we must verify that the interpretation is meaningful. Our situation with divide machines is analogous. In the present case we have introduced a new kind of input/output machine for instructions, D_n ,defined as un-R_n. and noted that for some Do-It machines there are instructions which are not acceptable input to D_n. Are there Do-It machines for which D_n accepts all whole number instructions?

We begin with some notation. Suppose we have a Do-It machine for which D₂ accepts I₁ . We will call the output of D₂ for input I₁ , “I_1/2 .” Since D₂ is un-R₂ the result of repeating I_1/2 twice is equivalent to I₁ . Similarly if D₃ accepts I₁ we refer to the output as I_1/3 because executing I_1/3 three times is equivalent to executing I₁ . An instruction which when executed three times is equivalent to executing I₂ will be referred to as I_2/3 and in general an instruction which when executed n-times is equivalent to I_m will be referred to as I_m/n . The notation “m/n” is called a “fraction” and a corresponding instruction I_m/n is called a “fractional instruction.” We are interested in finding a machine for which all fractional instructions exist.

Consider a “measure” machine. The machine consists of a rod and a marker which can be positioned at any distance from the beginning of the rod. We choose some unit distance, say the length of teacher’s foot, and take as our unit instruction I₁ , “Move the marker one unit of distance to the right. We take our zero state to be that in which the marker is at the beginning of the rod.

What would the instruction and the state corresponding to I_1/2 be for this machine?

Above we have shown the positions on the rod corresponding to states 0 through 5 along with an arrow of length one unit representing the unit instruction for moving the marker one unit away from the start of the rod. We have also indicated the desired property of I_1/2 : executing it twice is equivalent to executing I₁ . From this we see that I_1/2 must move the marker a distance such that twice that distance equals the unit distance. In common parlance, I_1/2 must move the marker “half of the unit distance.”

How do we know that such a distance exists? The pictures we have drawn above are only approximations to exact distances and so the fact that some line drawing appears even under very close observation to be exactly half of the length of some other line drawing is no guarantee that exact halves exists. You might say that if you have a line segment of some length then you can find a line segment of exactly half the length by taking the line segment starting at one end and ending at the “mid-point” of the segment. But then we would have to ask, “how do you know there is an exact mid-point of the segment?”

This kind of question, that is whether or not a geometric object, such as a line segment, having some exact relationship to some other geometric object exists was of considerable interest to the ancient Greek mathematicians. They actually asked such questions in a much more useful way: “Given one geometric object, can I construct another geometric object having a given exact relationship to the first?” For example, given a line segment can I construct another line segment which is “exactly half the length of the given line segment”, meaning if I repeat it twice the result will be exactly equivalent to the given line segment?

In order to carry out such a construction we need certain tools. The tools we will use are a straight-edge which we can use to draw a perfect line segment between any two points and a device called a compass. A compass, as illustrated below, consists of two pencil-like legs connected at their “eraser” ends by a hinge. The hinge can be opened and closed so that the pointy ends can be moved closer together or further apart. One of the pointy ends called the drawing-leg is a marker. When the compass is used the other leg, called the fixed-leg stays at a fixed point. The drawings below show the compass with the hinge relatively open and relatively closed.

One thing we can do with compass is to draw a perfect circle centered at a given point and having a radius of a given length. This is illustrated below. We start by holding the compass perpendicular to the plane of the paper and placing it over a line segment having the desired length of the radius and spreading the legs of the compass so that one leg is position at each end point of the segment. The distance between the points will then be exactly the length of the line segment. We then pick up the compass still keeping it perpendicular to the paper; position the fixed leg at the desired center of the circle; place the drawing point on paper; swivel the compass about the fixed leg keeping the marker on the paper.

Another use of a compass is to “lay off” a certain distance on a line. For example suppose we are given a point on a line and we want to construct another point on the line whose distance from the first point is the length of a given line segment. The technique is illustrated below.

Using these techniques we can construct fractional lengths. We start by constructing a length which is exactly half of a given length. We are given a line segment whose length we wish to halve. We will do this by constructing a point on the line segment which is exactly the same distance from each end point, i.e., the mid-point.

The blue line segment in the diagram below is the one we wish to halve. Here are the steps.

• Use the compass to construct a circle whose radius is equal to the line segment centered at the Right end-point of the segment.
• Use the compass to construct a circle whose radius is equal to the line segment centered at the Left end-point of the segment.
• Use the straight edge to construct a line segment between the two points where the circles intersect.
• The point where the two line segments intersect is the midpoint of the original line segment.

It certainly appears that the intersection point is exactly midway between the two end points of the original line segment, but how can we verify this? We first note that the plane is uniform in all directions, i.e. moving a figure in any direction will not change its size or shape. Second, except for the order in which the two circles are constructed, the construction given above is symmetric with respect to Left and Right. What we mean by symmetric with respect to left and right is that if we substitute right for left and left for right everywhere in the construction the result would be the same figure. Put another way – and you can try this! – if you were to carry out the construction as given while standing on your head so that your notion of left and right were the opposite of mine the figure would still be the same. From this it follows that the intersection point must be exactly the same distance from the end points. For suppose it were closer to one end, say the left end point. Then it would have to be closer to the left end point from both my point of view and your upside down point of view, but being closer to the left end point from your point of view would mean that it was closer to the right end point from my point of view! The only way we can both see the same figure is for the intersection point to be exactly in the center.

Here’s another way of looking at it. Let’s consider what happens if we flip the drawing over. Suppose that the red marks made by our marker show through to the other side of the paper as green and the green marks as red. Now suppose we flip the paper over. Flipping doesn’t change the size of any of the figures and so after flipping we can move the paper so that the original line segment, the blue line segment, is in exactly the same position as it was before the flip. Of course, after flipping, what was the right end point will now be the left end point and the old left endpoint will now be the right end point.

Now consider what happens to the two circles. What was the circle centered at the right end point with radius equal to the length of the blue line segment now becomes a circle centered at the left end point with radius equal to the length of the blue line segment so the old right circle must flip exactly onto the old left circle. Similarly, the old left circle must flip onto the old right circle. So the two circles after the flip are the same and so the two intersection points are the same and so the vertical line segment is the same and so the intersection point must be the same. Thus the figure must look exactly same before and after the flip. This implies that the cross in the center is exactly the same after the flip and so the left and right line segments of the horizontal segment must exactly match and so have the same length. Thus, the intersection point exactly splits the horizontal line segment into two equal parts which is what we wanted to show.

Also note that the vertical line segment must be exactly perpendicular to the horizontal line segment. For, as illustrated below, if it sloped even slightly before the flip it would slope in the opposite direction after the flip and so would not match the old image.

“Bisect” is a term for cutting exactly in half and for this reason and the fact that it is perpendicular to the original line segment, the exactly vertical line in our drawing above is called a “perpendicular bisector”. We will use our ability to construct perpendicular bisectors below.

We will use a different technique, called scaling, to construct the other fractional distances. Scaling is the basis for maps, and blueprints, and the technique by which massively complex electronic circuits are transferred to tiny pieces of melted sand.

Suppose we want to construct a distance which is “one third” (“1/3") of a given distance, i.e. which when repeated three times is equivalent to the given distance.

The idea of scaling is to construct a scale model of the desired construction in which all distances are either magnified or reduced to the same degree. For example if we have a street map of a city with a scale of “1 inch to the mile”, we have a model of the city in which a straight street of length one mile would be represented as a line segment of length one inch and a street of length two miles would be represented as a line of length two inches and so on. For the present problem, we will magnify the distances by a factor of three.

To construct the model below we mark the end points of the line segment we are given and use our straight edge to extend the line segment at least far enough that we can lay out three adjacent copies of the segment using the compass technique we discussed earlier.

The next step is to construct a vertical segment of length 1 unit based at the right end. As indicated in the figure we can do this by laying out a fourth adjacent segment and using the technique of the previous construction to construct the perpendicular bisector between the left end point of the third segment and the right endpoint of the fourth. Finally, using our compass technique again, we lay out a segment of unit length on the perpendicular.

Leaving out the extra figures required for the construction we have the following “model” for our solution. This is a model for our solution in the sense that the vertical segment is one third the length of the horizontal segment. If we can now reduce this figure by a factor of 3 preserving the exact shape so that the horizontal segment has length one unit then the vertical segment will have length one third of a unit.

We accomplish this reduction by constructing a sequence of triangles as illustrated below.

We start by connecting the left end of the horizontal segment to the top of the vertical segment giving us a right triangle in which the length of the vertical side is one third the length of the horizontal.

We then construct triangles at the intermediate points by drawing perpendiculars to the new segment.

We now claim that the small triangle containing the blue perpendicular and the large triangle containing the black vertical have “exactly the same shape” meaning that one can be obtained from the other by proportionately magnifying or reducing the dimensions. Figures which are proportionately equivalent in this way are said to be similar. In similar shapes, relative sizes are preserved and so since the one unit vertical side in the large triangle is one third of its three unit horizontal side, the vertical in the small triangle must be one third of its one unit horizontal side. This is the length we wanted to construct.

To verify this claim we again use an argument that depends on the uniformity of the plane, i.e., that moving a figure doesn’t change its shape. Just as our geometry does not favor left over right or right over left it also does not distinguish between one starting position over another in carrying out a construction. The results will be exactly the same except located in a different place.

In the figure below we show the results of carrying out our construction from three different starting positions: the original starting position, the position in which the left end point is at the top of the first vertical, and the position at the top of the second vertical.

The three large triangles must be exactly the same. It follows that the lines through the top verticals must be parallel and since they go through common points must coincide. From this it follows that the amount by which the second vertical exceeds the first equals the length of the first vertical and the amount by which the third vertical exceeds the second equals the length of the third vertical. (These are the three blue verticals circled in the diagram above.) Thus the length of the third vertical, which 1 unit, is exactly 3 times the length of the first vertical.

In the same way we can construct for any whole number n > 0 a segment which when repeated n times is equivalent to a given unit length. We construct a right triangle with base n units long and height one unit and take the height of the vertical above the point one unit along the base.

For our measuring rod machine there is a natural ordering of instructions based on the distance by which the marker is moved. For example we see that I_1/3 < I_1/2, I_1/4 < I_1/3, and in general if n > m then I_1/n < I_1/m.

Notice that for our measuring machine, if I < J, then I + I < J + J.

From this it follows that for each n there is only one instruction I_1/n which when repeated n times is equivalent to I₁ . For example, suppose I is not equal to I_1/2 . Then either I < I_1/2 in which case I + I < I_1/2 + I_1/2 = I₁ or I_1/2 < I₁ in which case I_1/2 + I_1/2 = I₁ < I + I and so in either case I + I is not equal to I₁ .[1] A Fractional instruction of the form I_m/n , an instruction which when repeated n times is equivalent to I_m , can be constructed from I_1/n as m* I_1/n . We have n*( m* I_1/n ) = (n x m)* I_1/n = (m x n)* I_1/n = m*(n* I_1/n ) = m*I₁ = I_m . It again follows that if our instructions are ordered, as they are for the measuring rod machine so that I < J implies (I+I) < (J+J), then there can be at most one instruction which when repeated n times is equivalent to I_m . We take this uniqueness property as a requirement for what we will call Fraction Machines.

A Fraction Machine is a Do-It machine such that for each instruction J and every n > 0 and every m there is a unique (up to equivalence) instruction ((m/n)*J) such that n*((m/n)*J) = m*J. Taking J to be I₁ we have for every n > 0 and m a unique instruction we call I_m/n such that n* I_m/n = m * I₁ = I_m .

If J is an instruction for a fraction machine then we say J is a fractional instruction if J is equivalent to I_m/n for some m and n?

The notation “m/n” is called a fraction with numerator m and denominator n. Note that n*(m*((1/n)*J)) = (nxm)*((1/n)*J) = (mxn)* I_1/n = m*(n*((1/n)*J)) = m*(1*J) = m*J . Also n*((1/n)*(m*J)) = m*J. Thus

m*((1/n)*J) = ((m/n)*J)

(1/n)*(m*J) = ((m/n)*J) and so

m*I_1/n = I_m/n

(1/n)*I_m = I_m/n

For example consider what happens when we repeat (I_1/5+I_1/5) 5 times.

=

Thus

As special cases of the above we also have

((n/n)*J) = n*((1/n)*J) = 1*J = J

((n/1)*J) = n*((1/1)*J) = n*J and so

I_n/n= n*I_1/n = I₁.

I_n/1 = n*I_1/1 = n*I₁ = I_n .

Notice that since I_n/1 = I_n , every whole number instruction is also considered a fractional instruction.

For a given denominator n we can view the sequence I₀ , I_1/n , I_2/n = I_1/n+I_1/n , I_3/n = I_1/n+I_1/n + I_1/n, I_4/n , … as the “whole number” instructions J₀ , J₁, J₂, J₃, … for a Do-It machine in which J₁ = I_1/n is named the “unit” instruction. This is the origin of the terms “numerator” and “denominator”. “Denominate” means to name as a unit (“nom” is the root of “name”) as for example when we talk about denominations of money. “Numerate” means “to number”. Thus for the fraction m/n, the denominator, n, tells us the units we are using, I_1/n, and the numerator, m, tells how many times that unit is repeated: I_m/n = m * I_1/n . Using this observation we see that it’s easy to add fractions which have a common denominator: I_j/n+I_k/n = J_j+J_k = J_j+k = I_(j+k)/n . This also follows directly from the facts given above: I_j/n+I_k/n = (j * I_1/n ) + (k * I_1/n ) = (j+k)*I_1/n = I_(j+k)/n . Also note that addition of fractions with the same denominator is commutative because ((j+k)=(k+j) so j/n + k/n = (j+k)/n = (k+j)/n = k/n + j/n). Summarizing:

(j/n + k/n) = ((j+k)/n) = ((k+j)/n) = (k/n + j/n)

Example:

(2/5 + 1/5) = ((2+1)/5) = 3/5 = ((1+2)/5) = (1/5 + 2/5)

While it’s easy to add fractions with the same denominator it is not so clear how to add fractions with different denominators[2]. In fact it’s not even obvious that the sum of two fraction is necessarily a fraction. For example, is (I_1/2 + I_1/3) a fraction? If so, which one?

This leads to an interesting question. How can we test whether a given instruction, I, is a fractional instruction? I is fractional means that I = I_m/n for some m and n and so repeating I some number of times will be equivalent to a whole number instruction. On the other hand, if repeating I some number of times, say n, is equivalent to a whole number instruction, say, I_m , then I must be equivalent to I_m/n . For example, if repeating I 5 times is equivalent to I₃ then I = I_3/5 . If repeating I 153 times is equivalent to I₁₇ then I = I_17/153 . So to test whether I is fractional we keep repeating I until we find some number of repetitions which is equivalent to a whole number instruction. Of course there is peril in this approach in that if I is not a fractional instruction then no matter how many times we repeat it the result will not be equivalent to a whole number instruction! In this case our search would never end. Let’s try this experiment for (I_1/2 + I_1/3) using our measuring rod and hope for the best!

From our experiment it appears that repeating (I_1/2 + I_1/3) six times is equivalent to I₅ which if true implies that (I_1/2 + I_1/3) equals I_5/6 . Of course we can’t be sure of this based on our drawing because our drawing is inexact and so repeating (I_1/2 + I_1/3) six times might only be close to I₅ and not exactly I₅ . Can we show that in fact the result of repeating (I_1/2 + I_1/3) six times is exactly I₅ ?

Maybe we can learn something by rearranging the instructions. You might be concerned that we don’t know that addition of fractions is commutative (though we do know this is the case for fractions with the same denominator) but that’s OK because we’re just trying to come up with ideas. Let’s see what happens when we break up the six (I_1/2 + I_1/3) pairs and put the like components together so that we have

Ah ha! It appears that repeating I_1/2 six times is equivalent to I₃ and repeating I₂ six times is equivalent to I₂ . Now these facts we can prove. By definition 2* I_1/2 = I₁ and 3* I_1/3 = I₁ . Combining these facts with have 6* I_1/2 = (3 x 2)* I_1/2 = 3*(2 * I_1/2 ) = 3 * I₁ = I₃ (exactly!) and 6 * I_1/3 = (2 x 3)* I_1/3 = 2*(3* I_1/3) = 2 * I₁ = I₂ . Thus repeating I_1/2 six times gives us a whole number instruction (I₃)and repeating I_1/3 six times gives us a whole number instruction (I₂) and so assuming we can commute I_1/2+I_1/3 , so that we can rearrange the instructions in the way we have, repeating (I_1/2+I_1/3) six times results in the sum of the two whole number instructions, I₃+I₂ = I₅ , and so (I_1/2+I_1/3) = I_5/6 .

But how do we know we can commute I_1/2+I_1/3 ? We know that 6* I_1/2 = I₃ so I_1/2 = I_3/6 and 6*I_1/3 = 2 so I_1/3 = I_2/6 . So ½ and 1/3 are equivalent to fractions with the same denominator, 6, and so they commute. So 6*(I_1/2+I_1/3) is exactly I₅ and so (I_1/2+I_1/3) = I_5/6 .

But wait a minute! Looking back over this argument we see that we can actually simplify it. Since I_1/2 = I_3/6 and I_1/3 = I_2/6, (I_1/2+I_1/3) = (I_3/6+I_2/6) = I_5/6 .

Now the key to being able to computing the fractional equivalent to (I_1/2+I_1/3 ) was discovering that there was a single number, 6, with the property that repeating I_1/2 that number of times and repeating I_1/3 that number of times resulted in whole number instructions. Will such a number exist for any two fractions and if so how do we find one?

Let’s try another example, say (I_1/5+I_1/3). We are looking for a number m such that both m*I_1/5 and m*I_1/3 are equivalent to whole number instructions. We can start by looking for what numbers m such that m*I_1/5 a whole number instruction. We know that 5*I_1/5 = I₁ so 5*I_1/5 + 5*I_1/5 = 10*I_1/5 = I₂ and so 5*I_1/5 + 5*I_1/5 + 5*I_1/5 = 15*I_1/5 = I₃ and so on. Thus m* I_1/5 is equivalent to a whole number instruction when m is a multiple of 5, i.e. 5=1x5, 10 = 2x5, 15 = 3x5, 20, … . Similarly m*I_1/3 is equivalent to a whole number instruction when m is a multiple of 3, that is 3=1x3, 6 = 2x3, 9 = 3x3, 12, … . So the number we are looking for must be both a multiple of 5 and a multiple of 3. Is there such a number? Let’s try searching the two lists 5, 10, 15, … and 3, 6, 9, 12, 15, … We discover that 15 = 3x5 is a multiple of 5 and 15 = 5x3 is a multiple of 3 We then have 15*I_1/5 = 3*(5*I_1/5 ) = 3*I₁ = I₃ and so I_1/5 = I_3/15 and 15*I_1/3 = 5*(3*I_1/3 ) = 5*I₁ = I₅ and so I_1/3 = I_5/15 . Thus I_1/5 + I_1/3 = I_3/15 + I_5/15 = I_8/15 .

Now consider the general case of adding a fraction with denominator m to a fraction with denominator n. (In the first example m=2 and n=3 and in the second example m=5 and n=3.)

We know that we can express the fractional instructions in terms of fractions with the same denominator if we can find a number which is both a multiple of m and a multiple n. In the first example the common multiple was 6 = 3x2 = 2x3. In the second example the common multiple was 15 = 3x5 = 5x3. After staring at these and perhaps doing some more examples (find a common multiple of 2 and 5 or find a common multiple of 3 and 7) we may realize that for any m and n, m x n = n x m is a common multiple of m and n[3]. Thus 10 = 5 x 2 = 2 x 5 is a common multiple of 2 and 5 and 21 = 7 x 3 = 3 x 7 is a common multiple of 3 and 7. To compute I_1/n + I_1/m , we reason as follows. (mxn)* I_1/n = m*(n* I_1/n) = m* I₁ = I_m . So I_1/n = I_m/mxn . Similarly (mxn)* I_1/m = (nxm)* I_1/m = n*(m* I_1/m ) = n* I₁ = I_n . Thus I_1/n+I_1/m = I_m/mxn+I_n/mxn = I_(m+n)/mxn . For example I_1/2+I_1/5 = I_5/10+I_2/10 = I_7/10 .

So far we’ve only added fractional instructions of the form I_1/n+I_1/m but the same technique allows us to handle fractions where the numerator is not 1. For example I_2/3+I_3/5 = 2*I_1/3+3*I_1/5 = 2* I_5/15+3*I_3/15 = 2*(5* I_1/15)+3*(3*I_1/15)=(2x5)* I_1/15+(3x3)*I_1/15 = 10*I_1/15+9*I_1/15 = I_10/15+I_9/15 = I_19/15 .

We’ll revisit adding fractions at the end of this article.

Multiplication of Fractions

In this discussion we will assume all instructions are for fraction machines so that for any instruction J and any n > 0 and m, the instruction ((m/n)*J) exists. For any n > 0 and m we interpret the fraction m/n as the input/output machine, R_m/n , which given an instruction J outputs ((m/n)*J). As with whole numbers we interpret multiplication as connection. This immediately implies the grouping law for multiplication. Thus we interpret (i/j)x(k/m) as the R_i/j * R_k/m .[4] We will first derive the law for multiplying fractions from this definition and the facts above. Then we will look at the corresponding models.

Note that R_1/n = D_n , the divide by n machine. From the green box above we know that R_n/n = R₁ and R_m/1 = R_m . We next show that

(m/n) = (1/n)xm = mx(1/n)

We must show that for any fractional instruction J, the output of R_m/n , R_1/n * R_m , and R_m * R_1/n are equivalent. The output of R_m/n is ((m/n)*J), the unique instruction which when repeated n times is equivalent to m*J. The output of R_1/n * R_m for input J is

The output of R_m * R_1/n for input J is

The equalities at the ends of the diagrams follow from the blue box above.

Next we show that

(1/n)x(1/m) = (1/(nxm))

For any fractional instruction J, (1/(nxm))*J is the unique instruction which when repeated (nxm) times is equivalent to J. We have

(nxm)*((1/n)*((1/m)*J)) = (mxn)*((1/n)*((1/m)*J)) = m*(n*((1/n)*((1/m)*J))) = m*((1/m)*J) = J.

Finally combining the two previous boxes we have the general rule for multiplying fractions

(i/j)x(k/m) = ((i x k)/(j x m)) For example

(2/3)x(4/5) = ((2 x 4)/(3 x 5)) = 8/15

We have (i/j) = ix(1/j) and (k/m)=kx(1/m).

So (i/j) x (k/m) = (i x (1/j)) x (k x (1/m)) = i x ((1/j) x k) x (1/m) =

i x (k x (1/j)) x (1/m) = (i x k) x ((1/j) x (1/m)) =

(i x k) x (1/(j x m)) = ((i x k)/(j x m))

Let’s attempt to understand the law for multiplying fractions from our pulley machine models.

Below we have pictured the pulley machines representing 1/3 and 1/5.

As usual we take the input pulley to be the pulley on the left and the output pulley to be the pulley on the right. For the 1/3 machine 3 turns of the input are required to produce one full turn of the output and for the 1/5 machine 5 turns of the input are required to produce one full turn of the output. We have also labeled equally spaced positions around the outside of the output pulley, 3 such labels, 0, 1/3, 2/3 for the 1/3 machine and 5 such labels, 0, 1/5, 2/5, 3/5, 4/5 for the 1/5 machine and in each case drawn a radius to the position labeled 0. In both cases, each full term of the input pulley will rotate the radius line to the next labeled position. 3 full turns will thus bring the radius back to the 0 position in the case of the 1/3 machine and 5 will bring it back to the 0 position in the case of the 1/5 machine. Now let’s multiply these machines by connecting them to each other and observe the states of the system after consecutive full turns of the input. In the first case we will connect the 1/3 machine to the 1/5 machine.

It requires 3 turns of input to the 1/3 pulley to produce one turn of input to the 1/5 pulley. So it will take 5*(3 turns) = ((5x3) turns) = 15 turns of input to the composite pulley to produce 1 turn of output. So the composite represents a 1/15 machine demonstrating that (1/3 x 1/5) = 1/15.

As an application of fraction multiplication we will convert teaspoons to cups. The Do-It machine for this application consists of a container holding some amount of liquid. Instructions for this machine specify an amount of liquid to add to the container. Thus “Teaspoon” is an instruction to add a teaspoon measure amount of liquid to the container and similarly for “Tablespoon” , “Ounce” and “Cup”. We will use the following information.

• Tablespoon = 3*Teaspoon.
• Ounce = 4*Tablespoon
• Cup = 8*Ounce

Expressing these as equivalent fractional expressions we have:

• Teaspoon = (1/3)*Tablespoon
• Tablespoon = (1/4)*Ounce
• Ounce = (1/8)*Cup

Combining these we have:

Teaspoon = (1/3)*Tablespoon = (1/3)*((1/4)*Ounce) = ((1/3)x(1/4))*Ounce = (1/12)*Ounce =

= (1/12)*((1/8)*Cup) = ((1/12)x(1/8))*Cup = (1/96)*Cup.

We could have also computed this using multiplication of whole numbers.

Cup = 8*Ounce = 8*(4*Tablespoon) = (8x4)*Tablespoon = 32*Tablespoon = 32*(3*Teaspoon) =

= (32x3)*Teaspoon = 96*Teaspoon.

Cup = 96*Teaspoon which is equivalent to Teaspoon = (1/96)*Cup. Both mean that “repeat add a teaspoon 96 times” is equivalent to “add a cup”.

Equality of Fractions

For fractions m/n and j/k we say that m/n = j/k if for any fraction machine we have I_m/n = I_j/k . Recall that if I_m/n is an instruction for a fraction machine then I_m/n is the unique instruction which when repeated n times is equivalent to I_m. So m/n = j/k when for any fraction machine, n* I_j/k = I_m . From our discussion of fraction multiplication we know n* I_j/k .= I_(nxj)/k . So, m/n = j/k just when I_(nxj)/k = I_m . Arguing in the same way, we know that I_(nxj)/k is the unique instruction which when repeated k times is equivalent to I_(nxj) . Thus I_m = I_(nxj)/k just in case k* I_m = I_(nxj) . But k* I_m= I_(kxm) . Putting this together we have m/n = j/k just when for any fraction machine, I_(kxm) = I_(nxj) , but that can only be the case if (k x m) = (n x j). This test is sometimes called the Cross-Multiply test because it involves multiplying the numerator of each side by the denominator of the opposite side.

Summarizing,

Cross-Multiply Equality Test

m/n = j/k just when (k x m) = (n x j).

For example,

4/6 = 2/3 because (3 x 4) = 12 = (2 x 6).

But,

4/6 is not equal 3/5 because (5 x 4)=20 not equal (3 x 6) = 18

Let’s apply the reasoning above directly to the two examples in the box.

4/6 = 2/3 means that 3 x (4/6) = 2. 3 x (4/6) = (3 x 4)/6 = 12/6. 12/6 = 2 means that 6 x 2 = 12.

On the other hand 4/6 = 3/5 would imply that 5 x (4/6) = 3 which would imply that (5 x 4)/6 = 3 which would imply that 6 x 3 = 5 x 4 which is not true.

Next we apply this result to some special cases.

When is m/n = 1? Writing 1 as 1/1 and applying the test, just when 1 x m = n x 1 and since 1 x m = m and n x 1 = n, m/n = 1 just when m = n. Thus 1 = 1/1, 2/2, 3/3, …

m/n = (m/n) x 1 , so for j > 0, m/n = (m/n) x (j/j) = (jxm)/(jxn).

For example 1/3 = (2 x 1)/(2 x 3) = (3 x 1)/(3 x 3) = (4 x 1)/(4 x 3) = …

And so, 1/3 = 2/6 = 3/9 = 4/12 = …

Can there be any fractions equal to 1/3 that are not of the form (j x 1)/(j x 3)?

Suppose m/n = 1/3. Then by the cross-multiply test, 3 x m = n x 1 = n. Thus m/n = m/(3xm) = (mx1)/(mx3). So the answer to the question is no. Thus, all fractions equal to 1/3 can be generated from 1/3 by multiplying the numerator and denominator of 1/3 by the same number. For this reason we call 1/3 a generator for the fractions equal to 1/3.

This leads to the question: For any fraction m/n is there a fraction j/k which is generator for the fractions equal to m/n? For example, 2/6 is not a generator for the fractions equal to 2/6 because 1/3 cannot be written as (2 x m)/(6 x m) for some whole number m. But there is a generator for the fractions equal to 2/6, namely 1/3. Will there always be such a generator?

Let’s try an example, say 4/6. Let’s call a whole number n > 0, a whole number multiplier of 4/6 if (n x 4/6) is a whole number. For example, 6 is a whole number multiplier of 4/6 because, 6 x 4/6 = 4. 12 = 2 x 6 is also a whole number multiplier because 2 x 6 x 4/6 = 2 x (6 x 4/6) = 2 x 4 = 8. In fact any multiple of 6 is a whole number multiplier of 4/6 because (m x 6) x 4/6 = m x (6 x 4/6) = m x 4. There is a connection between whole number multipliers of 4/6 and fractions equal to 4/6.

• If m/n = 4/6 then n x 4/6 = m and so n is a whole number multiplier of 4/6.
• If n is a whole number multiplier of 4/6, say n x 4/6 = m then m/n = 4/6 and so n is a denominator of a fraction equal to 4/6.

We conclude that n is a whole number multiplier of 4/6 if and only if[5] n is the denominator of a fraction equal to 4/6. So we can find all the denominators of fractions equal to 4/6 if we can find the whole number multipliers of 4/6. How can we find the whole number multipliers of 4/6? One way is to set up the experiment below. We have connected an R₄ to an R_1/6 pulley machine to make an R_4/6 pulley machine. We have attached a crank to the input side of the R_4/6 pulley machine and a marked wheel to the output side. The marked wheel has a red line which rotates with the wheel starting in a vertical position. We have also placed six markers at equal intervals around the output wheel. Each full turn of the crank will produce one turn of input to the 4/6 machine which will result in 4/6 of a turn of the output wheel which will cause the red on the output wheel to rotate through four of the markers. Our intention is to count the number of full turns of the crank are required to bring the red line back to a vertical position. This number will be the smallest whole number multiplier of 4/6.

R₄ * R_1/6 = R_4/6

The pictures above show the configurations of the system after each of the first 6 turns of the crank. We observe that the redline on the output wheel returns to vertical, indicating a whole number of output turns, after 3 turns of the input. In fact the output wheel turns exactly twice during the three turns of input. We can also observe that after 3 turns, the entire system is in exactly the same configuration as it was in originally. Consequently, the configurations after turns 4, 5, and 6 must exactly duplicate the configurations after turns 1, 2, and 3 and returns the system to the original configuration after turning the output wheel two more times. If we continue, the system will repeat the same pattern through turns 7, 8, and 9 and then through turns 10,11, and 12 and so returning to original configuration after every multiple of 3 turns with every 3 turns of input resulting in 2 turns of output. Thus 4/6 = 2/3 = 4/6 = 6/9 = …(2 x m)/(3 x m) and so 2/3 is the generator for fractions equal to 4/6.

Now consider any fraction m/n. Imagine that we have set up an experiment analogous to the one above where each turn of the crank results in m/n turns of the output wheel. We can imagine the output wheel has n equally spaced marks and that each turn of the input causes the output wheel to rotate through of the marks. After some number of input turns, say k, the output wheel will return to vertical after turning some whole number of times, say j. (The output wheel will certainly return to vertical after n turns of the input causing the output wheel to turn m times but it may happen sooner. We take k to be the smallest number of inputs that cause the output wheel to return to vertical.) We can imagine the output wheel going through some sequence of configurations like the following.

Since the configuration at k is the same as the configuration at 0, the sequence of configurations for inputs k+1, k+2, …, k+k=2 x k must exactly duplicate the sequence of configurations for 1,2, …,k. And so on. Every k inputs will result in an additional j turns and so m/n = j/k, (2 x j)/(2 x k), (3 x j)/(3 x k) … and so j/k is a generator for the fractions equal to m/n.

Note that our proof actually shows that the generator for fractions equal to m/n is the fraction equal to m/n with the smallest (positive) denominator.

Reducing Fractions

It is considered good form to present fractions in the form of the generator. For example, it is better to present a fraction in the form “2/3” rather than “4/6”, even though they are equal. The generator for a fraction is called the reduced form of the fraction and the process of finding the reduced form for a fraction is called reducing the fraction. For example, 2/3 is the reduced form of 2/3, 4/6, 6/9 and so on. 3/5 is the reduced form of 3/5, 6/10, 9/15, and so on. One advantage of using reduced forms is that we can immediately determine whether two so presented fractions are equal. If m/n and j/k are reduced then m/n = j/k if and only if m=j and n=k. Obviously m/n = m/n. Suppose m/n = j/k and both m/n and j/k are reduced. Then both m/n and j/k are generators and so for some whole numbers c and d > 0, m = c x j, n = c x k, j = d x m, and k = d x n. Using n = c x k and k = d x n we have n = c x k = c x (d x n) = (c x d) x n. Since n is not 0, this implies that (c x d) = 1. Since c and d are both positive whole numbers this can only be the case if c = d = 1 and so k = n and therefore, m = j.

The problem of finding the reduced form of a fraction is called reducing the fraction. How do we go about reducing fractions? One method as illustrated in the previous section is to consider successive multiples of the fraction until we find a whole number multiplier. For example the successive multiples of 2/14 are 2/14, 4/14, 6/14, 8/14, 10/14, 12/14, 14/14 = 1, … From this we see that 7 x (2/14) = 1 and so 2/14 = 1/7.

Another method, involves “eliminating common factors.” If m = c x j for some whole number c we say that c is a factor of m. For example, 14 = 2 x 7, so both 2 and 7 are factors of 14. For every m, m = m x 1 and so every number has itself and 1 as factors. Now suppose m and n both have a factor c > 1 then for some j and k, m = c x j and n = c x k. So m/n = (c x j) /(c x k) = (c/c) x (j/k) = 1 x (j/k) = j/k and so m/n is not reduced. Restating this[6], if m/n is reduced then m and n cannot have a common factor > 1. So to reduce m/n we look for common factors > 1 of m and n. If there aren’t any, m/n is reduced. If we find one, say c such that m = c x j, and n = c x k then we replace m/n by j/k and proceed to reduce j/k. The step of replacing ((c x j )/(c x k)) with (j/k) is called canceling the common factor c. We continue in this way until we find a fraction which can no longer be reduced. For example,

• 2/14 = (2 x 1)/(2 x 7) = 1/7.

• 12/18 = (2 x 6)/(2 x 9) = 6/9 = (3 x 2)/3 x 3) = 2/3.

The Greatest Common Divisor and Euclid’s Algorithm

As just noted, we can reduce fractions by finding and canceling the common factors of the numerator and denominator. As we shall see now, there is an efficient way of finding a single common factor which when canceled will completely reduce the fraction. This single common factor is called the greatest common factor or, more commonly, the greatest common divisor, abbreviated “GCD”, of the numerator and denominator. The method we will describe for finding the GCD of two whole numbers was used and possibly invented by Euclid and is called Euclid’s Algorithm[7].

Definition: The Greatest Common Divisor (GCD) of positive whole numbers a and b is the largest whole number which is a factor of both a and b.We will write GCD(a,b) for the Greatest Common Divisor of a and b. Note that the order in which we list a and b in “GCD(a,b)” doesn’t matter so our convention will be to always list the larger of the two values first. So instead of GCD(24,40) we prefer GCD(40,24).

For example, GCD(60,24) = 12. The other common factors of 24 and 60 are 6, 3, 2, and of course 1. Note that all the common factors are also factors of the GCD. The GCD(80,60) = 20. The other common factors are 10, 5, 4, 2, and 1. Again all the common factors are factors of the GCD. Finally, the GCD(44,16) = 4. The other common factors are 2 and 1 which again are common factors of the GCD. In fact,

GCD Proposition: Let a and b be positive whole numbers. Then all common factors of a and b are factors of GCD(a,b) Further, let c = GCD(a,b), then a/c and b/c have no common factors > 1. Thus, to reduce the fraction (a/b) it suffices to cancel the GCD of a and b.

For example the reduced form of (24/60) = ((24/12)/(60/12)) = (2/5). The reduced form of (60/80) = ((60/20)/(80/20)) = (3/4). The reduced form of (16/44) = ((16/4)/(44/4)) = (4/11).

Before proving the GCD Proposition we give two definitions and make some simple observations.

Definition: Let a and b be positive whole numbers, the Quotient of a and b, written Quotient(a,b) is the largest whole number q such that (q x b) ≤ a. The remainder of a and b, written Remainder(a,b) is a – (Quotient(a,b) x b).

For example Quotient(65,20) = 3, because (3 x 20) = 60 < 65. but 4 x 20 = 80 > 65, and Remainder(65,20) = 65 – (3 x 20) = 65 – 60 = 5.

Quotient(12,6) = 2 and Remainder(12,6) = 0.

Quotient(5,7) = 0 and Remainder(5,7) = 5 – (0 x 7) = 5.

By analogy with a chemical interaction, the remainder is sometimes called the residue. We can think of the quotient of a larger number by a smaller as analogous to a chemical interaction with the smaller consuming as much as it can of the larger leaving the remainder as the residue.

We can also view the Remainder(a,b) as the result of a process in which we repeatedly subtract b from a until we can subtract no more. The part left over is the remainder. For example, Remainder(13,5) = Remainder(13 – 5,5) = Remainder(8,5) = Remainder(8 – 5,5) = Remainder(3,5) = 3.

Euclid’s algorithm is based on the following observations:

• Remainder(a,b) < b

Proof: Let r = Remainder(a,b) and q = Quotient(a,b). Then (q x b)+ r = a < ((q + 1) x b) = (q x b) + b. So r < b.

• If d is a factor of both a and b then d is a factor of Remainder(a,b)

Proof: Let q and r be the Quotient(a,b) and Remainder(a,b) respectively. Then a = (q x b) + r and so a – (q x b) = r. Now suppose is a factor of a and b, say a = d x m and b = d x n. Then r = a – (q x b) = d x m – (q x (d x n)) = d x m – d x (q x n) = d x (m – (q x n)).

• If d is a factor of both b and Remainder(a,b) then d is a factor of a.

Proof: Let q and r be the Quotient(a,b) and Remainder(a,b) respectively and suppose d is a factor of both b and r, say b = d x m and r = d x n. Then a = (q x b) + r = (q x (d x m)) + (d x n) = (d x (q x m)) + (d x n) = d x ((q x m) + n).

The last two observations are illustrated in the following picture. If the purple exactly divides the red and the blue then it must exactly divide the green and if it exactly divides the blue and the green it must exactly divide the red.

As a consequence of the last two observations we have:

• Let a and b be positive whole numbers and let r = Remainder(a,b). Then GCD(a,b) = GCD(b,r).

Proof: Let c be the GCD(b,r). Then c divides both b and r and so c is a divisor of a and hence a divisor of both a and b. Let d = GCD(a,b). Then d divides a and b and so must divide r and so is a common divisor of both b and r and so d ≤ c. Hence c is the largest common divisor of a and b.

Finally, a very simple observation:

• If Remainder(a,b) = 0 then GCD(a,b) = b.

Proof: If Remainder(a,b) = 0 then b exactly divides a and so b is a common factor of both a and b. Since no number larger than b can be a factor of b, b is the largest of b and so the largest common factor of a and b.

We are now ready to present the Euclidean algorithm. We’ll start with an example: computing the GCD(44,16).

As illustrated in the diagram above, our initial problem is to compute GCD(44,16). At each step of the process we have a red box and a blue box containing respectively the larger and the smaller of the two values whose GCD we want to compute. So we start with 44 in the red box and 16 in the blue box. We then compute the remainder of the red and blue values. In this case Remainder(44,16) = 12. From the result above we know that GCD(44,16) = GCD(16,12). So we place 16 in the red box and 12 in the blue box. We have reduced the problem of computing GCD(44,16) to the simpler problem of computing GCD(16,12). We apply the same process to this problem. Remainder(16,12) = 4 so GCD(16,12) = GCD(12,4). Again we have reduced to a simpler problem. We apply the same process to this problem. Remainder(12,4) = 0. Since the remainder is 0, GCD(12,4) = 4 so GCD(16,12) = 4 so GCD(44,16) = 4. When we get a remainder of 0 we can stop.

So the general method of Euclid’s algorithm is as follows. We start with numbers a > b and we wish to compute the GCD(a,b). We compute r = Remainder(a,b). If the remainder is 0 then GCD(a,b) = b. If the remainder is not 0, we apply the same procedure to compute the GCD(b,r).

Two general questions to ask about any algorithm are:

• Will the algorithm eventually produce a result, i.e. does it ever stop
• If it produces a result will the result be the desired on?

Why must the algorithm stop eventually? Each step of the process has an associated problem of the form: compute GCD(c,d) for some positive numbers c and d. The first step is associated with the original problem GCD(a,b). The next step, if there is one, is associated with the problem compute GCD(b,r), r = Remainder(a,b). So we can enumerate the problems associated with the steps as GCD(c₀,d₀), GCD(c₁,d₁), GCD(c₂,d₂), … where c₀ = a, d₀ = b, and c_i+1 = d_i and d_i+1 = Remainder(c_i,d_i). Note that d_i+1 = Remainder(c_i,d_i) < d_i So d₀ > d₁ > d₂ > … Since d is positive this sequence must eventually stop with GCD(c_n,d_n) where Remainder(c_n,d_n) = 0. (In the example the sequence of problems is GCD(44,16), GCD(16,12), GCD(12,4) and we have n = 2, d₀ = 16, d₁ = 12, d₂ = 4.)

So we know the process will stop. Will it produce the correct answer. Using the notation above we know that GCD(c₀,d₀) = GCD(c₁,d₁) = … = GCD(c_n,d_n) so if the value returned for GCD(c_n,d_n) is correct it will be correct for GCD(c₀,d₀). Since Remainder(c_n,d_n ) = 0, GCD(c_n,d_n) = d_n which is the value returned so the algorithm returns the correct value for GCD(a,b).

By analyzing the algorithm we can in fact prove that every common factor of a and b is a factor of GCD(a,b). The idea is that we can work our way backwards through the sequence of steps. Let’s look at our example. In the final step we have GCD(12,4) = 4. Well of course any factor of 12 and 4 must be a factor of 4. At the previous step the problem was GCD(16,12). We know that any common factor of 16 and 12 must be a common factor of 12 and Remainder(16,12) = 4, so must be a common factor of 4. Going to the step before that, which is our original problem, we have that any common factor of (44,16) must be a common factor of 16 and 12 and so a factor of 4. The same reasoning can be applied toany case. Using the notation above, we know that any common factors of c_n, d_n are factors of d_n = GCD(c_n,d_n). We also know that any common factors of a = c₀,b = d₀ are common factors of c₁,d₁ which are common factors of (c₂,d₂) which are common factors of … (c_n-1,d_n-1) which are common factors of (c_n,d_n) and so are common factors of d_n = GCD(a,b). This proves the first part of the GCD Proposition, i.e that any common factors of a and b are factors of GCD(a,b). The second part says that a/c, and b/c where c = GCD(a,b) have no common factors > 1. Suppose for contradiction that they did have a common factor, say d > 1. Then we would have a/c = d x m and b/c = d x n for some n and m. But then we would have a =c x d x m and b = c x d x n for some m and n and so (c x d) would be a common factor of a and b. But since d > 1, (c x d) > c contradicting the assumption that c is the largest common factor of a and b.

Un-machines for Fractions

Does R_(5/3) have an un-machine and if so is it a fraction machine? Let’s look at the pulley-machine representation of R_(5/3) and then look at the result of reversing the pulley machine to get its un-machine.

3

It appears that Un-R_5/3 = R₃ * R_1/5 = R_3/5. Indeed, we can verify this directly:

R_3/5 * R_5/3 = R_(3/5)x(5/3) = R_(3x5)/(5x3) = R_15/15 = R₁ and

R_5/3 * R_3/5 = R_(5/3)x(3/5) = R_(5x3)/(3x5) = R_15/15 = R₁

In fact, for any non-zero whole numbers m and n, we have

R_m/n* R_n/m = R_(m/n)x(n/m) = R_(mxn)/(nxm) = R_(mxn/mxm) = R₁

Stating this in terms of fractional numbers

For any positive whole numbers m and n,

(m/n) x (n/m) = 1

n/m is called the reciprocal of m/n

Division

If p and q are fractions and R_q has an un-machine, we define a new machine (R_p divided-by R_q ) to be (R_p * un- R_q ).

Using the result above we have

For any positive whole numbers j, m and n,

R_i/j divided-by R_m/n = R_i/j * R_n/m= R(_{i/j )x(n/m)} = R_(ixn)/(jxm)

Based on this we define division on fractional numbers by

For any positive whole numbers j, m and n we define

(i/j)divided-by (m/n) = (i/j)x(n/m) = (ixn)/(jxm).

As special cases we have

(m divided-by n) = ((m/1) divided-by (n/1)) = (m/1)x(1/n) = m/n

(m divided-by (1/n)) = ((m/1) divided-by (1/n)) = (m/1)x(n/1) = mxn

((m/n) divided-by (m/n)) = (m/n) x (n/m) = (m x n)/(n x m) = 1

In words, dividing by a fraction is defined as multiplication by the reciprocal of the fraction. So for example, dividing by (1/2) is the same as multiplying by 2 and dividing by 2 = 2/1 is equivalent to multiplying by ½.

A common application of division is to solve problems with the following general form: We wish to repeat some instruction some number of times to achieve some total effect. Either we know how many times the instruction will be repeated, in which case the problem is to determine what instruction to execute, or we know what instruction will be executed and our problem is to determine how many times to repeat it. We give an example of each kind of problem.

• We wish to divide 1/2 gallon of ice cream equally among 12 people. How much should we give each person?
• How many ½ cup servings can we make from 3 gallons of ice cream?

In the first problem, we are given the number of times (12) to repeat some unknown instruction and the total effect (give out 1/2 of a gallon of ice cream) and the problem is to determine what the instruction should be. .

In the second problem, the instruction, “give out a ½ cup serving”, and the total effect, “give out 3 gallons” are given and the problem is to determine how many times to repeat the instruction

Note that the answer to the first problem is an instruction. In most applications, instructions are equipped with units. In the first problem the result is an instruction is to give out some measure of ice cream and that measure will be specified in gallons or cups or ounces or something. Note that when we use units we can generally leave off the repeat operator ‘*’. Thus 3*Gallon can just be written as 3 Gallon. The answer to the second problem is a pure number corresponding to a repeat count. It will have no units.

The solution to the first problem is a straightforward application of unmachines. Some unknown input is fed into a known machine and produces a known output. To solve the problem we feed the known output into the unmachine. In this case the machine multiplies by 12 and so the unmachine divides by 12 which means multiply by 1/12. The output is ½ Gallon so the input must be ½ x 1/12 Gallon = 1/24 Gallon. Knowing that 1 Gallon = 4*Quart = 4 *(4*Cup) = (4 x 4)*Cup = 16*Cup we can compute the input in cups as (1/24)*(16*Cup) = ((1/24)x16)*Cup = 16/24 * Cup = ((8 x 2)/(8 x 3)) * Cup = 2/3 Cup. Note that when we divide an instruction by a pure number such as a repeat count the result is again an instruction. If the instruction is equipped with unit the result of dividing by a number will be equipped with the same units.

The second problem involves a different model that requires us to “divide instructions” resulting in a pure number. A pure number resulting from dividing two instructions is sometimes called a ratio.

Ratios of instructions

Suppose I₁ and I₂ are instructions for the same DO-IT machine. A number r is called the ratio of I₂ to I_1, which we may write as “I₂/I₁“ or sometimes “I₂:I₁“ or sometimes “I₁(s) per I₂“, if r * I₁ = I₂.

For example, consider the liquid measure machine instructions Cup and Gallon. The ratio of Gallon to Cup = Gallon/Cup = Gallon : Cup = Cups per Gallon = 16. Reversing we have The ratio of Cup to Gallon = Cup/Gallon = Cup : Gallon = Gallons per Cup = 1/16. Note the following:

• If m*I₁ = n*I₂ then I₂/I₁ = m/n. Proof: (m/n)* I₁ = (1/n)*(m* I₁ ) =((1/n)*(n* I₂ )= ((1/n) x n)* I₂ = (n/n)* I₂ = 1* I₂ = I₂ .
• (p*I)/(q*I) = (p/q). Proof: (p/q)*(q*I) = ((p/q) x q)*I = ((p x q)/q)*I = (p x (q/q))*I = (p x 1)*I = p*I.
• (p* I₂)/(q*I₁)= (p/q)x(I₂/I₁). Proof: By definition, (I₂/I₁)*I₁ = I₂. So (p* I₂)/(q*I₁) = (p*((I₂/I₁)*I₁))/(q*I₁) = ((p x (I₂/I₁))*I₁)/(q*I₁) = (p x (I₂/I₁))/q = (p/q) x (I₂/I₁).

For example,

• 16 * Cup = Gallon, so Gallon/Cup = 16 and Cup/Gallon = 1/16.
• ((3/2)*Cup)/((3/4)*Cup) = (3/2)/(3/4) = (3/2)x(4/3) = (3 x 4)/(2 x 3) = 12/6 = 2.
• (3*Gallon)/((1/2)*Cup) = (3/(1/2))x(Gallon/Cup) = (3x2)x(Gallon/Cup) = 6 x 16 = 96.

Going back to the second problem above we have

?*((1/2)*Cup) = 3*Gallon. So ? = (3*Gallon)/((1/2)*Cup) = 96

The Rational Numbers

In this section we define the rational numbers to be numbers corresponding to fractions and their negatives. The term rational derives from the interpretation of a fraction as a ratio as discussed above. We will also derive and summarize the laws of arithmetic for the rational numbers. In this section, all Do-It machines are assumed to be fractional machines for which negative instructions exist. The latter requirement means that for every instruction I there is an instruction -I such that (I;-I)=(-I;I) = Do-Nothing. As noted in Article II, negative instructions where they exist are unique. (Suppose –I exists and J is an instruction satisfying (I;J)=(J;I) = Do-Nothing. Then we have –I = (-I;Do-nothing)= (-I;(I;J)) = ((-I;I);J) = (Do-Nothing;J) = J.) We also have, -(-I) = I, since as required for –(-I), (-I;I) = (I;-I)= Do-Nothing.

Also as in Article II, for m a positive whole number we define (-m)*I = m*(-I), (e.g., “take (-3) steps forward” means “take 3 backward steps.”).

Note: (-m)*I = m*(-I) = -(m*I), e.g. “take (-3) steps forward” means “take 3 backward steps” = “take 3 steps backwards”.

Proof: (-m)*I = m*(-I) by definition. Using the distributive law for repeating instructions, ((m*(-I));(m*I)) = m*(-I;I) = m*Do-Nothing = Do-Nothing and (m*I;m*(-I)) = m*(I;-I) = m*Do-Nothing = Do-Nothing. So m*(-I) satisfies the requirements for –(m*I) so by the uniqueness result must = -(m*I).

For any whole numbers, j and k with k not equal to 0, we define (j/k)*I to be an instruction J such that k*J = j*I. There are 4 cases depending on the signs of j and k. Taking m and n to be positive whole numbers the cases are:

• (m/n)*I, e.g., (2/5)*I
• ((-m)/n)*I, e.g. (-2/5)*I
• (m/(-n))*I, e.g. (2/(-5))*I
• ((-m)/(-n))*I, e.g. (-2/-5)*I

The following equalities relate the last three cases to the first.

• ((-m)/n)*I = -((m/n)*I), e.g. ((-2)/5)*I = -((2/5)*I)
• (m/(-n))*I = -((m/n)*I), e.g. (2/(-5))*I = -((2/5)*I)
• ((-m)/(-n))*I = (m/n)*I, e.g. ((-2)/(-5))*I = (2/5)*I

Proofs:

• Suppose J = ((-m)/n)*I. Then n*J = (-m)*I = -(m*I). So –(n*J) = m*I, so, using –(n*J) = n*(-J), n*(-J)=m*I so –J = (m/n)*I, so J = -((m/n)*J).
• Suppose J = (m/(-n))*I. Then (-n)*J = (m)*I. So, using (-n)*J=-n*(-J), n*(-J)=m*I so –J = (m/n)*I, so J = -((m/n)*J).
• Suppose J=((-m)/(-n))*I. Then (-n)*J = (-m)*I, so , applying the green note above to both sides, –(n*J) = -(m*I). So -(-(n*J)) = -(-(m*I)), so n*J = m*I, so J = (m/n)*I.

For non-negative whole numbers m and n with n > 0 we define R_-(m/n) to be the input/output machine which for input instruction I generates output –((m/n)*I). For any whole numbers j and k with k not equal to 0 we define R_j/k to be the input /output machine which for input instruction I generates output instruction (j/k)*I. From the red bulleted results above it follows that for every j and k, k not equal to 0, there are non-negative whole numbers m and n with n > 0 such that R_j/k = R_m/n or R_j/k = R_-m/n.

We define the rational numbers to be the collection of all machines of the form R_m/n and R_-m/n for some non-negative m and n with n > 0. For any whole numbers j and k with k not equal to 0 we interpret the fraction j/k as the rational R_j/k. We say that j/k denotes R_j/k or that j/k represents R_j/k. We interpret ‘j/k = p/q’ to mean that R_j/k = R_p/q. We interpret `(j/k)x(p/q)’ to be the input/output machine R<sub>j/k</sub>*R<sub>p/q</sub>. We interpret `j/k + p/q’ to be the input output machine which for input instruction I, produces output instruction ((j/k)*I;(p/q)*I). We define`-(j/k)’ to be –1 x (j/k). We define `(j/k) – (p/q)’ to be `(j/k)+(-(p/q)). We define `(j/k)/(p/q)’ for p not equal to 0 to be `(j/k)x(q/p)’. Under these interpretations, we have the following results for rational arithmetic. (The names assigned to some of the results will be explained below.)

• Multiplication is Associative: For any rational numbers (j/k), (p/q), (r/s) ((j/k) x (p/q)) x (r/s) = (j/k) x ((p/q) x (r/s)).

Proof: multiplication is defined by connection and connection is associative, i.e., for connectable input/output machines R, S, and T, (R*S)*T = R*(S*T). We obtain the result by applying this with R = R_(j/k), S = R_(p/q), and T = R_(r/s).

• Multiplication: (p/q)x(j/k) = (j x p)/(k x q), e.g. (-2/5)x(3/4) = ((-2)x3)/(5x4) = (-6)/20 = -(6/20) = -(3/10)

Proof: We must show that R_(p/q)*R_(j/k) = R_(jxp)/(kxq). For input I the left hand side outputs J = (j/k)*((p/q)*I) and the right hand side outputs K = ((jxp)/(kxq))*I. We must show that J = K. J satisfies k*J = j*(p/q)*I. K is the unique instruction with the (kxq)*K = (jxp)*I. We have (kxq)*J = (qxk)*J = q*(k*J) = q*(j*(p/q)*I) = (qxj)*((p/q)*I) = (jxq)*((p/q)*I) = j*(q*((p/q)*I)) = j*(p*I) = (jxp)*I. The blue equality follows from the definition of J and the green equality follows from the definition of ((p/q)*I). So J satisfies the definition of K and so J=K.

• Closure Under Multiplication: The product of two rational numbers is a rational number.

Proof: In the previous result note that (j x p)/(k x q) is rational.

• Multiplication is Commutative: (p/q)x(j/k) = (pxj)/(qxk) = (jxp)/(kxq) = (j/k)x(p/q)
• One: For any j not equal to 0, (j/j) = 1, hence 1 is rational, e.g. (-2/-2) = (10/10) = 1/1 = 1

Proof: For input I, R_(j/j) outputs (j/j)*I. We must show that (j/j)*I = 1*I. (j/j)*I is the unique instruction Ksatisfying j*K = j*I. Well of course j*I = j*I so I = (j/j)*I and so since 1*I = I, 1*I = (j/j)*I.

• Multiplicative Identity (uniqueness): (j/k)x1 = 1x(j/k) = (j/k)

Proof: (j/k)x1 = (j/k)x(1/1) = (jx1)/(kx1) = j/k

• Multiplicative Identity (uniqueness): if (j/k)x(p/q) = (j/k) for all (j/k) then (p/q) = 1.

Proof: Suppose (j/k) x (p/q) = (j/k) for all (j/k). Then, in particular, 1 = (1/1) = (1/1)x(p/q). But (1/1)x(p/q) = (p/q). So 1 = (p/q)

• Integers are Rational: For any integer j, (j/1) = j, hence the rational numbers include the integers.

Proof: 1*(j*I) = j*I so j*I satisfies the definition of (j/1).

• Closure under Division by Non-Zero Rational: for p not equal to 0, (j/k)/(p/q) = (q x j)/(p x k), hence the result of dividing a rational number by a rational number other than 0 is again a rational number, e.g. (-2/5)/(3/4) = ((-2)x4)/5x3 = -8/15

Proof: By definition (j/k)/(p/q) = (j/k)x(q/p) = (jxq)/(kxp) = (qxj)/(pxk)

• Multiplicative Inverses (Existence): for j not equal to 0, (j/k)*(k/j) = (j/k)/(j/k) = 1.

Proof: (j/k)/(j/k) = (kxj)/(jxk) = (jxk)/(jxk) = 1.

• Multiplicative Inverses (Uniqueness): If (j/k)/(p/q) = 1 then (p/q) = (j/k)

Proof: Suppose (j/k)/(p/q) = 1. Then ((j/k)x(q/p) = 1 so ((j/k)x(q/p)) x (p/q) = 1 x (p/q) = (p/q). ((j/k)x(q/p))x (p/q) = (j/k)x((q/p)x(p/q)) = (j/k)x1 = (j/k). So j/k = p/q

• Multiplication Distributes Over Addition: (r/s)x((j/k)+(p/q)) = ((r/s) x (j/k))+((r/s) x (p/q))

Proof: We must show that R_{(r/s)x((j/k)+(p/q))} = R_{((r/s) x (j/k))+((r/s) x (p/q))}. The output of the left side machine for input I is ((j/k)+(p/q))*((r/s)*I) = ((j/k)*((r/s)*I);(p/q)*((r/s)*I)) = (((r/s)x(j/k))+((r/s)x(p/q)))*I

• Addition With Common Denominator: (j/k)+(p/k) = (j+p)/k

Proof: kx((j/k)+(p/k)) = (kx(j/k)+kx(p/k)) = (j+p). So for any I, k*(((j/k)+(p/k)))*I = (j+p)*I so ((j/k)+(p/k)) = (j+p)/k.

• Closure Under Addition: (j/k) + (p/q) = ((j x q)+(k x p))/(k x q), hence the result of adding two rational numbers is a rational, e.g. (-2/5) + (3/4) = (((-2)x4) + (5x3))/(5x4) = (-8+15)/20 = 7/20

Proof: (j/k) = (j/k)x1 = (j/k)x(q/q) = (jxq)/(kxq). Also, (p/q)=(p/q)x1 = (p/q)x(k/k) = (p x k)/(q x k) = (k x p)/(k x q) . So (j/k) + (p/q) = ((j x q)/(k x q)) + ((k x p)/(k x q)) = ((j x q) + (k x p))/(k x q)

• Addition is Commutative: (j/k) + (p/q) = (p/q) + (j/k)

Proof: Using the result above and the fact that multiplication and addition of integers are commutative, (j/k)+(p/q) = ((j x q)+(k x p))/(k x q) = ((q x j)+(p x k))/(q x k) = ((p x k) + (q x j))/(q x k) = (p/q) + (j/k)

• Additive Identity (existence): (j/k)+0 = 0+(j/k)

Proof: On input I, R_(j/k)+0 outputs ((j/k)*I;0*I) = ((j/k)*I;Do-Nothing) = (j/k)*I

• Additive Identity (uniqueness): if (j/k) + (p/q) = (j/k) for all (j/k) then (p/q) = 0.

Proof: if (j/k) + (p/q) = (j/k) for all (j/k) then, in particular, 0 = 0 + (p/q) = (p/q)

• Addition is Associative: ((j/k) + (p/q))+(r/s) = (j/k)+((p/q)+(r/s))

Proof: This follows directly from the definition of rational addition and the fact that instruction sequencing is associative. Specifically, on input I, R_{((j/k) + (p/q))+(r/s)} outputs ((j/k)*I;((p/q)*I;(r/s)*I)) = (((j/k)*I;(p/q)*I);(r/s)*I) = the output of R_{(j/k) + ((p/q))+(r/s))} on input I.

• Multiplication by 0: (j/k)x0 = 0.

Proof: R_(j/k)x0 = R_(j/k)*R₀ which on input I outputs 0*((j/k)*I) = Do-Nothing

• Zero: (p/q) = 0 if and only if p = 0.

Proof: We first show that 0/q = 0. For any j/k we have (j/k) + (0/q) = ((j x q)+(k x 0))/(k x q) = ((j x q)+0)/(k x q) = (j x q)/(k x q) = (j/k) x (q/q) = (j/k) x 1 = (j/k). So 0/q = 0.

Now suppose (p/q) = 0. If p were not equal to 0 we could form the fraction (q/p) and so we would have 1 = (q/p)x(p/q) = (q/p) x 0 = 0. So p must equal 0.

• Multiplication by –1: (-1)x(j/k) = ((-j)/k)

Proof: (-1) x (j/k) = ((-1)/1) x (j/k) = ((-1) x j)/(1 x k) = (-j)/k

• Additive Inverse (existence): (j/k) + (-j/k) = 0

Proof: (j/k) + (-j/k) = (1xj/1xk) + ((-1)xj/1xk) = (j/k)x(1/1) + (j/k)x(-1/1) = (j/k)x1 + (j/k)x(-1) = (j/k)x(1+(-1)) = (j/k)x0 = 0

• Additive Inverse (uniqueness): if (j/k) + (p/q) = 0 then (p/q) = (-j/k)

Proof: Suppose (j/k) + (p/q) = 0. Then (-j/k) = (-j/k) + 0 = (-j/k) + ((j/k) + (p/q)) = ((-j/k) + (j/k)) + (p/q) = ((j/k) + (-j/k)) + (p/q) = 0 + (p/q) = (p/q) + 0 = (p/q)

• Closure Under Subtraction: (j/k) – (p/q) = ((j x q) – (k x p))/(k x q), hence, the result of subtracting a rational number from a rational number is a rational number, e.g. (-2/5) – (3/4) = (((-2)x4) – (5x3))/(5x4) = (-8+(-15))/20 = (-23)/20

Proof: (j/k) – (p/q) = (j/k) + -1x(p/q) = (j/k) + (-p/q) = ((j x q) + ((-p) x k))/(k x q) =

((j x q) + -(p x k))/(k x q) = ((j x q) – (p x k))/(k x q) = ((j x q) – (k x p))/(k x q)

• Equality: (j/k) = (p/q) if and only if (j/k) – (p/q) = 0

Proof: if (j/k) = (p/q) then (j/k) – (p/q) = (j/k) – (j/k) = (j/k)+ (-1)x(j/k) = (j/k) + ((-j)/k) = 0. If (j/k) – (p/q) = 0 then (p/q) = 0 + (p/q) = ((j/k) – (p/q)) + (p/q) = ((j/k) + (-1)x(p/q)) + (p/q) = (j/k) + ((-1)x(p/q) + (p/q)) = (j/k) + ((-1)x(p/q) + (1)x(p/q)) = (j/k) + (-1 + 1)x(p/q) = (j/k) + 0x(p/q) = (j/k) + 0 = (j/k).

• Equality: (j/k) = (p/q) if and only if (j x q) = (k x p)

Proof: (j/k) = (p/q) if and only if (j/k) – (p/q) = 0 if and only if ((j x q) – (k x p))/(k x p) = 0 if and only if ((j x q) – (k x p)) = 0 if and only if (j x q) = (k x p).

Terminology Used Above

Suppose “@” is some kind of operator that operates on two value: so that given two values x and y of some appropriate type, (x @ y) denotes a value. Examples we have discussed of such operators include the connection operator, “*”, used to connect two input/output machines, S and T, of appropriate type to form a new input/output machine, (S*T), the sequencing operator, “;” used to sequence two instructions I and J for a given Do-It machine to form a new instructions ‘(I;J)’, and the operators of arithmetic, +, x, -, / defined above.

• A collection of values V is said to be closed under @, if whenever x and y are values in V, (x @ y) is also in V.
• The collection of non-negative whole numbers is closed with respect to + because if m and n are non-negative whole numbers, (m+n) is again a non-negative whole number
• The collection of non-negative whole numbers is not closed under -, for example, (2 – 3) is not a non-negative whole number.
• The integers, i.e. the collection of all whole numbers, positive, negative, or zero is closed under +, -, and * but not closed under /.
• @ is said to be associative if for any values, x, y, and z, if ((x @ y) @ z) is defined then (x @ (y @ z)) is defined and ((x @ y) @ z) = (x @ (y @ z)).
• Connection, sequencing, +, and * are associative.
• – is not associative: ((5 – 2) – 1) = 3 – 1 = 2. But (5 – (2 – 1)) = (5 –1) = 4.
• / is not associative: ((12 / 2) / 2) = (6 / 2) = 3. But (12 / (2 / 2)) = (12 / 1) = 12
• @ is said to be commutative if whenever (x @ y) and (y @ x) are defined, we have (x @ y)= (y @ x)
• + and * are commutative.
• Sequencing is not commutative: (“put on shoes” ; “put on socks”) is not equal to (“put on socks” ; “put on shoes”)
• Connection is not commutative: [add 2] * [multiply by 3] is not equal to [multiply by 3] * [add 2]. For input 1, the first machine outputs (1 + 2) x 3 = 9 while the second outputs (3 x 1) + 2 = 5.
• – and / are not commutative: (4 – 2) = 2 but (2 – 4) = -2 and (4/2) = 2 but (2 / 4) = ½.
• A value I is an identity for @ if for any value x, (x @ I) = (I @ x) = x
• “Do-Nothing” is the identity for sequencing.
• The identity machine is the identity for connection
• 0 is the identity for +
• 1 is the identity for x
• When an identity exists it is unique for suppose I and J are identities for @ then because I is an identity, (I @ J) = J, and because J is an identity (I @ J) = I. So I=J.
• If @ has an identity I then a value y is called an inverse for x under @ if (x @ y) = (y @ x) = I.
• Note that if y is an inverse of x under @ then x is an inverse of y under @.
• Note that for associative operators, if an inverse exists, it is unique. For suppose z and y are inverses of x. Then z = (I @ z) = ((y @ x) @ z) = (y @ (x @ z)) = (y @ I) = y
• (-2) and 2 are inverses under +
• (1/2) and 2 are inverses under multiplication
• If “$” is another operator we say, @ distributes over $ if (x @ (y $ z)) = ((x $ Y) @ (x $ z))
• ‘x’ distributes over ‘+’.
• A collection of values V together with operators @ and $ is called a field if
• V is closed under @ and $, e.g. rational numbers with ‘x’ and ‘+’
• @ and $ are associative
• @ and $ are commutative
• Identities exist for both @ and $
• Every value in V has an inverse under $
• Every value in V other than the identity under $ has an inverse under @
• @ distributes over $
• Thus the rational numbers under multiplication and addition form a field.

Ordering of the Rational Numbers

We say that a rational number is positive if it is denoted by a fraction of the form m/n where both m and n are > 0. We that a rational number is negative if it is denoted by a fraction of the form (-m)/n where m and n are > 0.

• Every rational number is denoted by a fraction of the form j/k where k is positive.

Proof: Let r be rational denoted by fraction p/q. If q is positive then we take j/k to be p/q. Otherwise, (p/q) = 1 x (p/q) = ((-1)/(-1))x(p/q) = ((-p)/(-q)) and so we can take j/k to be ((-p)/(-q)).

• Every rational number is exactly one of positive, negative, or 0.

Proof: Let r be a rational number and let (j/k) with k positive denote r. If r = 0 then every fraction denoting r is of the form (0/k) so r is not positive or negative. If j > 0 then r is positive and if j < 0 then r is negative. It remains to show that r cannot be both positive and negative. Suppose r were both positive and negative. Then for some j,k, p and q all > 0, we would have (j/k) = ((-p)/q) and so (j x q) = ((-p) x k). But (j x q) > 0 and ((-p) x k) = -(p x k) < 0 and so (j x q) would have to be both > 0 and < 0. Since this is impossible, r cannot be both positive and negative[8].

• If r is positive then (-r) is negative and if r is negative (-r) is positive.

Proof: if r = (m/n) with m,n > 0 then –r = (-1)xr = ((-m)/n) and so –r is negative. If r = ((-m)/n) with m,n > 0 then –r = ((-(-m))/n) = (m/n) and so –r is positive.

• -(s – r) = (r – s)

Proof: -(s – r) = (-1)x(s – r) = (-1)x(s + (-1)xr) = ((-1)xs + (-1)x((-1)xr)) = (-1)xr + ((-1)x(-1))xs = (-1)xr + 1xs = (-r) + s = s + (-r) = s – r.

• The sum of two positive rational numbers is positive.

Proof: Suppose r and s are positive, say r = m/n and s = (p/q) with all of m,n,p, and q > 0. Then r + s = (m/n) + (p/q) = ((m x q) + (p x n))/(n x q) which is positive.

• The product of two positive numbers is positive. The product of two negative numbers is positive. The product of a negative and a positive number is negative.

Proof: let m,n,p, q all be positive. Then (m/n)x(p/q) = ((m x p)/(n x q)), ((-m)/n)x((-p)/q) = ((-m) x (-p))/(n x q) = ((m x p)/(n x q)). (m/n) x ((-p)/q) = (m x (-p))/(n x q) = (-(m x p))/(n x q).

• Order: We define the ordering, < , of the rational numbers by (r < s) if (s – r) is positive. We define (r > s) to mean (s < r).
• Totality: For all rational numbers r and s, exactly one of the following is true:
• r < s
• r = s
• s < r

Proof: (s – r) is exactly one of positive, zero, and negative. In the first case, r < s. In the second r = s. In the third case, -(s – r) is positive, so (r –s) is positive, so s < r.

• Transitivity: For all rational numbers r, s and t, if (r < s) and (s < t), then (r < t).

Proof: Suppose r < s and s < t. Then (t – s) and (s – r) are positive. Then, as discovered from the picture below, (t – s) + (s – r) = (t + (-s)) + (s – r) = t + ((-s) + s) + (-r) = t + 0 + (-r) = t + (-r) = (t – r). So (t –r ) = (t – s) + (s – r) so (t – r) is positive.

• A rational number is positive if and only if it is > 0. A rational number is negative if and only if it is < 0.

Proof: (r > 0) if and only if (r – 0) is positive if and only if r is positive.

(r < 0) if and only if (r – 0) is negative if and only if r is negative.

• Addition Preserves Order: if s < t then for any r, (r + s) < (r + t).

Proof: (r + t) – (r + s) = (r + t) + (-1)x(r + s) = (r + t) + ((-1)xr + (-1)xs) = (r + t) + (-r + -s) = (t + r) + (-r + -s) = (t + (r + -r))+(-s) = (t + 0) + -s = (t + (-s)) = (t – s). So if (t – s) is positive then so is (r + t) – (r + s).

(t – s)

(t – s)

• Multiplication by a Positive Preserves Order: if s < t then for any positive r, (r x s) < (r x t).

Proof: (r x t) – (r x s) = (r x t) + (-1)x(r x s) = (r x t) + ((-1)xr)xs) = (r x t) + ((r x (-1))xs) = (r x t) + (r x ((-1) x s)) = r x (t + ((-1) x s)) = r x (t – s). Since the product of two positives is positive, if r is positive and (s < t) so that (t – s) is positive then r x (t – s) will be positive and so (r x t) – (r x s) will be positive and so (r x s) < (r x t).

• Multiplication by a Negative Reverses Order: if s < t then for any negative rational number r, (r x t) < (r x s)

Proof: As in the previous result, (r x t) – (r x s) = r x (t – s). If (t – s) is positive and r is negative then r x (t – s) is negative and so (r x t) – (r x s) is negative, so (r x s) – (r x t) is positve and so (r x t) < (r x s).

The Rational Number Line:

We can construct a model of the rational number ordering using a Do-It machine consisting of a line which is infinite in both directions and a movable pointer which points to positions on the line. We choose an arbitrary position on the line as the start state of the pointer, and an arbitrary unit of distance. We take the unit instruction to be “move the pointer one unit of distance to the right”. We then represent rational numbers as positions (points) on the line. We will call this collection of states the rational number line.

We can imagine filling in the positions on this line, starting with the integer positions, and then adding the positions corresponding to multiples of ½, 1/3, ¼, and so on as in the following sequence of illustrations.

We notice that as n becomes larger, the spacing between multiples of 1/n becomes smaller and thus the density of multiples of 1/n increases.

For any rational number r, we define the absolute value of r, written |r|, to be r if r is positive and –r if r is negative. For example, |2| = |-2| = 2 and |1/2| = |-1/2| = ½. In general, |r| is 0 if r is 0 and otherwise is positive and |r| = |-r|. In terms of our rational number line, |r|, represents the distance of r, in the units used to define the number line, of r from the origin.

|r|

|r|

More generally, for rational numbers s and t, |t – s| represents the distance between s and t.

This distance formula is convenient for finding points between given points s and t. For example, if s < t then the rational number corresponding to the midpoint between s and t is given by s+(|t– s|/2)

|t – s|

	s	s + (|t – s|/2)	t

Similarly we can compute a point 1/3 of the way between s and t as s + (|t – s|/3)

Since the rational are so densely packed it is natural to ask whether every point on the line corresponds to a rational number? This question will be discussed in the next section. Preliminary to that we ask whether the rational numbers satisfy a weaker condition: Does every interval in the line containing more than one point include a rational point? If every point is rational this is certainly true but this condition only asks that the rational points be densely packed and extend throughout the line. To prove this we need an assumption about the line that rules out “infinitesimally small” intervals.

• No Infinitesimals Assumption: For any finite line segments L and M there is some whole number n such that a line segment formed from n copies of L is at least as long as M. (This rules out the possibility for example that you could have an interval so infinitesimally small that no matter how many copies you put together it would still be infinitesimally small.)

• On the rational number line, for any finite line segment M there is some whole number n such that M is shorter than a line segment of length n.

Proof: Take L in the No Infinitesimals Assumption to be the line segment from 0 to 1 and take n such that n copies of L are longer than M.

• On the rational number line, for any line segment M there is a whole number n such that M is to the left of n

Proof: If M is to the left of 0 then take n to be 0. If M does not include 0 then extend it so that it does and take n to be such that M is shorter than a line segment of length n.

• On the rational number line, for any line segment M there is a whole number j such that M is to the right of j

Proof: If M is to the right of 0 then take j to be 0. If M does not include 0 then extend it so that it does and take j = -n where n is such that M is shorter than a line segment of length n.

• On the rational number line, for any line segment M there is a positive whole number n such that M is longer than a line segment of length 1/n.

Proof: Choose n such that n copies of M are longer than a unit line segment. Then, since n copies of lines of length 1/n have total length 1 which is less than the total length of n copies of M, M must be longer than a line segment of length 1/n.

• The Rational Points are Dense in the Rational Number Line: On the rational number line every line segment contains a rational point.

Proof: Let M be a line segment. We can assume M is finite because if it’s not then replace M with a finite part of M; any rational point in the part will also be in the whole. We know from the previous remarks that there are whole numbers j and k such that M is between j and k. Take j to be the largest whole number point to the left of M. If j+1 is in M then j+1 is a rational point in M. So assume that M is strictly between j and j+1. Now choose n such that a line segment of length 1/n is shorter than M and divide the segment between j and j+1 into n sub-segments of length 1/n. The endpoints: j, j+(1/n), j+(2/n),… j+1 are all rational points. J is to the left M and j+1 is to the right of M so there is a largest one of these point, j + (k/n), which is to the left of M. Then j + ((k+1)/n) is not to the left of M so it is either in M or to the right of M. But the segment from (j + (k/n)) to (j + ((k+1)/n)) has length 1/n and so is shorter than M and (j + (k/n)) is to the left of M, so (j + ((k+1)/n)) can only be in M which provides us with a rational point in M.

In the next section we will take up the question of whether there are points on the line which are not rational.

---

[1] It’s not too hard to come up with a Do-It machine for which there is more than one instruction which when repeated twice is equivalent to the unit instruction. For example, consider a machine which moves a football player around a field. Take our unit instruction to be “move the player one yard directly towards the opposite goal.” In addition to the straightforward “1/2” instruction we can also design instructions which “zig-zag” him down the field moving him ½ yard toward the opposite goal but also moving him parallel to the goal line up or down depending on whether he’s zigging or zagging so that repeating the instruction twice is equivalent to the unit instruction. The addition we get for this machine will not be commutative. It takes a little more thought to come up with a commutative machine with multiple versions of fractional instructions. (For example consider a machine which moves a tank in a fixed direction and rotates the turret by some number of degrees so that canon can end up pointing in different directions. The state of the machine is determined by the location of the tank and the direction of the canon. An instruction has two parts: how far to move the tank and how many degrees to rotate the turret. The unit instruction moves the tank one yard with no rotation.) Of course, as our argument for the measure machine shows, for such machines the instructions cannot be ordered in a manner that is preserved by addition (I < J implies I + I < J + J).

[2] The point I’m trying to make in the following presentation is that it may be possible through a combinartion of emperical and logical deduction, with the guidance of a teacher, for an elementary school student to discover the method for adding fractions. I think it is at least possible that this process could involve several of the kinds of “Ah ha!” moments that so many of us that enjoy mathematical and scientific reasoning find so rewarding. Even the problem of finding common multiples could involve such a discovery. Why in the world should we believe that the sequences 7, 14, 21, … and 13, 26, 39, … should have elements in common?

[3] I think there’s a potentially interesting emperical exercise in considering least common multiples or at least when is it the case that there are common multiples smaller than mxn? It would be interesting to see if students could get anywhere in terms of hypotheses and even proofs. Special cases for particular values of m could include m and m, m and 2m, m and mxn, 2xm and 2xn

[4] In this case we won’t bother reversing the order of the machines. We’ll just prove multiplication is commutative and not worry about it.

[5] “if and only if” is a mathematical cliché which means that two statements are equivalent. When we say “A if and only if B” we mean that A will be true whenever B is true and B will be true whenever A is true. So in this case we mean that n will be a denominator of a fraction equal to 4/6 whenever n is a whole number multiplier of 4/6 and whenever n is a denominator of a fraction equal to 4/6 then n will be a whole number multiplier of 4/6.

[6] This form of “restatement” is called the contrapositive. The contrapositive of a statement: ‘If A then not B’ is ‘If B then not A’. In this case we take A to be the statement: ‘m and n have a common factor > 1’ and B to be the statement: ‘m/n is reduced’. So the original statement is: ‘If (m and n have a common factor) then (m/n is not reduced.)’ and the contrapositive says: ‘If (m/n is reduced) then (m and n do not have a common factor).’ A statement is always logically equivalent to its contrapositive. Suppose we know that whenever A is true B cannot be true then when B is true A cannot be true. On the other hand if we know that whenever B is true A is false then B must be false whenever A is true.

[7] An Algorithm is a calculation procedure.

[8] The proof given here of this last point, that r cannot be both positive and negative, is an example of a “proof by contradiction.” In such a proof one assumes that what one is trying to prove is false and show that that assumption leads to a conclusion which is known to be false. In this case, the assumption that r was both positive and negative led to the conclusion that there is a whole number which is both > 0 and < 0. This false conclusion is called a contradiction.