Did you know the formula your TI calculator uses to find the most simple form of any fraction is based on an algorithm discovered around the year 300 BC. Much to my surprise it was a simple process known as Euclid’s Algorithm. I came across the algorithm when I picked up a copy of Algorithms in C++ by Robert Sedgewick. This led me to search through my roommate’s textbook for Discrete Mathematics for a while since I am a Biology major.
The algorithm used to compute the most simple form of any fraction is a 2 step process.
- The first step is finding the greatest common divisor (GCD).
- Then both the numerator and denominator are divided by the GCD to produce the fraction in its simplest form.
Too easy right. Actually, finding the GCD is a repetitious task that your calculator can do much quicker than any human, but that does not make it impossible for us to solve.
1. Finding GCD
Lets say we want to simplify the fraction 414/662. The greatest common denominator of the integers can be found using principles of Euclid’s Algorithm which relies on the remainder left over after simple subtraction:
- u’= (u-v)
This equation is true whenever U represents the larger number, and V represents the smaller number. Do not let the equation above scare you because I have simplified the process below . In order to simplify 414/662 we start with the equation:
662= 414 x (a number) + (the remainder)
- 662= 414 x (1) + 241 //the largest number is always to the left side of the equation.
662414= 414241 x (1) + 241166 //441 becomes the new “largest number” while the remainder(241) replaces 441 from the first in the equation.
- 241 = 166 x (1) + 82 //we keep repeating this process
- 166 = 82 x (1) + 84
- 82 = 84 x (1) – 2 //notice we are subtracting 2 now since our V (84) is larger than the U (82) now. We almost have our final answer. Now we can find the simplest multiple
- 84= 2 x (41) + 0 //our remainder is zero and the V became large than U in the last step. So our GCD will be 2
In the first line 662 and 441 are the given numbers. In this case 441 can only fit inside of 661 one time and the remainder is (662-(441 x 1)) or simply 241. A computer program can use 1 every time or a quicker method using the (%)operand function common to high level programming. We are just going to multiply by 1 every time to keep things simple.
2. Finding the simplest fraction
If you read through the comments you should be able to see how we discovered the GCD of 662 and 414 was 2. Now we can divide each integer by 2 to get our most simple fraction of:
Now you can tell TI you want a $5 rebate on your next purchase of their calculator since you can already the simplest fraction on your own. Most people will be satisfied just knowing they have demystified the function of the MATH> FRAC algorithm they have been using for half of their life.