Originally Posted by SlowToady
Ok, strap in and let's sit through some Elementary Number Theory for a second. Your son, obviously, doesn't need to know this part (yet) but it will help you understand, and hopefully thereby enable you to teach/help him more effectively.
First we must establish divisibility, which will be represented by the " | " sign. Let a be non-zero and b be arbitrary. Then, if there exists a c such that b = a*c, we say that a divides b. Alternatively, we say that a is a divisor of b. (The statements are equal.) We write a | b. The negation is a !| b, where " !| " means "does not divide." a, b, c are integers.
Following from this definition we have:
1. For every a != 0, a | 0 and a | a. For every b, +-1 | b.
2. If a | b and b | c, then a | c.
3. If a | b and a | c, then a | (bx + cy) for each x, y.
4. If a | b and b != 0, then abs(a) <= abs(b).
Ok, now that we have that established, we move on to the Euclidean Algorithm and the Greatest Common Divisor.
Theorem: Given any two integers a and b, not both 0, there is a unique integer, d such that
i) d > 0
ii) d | a and d | b
iii) If d(sub1) is any integer such that d(sub1 | a and d(sub1) | b, then d(sub1) | d.
What the third property says is that every common divisor of a and b divides d. It follows logically from Assertion 4 that d is the numerically largest of the divisors of a and b. We therefore state that gcd(a,b) = d. I've omitted the proof of this, thinking that instead examples will serve better than mathematical proof.
Say, for example, we wish to find the Greatest Common Divisor of 4147 and 10672, or, gcd(4147, 10672). We would go about it as follows:
10672 = 4147 * 2 + 2378
4147 = 2378 * 1 + 1769
2378 = 1769 * 1 + 609
1769 = 609 * 2 + 551
609 = 551 * 1 + 58
58 = 29 * 2
Thus, gcd(4147,10672) = 29.
Basically, what you are doing, is taking the smaller number, 4147, multiplying it by the largest possible number whose product is < the largest number (10672) (call it t), and then adding the difference of the largest number and the product of the smaller number multiplied by t.
For 24 and 84:
84 = 24 * 3 + 12
24 = 12 * 2
Therefore, gcd(24,84) = 12.
For 28 and 84:
84 = 28 * 3
28 = 28 * 1
Therefore, gcd(28,84) = 28
If a, b have no common divisor, that is, gcd(a,b) = 1, then a and b are said to be "Relatively Prime."
.
|