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

The GCD of two integers is the largest integer that divides both of them. The LCM is the smallest positive integer that is a multiple of both. Questions involve finding GCD and LCM (e.g., via prime factorization or Euclidean algorithm) and solving problems using their properties.

• The Number

  Given a positive integer less than 2000.
  If it is not divisible by 43, then it is divisible by 41,
  If it is not divisible by 53, then it is divisible by 43,
  If it is not divisible by 41, then it is divisible by 53.
  Find the number.

  Topics:

  Number Theory -> Prime Numbers Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Logic -> Reasoning / Logic Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Number Theory -> Division
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage B, Grades 3-4 Question 6
  • Young Mathematician Olympiad, 2019-2020, Stage B, Grades 5-6 Question 4

• Pairwise Relatively Prime Composite Numbers

  Yossi writes two-digit composite numbers on the board. He wants all the numbers written on the board to be pairwise relatively prime.
  What is the maximum number of integers Yossi can write on the board?
  Note: Integers are called relatively prime if they have no common factors other than 1.

  Topics:

  Logic -> Reasoning / Logic Number Theory -> Prime Numbers -> Prime Factorization Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM)
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 5-6 Question 4

• The Number with the Most Divisors

  Among the positive integers less than 1000, which number has the most divisors?

  Topics:

  Arithmetic Number Theory -> Prime Numbers -> Prime Factorization Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Number Theory -> Division
  Sources:
  • Bar-Ilan's weekly mathriddle competition, 2024 Question 3

• THE MARKET WOMEN

  A number of market women sold their various products at a certain price per pound (different in every case), and each received the same amount—`2`s. `2`½d. What is the greatest number of women there could have been? The price per pound in every case must be such as could be paid in current money.
  Topics:

  Arithmetic Algebra -> Word Problems Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Minimum and Maximum Problems / Optimization Problems
  Sources:
  • Amusements in Mathematics, Henry Ernest Dudeney Question 18