Jumping Jiving GCD
Summary
Resources
Jumping Jiving GCD
1. Motivation: Simplifying Fractions
We know that there are many different ways of writing the same number as a fraction, for example:
23= 5075
Which means that carving out 2 thirds of a pie is the same as carving out the pie in 75 little pieces and picking 50 of them ... hard work!
Based on this, we say that there is a “best” or easiest way to write a fraction, when it is impossible to cancel out anything between the numerator and the denominator. The fraction is said to be reduced, or in simplest form, in this case.
To bring a fraction to its simplest form one may do successive simplifications:
5075=50÷575÷5=10÷515÷5=23
Or one can do it in one strike like this:
5075=50÷2550÷25=23
In both cases one simplifies by numbers that divide both the numerator and denominator.
The Greatest Common Divisor (GCD) a.k.a. Highest Common Factor (HCF)
Question: What is special about the number 25 above? (think in relation to 50 and 75).
Answer: 25 is the largest natural number which divides both 50 and 75.
The greatest common divisor of two numbers is the largest number that divides them both.
The greatest common divisor of a and b is usually denoted by gcd(a,b).
For example, gcd50, 75=25.
Co-prime numbers
Question:
Suppose that ab is the simplest form of a fraction.
What is gcd(a,b) ?
Answer:
gcda,b=1.
If gcda,b=1 then a and b are said to be co-prime. In other words, they have no other common divisors except 1.
Question:
Can you find a number which is co-prime with all numbers except multiples of itself?
Can you name all such numbers?
Answer:
The prime numbers.
Simplifying fractions, finding gcda,b.
Take any two numbers a and b. Next we’ll look at different methods for finding gcda,b, that is, of bringing a fraction ab to its simplest form.
Method I: Successive simplification. Looking back at our first example
5075=50÷575÷5=10÷515÷5=23
How can gcd50, 75 be extracted from this calculation?
Answer:
gcd50,75=25=5×5, the product of the numbers by which we simplified.
That’s because 50÷5÷5=50÷5×5= 50÷25=2 and
75÷5÷5 = 75÷5×5=70÷25=3 and 2 and 3 clearly have no other common divisors.
Practice exercise: Use successive simplification to find gcd60,84.
Answer: (in its goriest form):
6084=60÷284÷2=30÷242÷2=15÷321÷3=57
We simplified by 2, 2, and 3 so gcd60,84=2×2×3=12.
Method II: Prime factorization.
This worked well and good, but what if we can’t easily find any common divisors?
Example: Find gcd345, 184.
Solution: We can’t find a number that divides both 345 and 184 right away, but we can find some divisors for each of them at a time. So let’s just prime factorize the numbers. The hidden common factors will surely reveal themselves:
345=5×3×23 and 184=23×23.
And gcd345,184=23.
Now suppose we have prime factorized two numbers. Let’s derive some basic rules for finding their gcd.
Example: Find gcda,b for a=23×32×7 ×135, and b=2×33×5×74.
Solution: gcda,b=2×32×7=126.
Rule: gcda,b = the product of all common primes, each chosen with its smallest index between the prime factorizations of a and b .
Explanation: The prime 2 comes up with index 3 in a and index 1 in b, so in gcda,b it will come up with index 1= min( 3, 1). Recall that 2=21.
Indeed, 2 divides both a and b but 22 wouldn’t divide b so it can’t be a factor of gcda,b.
We can generalize to as many numbers we want.
Practice exercise: Find gcda,b,c when for a=2×3×4×5, and b=6×7×8×9 and for c=10×11×12 ×13.
Solution: Prime factorisation
Method III: Euclid’s algorithm.
What if even prime factorization fails with numbers a and b: what if a and b are too large to factorize, or what if they are written as sums with terms depending of an unknown number n?
Strategy: reduce our numbers to manageable proportions, using these simple
Simplifying principles:
1) If a fraction ab can be simplified by a number, then ab - 1, ab - 2, ab -3, ... as well as ab + 1, ab + 2, ab + 3 ... can be simplified by the same number.
2) If a fraction ab can be simplified by a number, then ba can be simplified by the same number.
Proof of the principles:
Point 2) Is pretty clear, as in both cases a and b are divisible by that same number.
For 1), ab-1=a-bb. Let’s assume ab can be simplified by a number d. That is, d| a and d|b. But then d|(a-b). So both numerator and denominator of a-bb are divisible by d.
We can adapt this argument for all the other fractions.
Application: Euclid’s algorithm for finding gcda,b, the magic simplifying factor of the fraction ab :
Let’s suppose that the fraction is what you call improper, so the denominator (bottom) is smaller than the numerator (top). Then
1) We divide the numerator by the denominator to get a mixed number, then discard the integer parts.
2) We turn the resulting fraction upside down, to get its reciprocal.
3) The resulting fraction will have the same simplifying factors as the original one, but smaller numbers. We apply steps 1) and 2) again as many times as necessary until the fraction becomes manageable.
Memo Note: Euclid’s algorithm closely resembles Greco-Roman wrestling between the numerator and the denominator:
1) First the denominator knocks a few units off the numerator.
2) Then it topples the numerator down and gets on top.
3) They start all over again.
This analogy seems quite appropriate because Euclid founded a famous Greek school of mathematics.
Example: Find gcda,b in each of the following two cases:
i) a=23456, and b=34567.
ii) a=6n+10 and b=8n+11 where n is some unknown natural number.
Solutions:
i) Since 34567>23456, let’s start with 3456723456:
3456723456=1+1111123456 has the same simplifying factors as 1111123456, and so also as 2345611111.
2345611111=2+123411111 has the same simplifying factors as 123411111, and so also as 111111234.
111111234=9+51234 has the same simplifying factors as 51234.
But 5 clearly doesn’t divide 1234 so 51234 is in reduced form, 5 and 1234 are co-prime.
This means that 3456723456 was in reduced form in the first place, so 34567 and 23456 are co-prime. In terms of gsd-s we can write:
gcd(34567,23456)=gcd(23456,11111)=gcd(11111,1234)=gcd(1234,5)=1.
ii) Solution I
a=6n+10 and b=8n+11 where n is some unknown natural number.
We write 8n+11=6n+10+2n+1 so
8n+116n+10=1+2n+16n+10
Then 6n+10=3(2n+1)+7 so
6n+102n+1=3+72n+1
We could even go on one more time like this:
2n+1=7+2n-6 so
2n+17=1+2n-67
Now we have two cases:
- For some values of n like 1, 2, 4, 5, 6, 7, 8, 9, 11,..., the number 2n+6 is not divisible by 7, so 2n-6 and 7 are co-prime. This makes a and b co-prime also.
- For other values of n like 3, 10, 17, 24, ... the number 2n-6 is divisible by 7, so
gcd(2n-6,7)= gcd(a, b)=7. How do we recognize these values of n?
Well, because 2n-6=2(n-3) and 7 is a prime, so if 7| 2(n-3) then 7|(n-3), so n-3=7k where k can take the values 1,2,3,...
Solution II
We could have saved ourselves a lot of trouble if we decided to eliminate n right away:
a=6n+10 and b=8n+11 .
There are 6 n-s in a and 8 n-s in b). (6 and 8 are called coefficients of n).
We notice that 6×4=8×3 and so
4a-3b=4(6n+10)-3(8n+11)=24n+40-24n-33=7 no more n-s!
Let’s denote gcd(a, b) by d. Now if d|a and d|b then d|(4a-3b), (prove this!)
so d|7 so d can only be 7 or 1. It remains to check that either of these values can occur, like in the first solution we used.
A surprising property of the GCD.
A flea problem
Two fleas, one red and one blue, are jumping happily along a straight line. The red flea’s jump length is a=17 cm and the blue flea’s jump length is b=13 cm. They both start up from the same point 0 and jump at various speeds, sometimes even stopping and waiting for each other.
a) Find all the spots on the line where the two fleas can land in their first 5 steps, if they jump Eastward.
b) What is the closest from each other they can ever be on their line, without having to be both on the same spot?
c) Repeat the problem in the case when a=34 cm and b=26 cm.
d) Repeat the problem in the case when a=51 cm and b=39 cm.
Solutions:
a) Since the red flea can land every 17 cm, the spots it lands on are
1×17=17, 2×17=34, 3×17=51, 4×17=68, 5×17=85.
Since the blue flea can land every 13 cm, the spots it lands on are
1×13=13, 2×13=26, 3×13=39, 4×13=52, 5×13=65.
b) From the table above we see that 4b-3a=4×13-3×17=1,
so the fleas can get within 1 cm of each other. They cannot get any closer without bumping into each other, because the places they land in are natural numbers and their smallest positive difference can only be 1.
c) In the case when a=34=17×2 cm and b=26=13×2 cm, all the measures of the landing spots above get doubled. Now 4b-3a=4×26-3×34=2, so the fleas can get within 2 cm of each other. They can never get any closer than that without bumping into each other. Indeed, in this case the landing spots of the two fleas are all even, so the distances between them will be even.
d) In the case when a=51=17×3 cm and b=39=13×3 cm, all the distances will be multiples of 3. Now 4b-3a=4×39-3×51=3, so the fleas can get within 3 cm of each other, but they can never get any closer without bumping into each other.
The flea problem, mathematical formulation:
Let’s discuss the case when a=17 cm and b=13 cm.
Then the red fleas landing spots are all the multiples of 17 cm. The blue fleas landing spots are all the multiples of 13 cm.
Let u and v be two natural numbers. Suppose that the red flea has made u jumps and the blue flea has made v jumps. Let’s write an algebraic formula for the distance between the fleas, then rewrite the conclusion of our problem b) mathematically.
The red flea has made u jumps, it is at u×17 cm from the origin.
The blue flea has made v jumps, it is at v×13 cm from the origin.
The distance could be either u×17- v×13 or -u×17+ v×13 depending on who is closest to the origin. Our problem b) proves:
1 is the smallest positive distance between any two multiples of 17 and 13.
2 is the smallest positive distance between any two multiples of 34 and 26.
1 is the smallest positive number of the form u×17- v×13 or -u×17+ v×13,
where u and v are random natural numbers.
It’s annoying to have two formulas so let’s choose two new symbols x and y and set
x=u, y=-v if the distance is u×17- v×13
x=-u, y=-v if the distance is -u×17+ v×13
In either case the distance now reads 17x+13y, but x and y are now random integers.
(The multiplication sign between the numbers and the symbols are implied).
1 is the smallest positive number of the form x17+y13 where x and y are random integers.
Question: i) What is gcd17,13?
ii) If rather than 17 and 13 we work with two unknown natural numbers a and b, can you guess how close the fleas can get from each other without being on the same spot?
Answer: i) 1; ii) d = gcda,b.
Property of the GCD:
gcda,b is the smallest positive number of the form xa+yb where x and y are random integers!
To prove this, let’s look at
A generalized flea problem
Mummy flea’s jump is a cm long, Daddy’s jump is b cm long, and Baby’s jump is d cm long. Mummy and Daddy start up from the same point and jump on a straight line at various speeds. At the exact moment when Mummy and Daddy are the closest they can ever be on their line, (but not on the same spot), Baby flea, who’s piggybacking on Daddy’s back, can jump onto Mummy’s back, and hence on happily away.
If Mummy or Daddy take one more jump each and then wait for Baby, prove that Baby can reach any of them if it wants to.
a) Question: How can we formulate the question mathematically in terms of a, b and d?
Answer: Prove that d divides both a and b. Let’s focus on d divides . So we want Mummy and Baby’s jumps to look like this:
b) Strategy: Proof by Contradiction.
We know: d is the closest that Daddy can get to Mummy.
To prove: d divides a.
Idea of proof: Assume d doesn’t divide a.
Then Baby could only reach within r cm of Mummy, where r<d:
If we prove that Daddy can also get within r cm of Mummy, where r<d then we contradict the info that d is the closest that Daddy can get to Mummy! So our assumption was wrong: d actually divides a.
c) Main step:
Assuming a=kd+r and r<d, to prove that Mummy and Daddy can get within r cm of each other:
i) Let’s say that it took 1 hour for Mummy and Daddy to get within distance d of each other.
Let’s assume they keep jumping at same speeds. How far away from each other will they be
after k hours?
ii) Can Mummy then get within distance r of Daddy?
Answers: i) kd; ii) Yes if Mummy just takes another step in the right direction: a-kd=r
d) Mathematical formulation of the proof:
We know: d is the smallest positive number of the form xa+yb where x and y are random integers.
To prove: d divides a.
Proof: Assume d divides into a with remainder r. Then a=kd+r and r<d.
But then r=a-kd=a-kxa+yb=a-kxa-kyb=1-kxa-kyb.
......
......
Left out for lcm and co-prime purposes:
c) Are there any spots on the line, except for 0, that both fleas can reach? Can you describe all these spots?
c) The red flea lands on multiples of 17, which we can write as 17k. The blue flea lands on multiples of 13, which we can write as 13h. The spots where they both land have to be multiples of both 13 and 17. The smallest would be 13×17 and then all multiples of that.
7