Math question: Easiest way to find the Greatest Common Factor?

[the]

What's the easiest way to do that? Formula or something?

Trying to help my son with his math (LOL). Easy ones, like 21, 28, are not a problem, because it's easy to spot the answer (7).

But what about harder ones, like, say 28 and 84, or 46 and 138? Surely there must be a method to figuring these out! (I guess I'm NOT smarter than a fifth grader!).

[HardDrive]

Do your own googling man.....

http://www.math.com/school/subject1/lessons/S1U3L2GL.html

[island911]

one good trick is that if the numbers in the number add up to 3, then it is also divisible by 3.

example: 123 .. . . 1+2+3=6 (=>divisible by 3)

anything divisible by 5 is obvious. Same for 2.

[stomachmonkey]

9, 18, 27, 36, 45....... digits add up to 9 so divisible by 9

[WI wide body]

Originally Posted by island911

one good trick is that if the numbers in the number add up to 3, then it is also divisible by 3.

example: 123 .. . . 1+2+3=6 (=>divisible by 3)

anything divisible by 5 is obvious. Same for 2.

And how does that work for the example he listed: 28 and 84, or 46 and 138?

[baldman]

I'm going through the same thing with my daughter. To me it's easiest to start with the smaller number and work backwards. So 28 and 84 you say "does 28 divide into 84", then if not, work the next highest number you can evenly divide into 28.

In this case, the answer is 28

[baldman]

Originally Posted by WI wide body

And how does that work for the example he listed: 28 and 84, or 46 and 138?

It works to eliminate soime numbers. Since 2+8=10 and 10 is not divisible by 3, then 3 and any multiple of 3 can't be the answer.

[SlowToady]

This is pretty easy...I'll write something up for you when I get back from my Spanish exam.

[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."

If you don't like that method, there is another way (it does the same thing) using a 2x2 matrix. I don't remember if in 5th grade basic Matrix stuff is covered, but if so, or if you want to see the method anyway, reply here or PM/email me and I'll write that out as well. For me, personally, it's easier than the above.

[the]

Thanks, I'll have to print that out and read it carefully. Because I really don't fully understand it at first glance.

Poor kid, he's only in 4th grade, and he's young for his grade (there are kids in his class who are more than a year older than him). I don't remember doing things like this in 4th grade.

[island911]

I was going to say, that the math "Formula or something" is more involved than just having the kid use his head, trial and error style(w/ a few tricks). --anyway, using the math is likely the crux of the lesson. But I see that SlowToady has made that point.

[rammstein]

The answer in my adult life is to call my wife and ask her.

Tell him to start dating smart girls.

[WI wide body]

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."

.

Yeah, lot's of 5th graders will be all over the above...right after they get the iPod out of their ear!

[SlowToady]

The part involving the Number Theory aspect was intended for the OP so he could understand the mathematical reasoning behind what the Greatest Common Divisor really means, and how it's calculated. The examples serve to show how it works, and how he can apply it to his son.

I've found that if, while you're following the examples, you say in English what you're doing, it reinforces the concept.

There is another, possibly easier to understand, method using a Matrix. Your son doesn't have to understand (yet) *why* it works, but he needs to know how to do it.

In 5th grade, I would have gotten wood over "the above"

[island911]

It was a very good write up, good method, ST.
Tho, you may want to open with an example ... a simpler one; similar to what you closed with. I think the most started glazing over with the defn's.

[ZOA NOM]

I vote SlowToady's as the post of the year. That was absolutely beautiful. I wish half the questions I ever asked were answered so cleanly. Well done!

[911Rob]

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."

If you don't like that method, there is another way (it does the same thing) using a 2x2 matrix. I don't remember if in 5th grade basic Matrix stuff is covered, but if so, or if you want to see the method anyway, reply here or PM/email me and I'll write that out as well. For me, personally, it's easier than the above.

This is why after every math lecture in college I would give an evening class for my classmates, to help them decipher the lesson!