Theory
In this lesson, we will work with the concepts of the greatest common divisor (GCD) and least common multiple (LCM), as well as related problem-solving techniques. The GCD of two numbers is the largest number that divides both of them without a remainder. The LCM of two numbers is the smallest number that is a multiple of both.
Problems
- Prove that if a > b, then GCD(a, b) = GCD(b, a − b).
- Find GCD(25, 1717).
- Let u be the LCM of a and b, and let m be any other common multiple of a and b. Prove that u divides m. (Written solution required.)
- Daniel takes a sheet of paper of size m × n, cuts off a square along the shorter side, and throws it on the floor. From the remaining rectangle, he again cuts off a square and continues this process as long as possible. The cuts follow the grid lines of the paper. What will Daniel be holding in his hands when he finishes this process and starts cleaning up?
- A natural number a is given. What is the largest possible value of GCD(n² + a, (n + 1)² + a)?
- A counterfeiter named Bill prints banknotes worth 17 pounds, while another counterfeiter named John prints banknotes worth 23 pounds. John owes Bill 10 pounds. How can they settle the debt? Find several ways.
- Is it true that the polynomial n² + n + 41 always produces prime numbers?
- From 1 September, four pupils start going to the cinema. The first goes every fourth day, the second every fifth day, the third every sixth day, and the fourth every ninth day. When will all four pupils meet in the cinema for the second time?
- Solve the equation |x − 1717| = |1919 − x|.
- There are two jugs with capacities of 310 ml and 210 ml. Is it possible, using these jugs, to pour from a full barrel into an empty barrel exactly 3 litres of water? Exactly 10 ml? Exactly 45 ml?
- Prove that the equation x / y + y / z + z / x = 1 has no solution in natural numbers.
- Prove that for odd numbers a, b, c, the following is true: GCD((a + b) / 2, (b + c) / 2, (a + c) / 2) = GCD(a, b, c).