This section tests your knowledge on the properties of natural numbers, number theory facts, and the Euclidean Algorithm.
Here are some concepts that you may see on the test.
Properties of Divisibility
For real numbers, a, b, and c, the following are true:
- If a nonzero integer divides two other integers, then it divides their sum.
3 divides 9 evenly, and 3 divides 6 evenly. Applying this property means that 3 divides 9 + 6. In fact, 3 does divide 15 since 15 divided by 3 is 5.
- If a divides b, and b divides c, then a divides c, where a, b, and c are nonzero integers.
2 divides 4, and 4 divides -16. Applying this property means that 2 divides -16, which it does since -16 divided by 2 is -8, an integer.
- If a divides b then a divides a scalar multiple of b.
5 divides 20. Applying this property then means that 5 divides any scalar multiple of 20, which it does. For example, 5 divides -40 which is -2(20), since -40 divided by 5 is -8.
The Euclidean Algorithm is a method for finding the greatest common divisor for two integers.
For integers a and b, where a ≥ b, the greatest common divisor (gcd) is given by the following:
- If b = 0, then gcd(a, b) = a.
- If b > 0, then gcd(a, b) = gcd(b, r) where r is the remainder of a divided by b.
For example, let’s find the greatest common divisor of 8,602 and 4,278. Here, a = 8602 and b = 4278. Since 4278 > 0, we need to use the second part of the algorithm and find the remainder of 8602 divided by 4278. 4278 goes into 8602 two times with a remainder of 46.
Therefore, gcd(8602, 4278) = gcd(4278, 46). Now we can apply the algorithm again with these new smaller numbers. 46 goes into 4278 ninety-three times with a remainder of 0.
Therefore, gcd(4278, 46) = gcd(46, 0). Using the first part of the algorithm, we know that gcd(46, 0) = 46.
Putting this all together, gcd(8602, 4278) = gcd(4278, 46) = gcd(46, 0) = 46. So, the greatest common divisor of 8,602 and 4,278 is 46.