Number Theory, Greatest Common Divisor (GCD) and Least Common Multiple (LCM), Euclidean Algorithm

The Euclidean Algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers. It's based on the principle that `\text{GCD}(a, b) = \text{GCD}(b, a \pmod{b})`. Questions involve applying the algorithm and understanding its use, including the extended version for linear Diophantine equations.

• Question

  There are chairs with `4` legs and with `3` legs in a room. When people sat on all the chairs, there were `39` legs in the room (no one remained standing). How many chairs of each type are there in the room?

  Topics:

  Algebra -> Word Problems Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) -> Euclidean Algorithm Algebra -> Equations -> Diophantine Equations

• Question

  A. You have a large jug of 12 liters of olive oil and two empty smaller vessels, one of 5 liters and one of 8 liters. Can you divide the oil you have into two equal parts, if you only have these vessels and no additional measuring tools?

  B. The same question, but instead of the 5-liter vessel, you have a 4-liter vessel.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Constructing an Example / Counterexample Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) -> Euclidean Algorithm Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  In the magical land, there are only two types of coins: `16` LC (Magical Pounds) and `27` LC. Is it possible to buy a notebook that costs one Magical Pound and receive exact change?

  Topics:

  Proof and Example -> Constructing an Example / Counterexample Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) -> Euclidean Algorithm Number Theory -> Division Algebra -> Equations -> Diophantine Equations

• SIMPLE DIVISION

  Sometimes a very simple question in elementary arithmetic will cause a good deal of perplexity. For example, I want to divide the four numbers, `701, 1,059, 1,417`, and `2,312`, by the largest number possible that will leave the same remainder in every case. How am I to set to work Of course, by a laborious system of trial one can in time discover the answer, but there is quite a simple method of doing it if you can only find it.
  Topics:

  Arithmetic Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) -> Euclidean Algorithm Number Theory -> Division
  Sources:
  • Amusements in Mathematics, Henry Ernest Dudeney Question 127