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.

• 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

• Question

  Find all integer solutions `(k>1) y^k=x^2+x`

  Topics:

  Number Theory -> Prime Numbers -> Prime Factorization Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Algebra -> Equations -> Diophantine Equations
  Sources:
  • Tournament of Towns, 1980-1981, Spring, Main Version, Grades 9-10 Question 1 Points 3

• Movie Buffs

  Avi, Beni, and Gili love movies. Avi goes to the movies every `3` days, Beni – every `5` days, and Gili goes every `7` days. Today, they all went to the movies together. In how many days can this happen again?

  Topics:

  Arithmetic Algebra -> Word Problems Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM)
  Sources:
  • problems.ru web site

• Question

  The "Sweet Math" candies are sold in boxes of `12` units, and the "Geometry with Nuts" candies – in boxes of `15` units.

  What is the minimum number of boxes that must be purchased so that there are equal quantities of candies of both types?

  Topics:

  Arithmetic Algebra -> Word Problems Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Minimum and Maximum Problems / Optimization Problems
  Sources:
  • problems.ru web site

• Question

  How many numbers between `1` and `100` are not divisible by `2` or `5`?

  Topics:

  Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 2, 4, and 8 Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 5 and 25 Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Set Theory Number Theory -> Division

• Question

  Consider the integers from `1` to `700`.

  a. How many of these numbers are even?

  b. How many of these numbers are divisible by `7`?

  c. How many of these numbers are not divisible by `2` nor by `7`?

  Answer question c.

  Topics:

  Number Theory -> Prime Numbers Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Matchings Number Theory -> Division -> Parity (Even/Odd) Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Set Theory

• Question

  Given the sequence `1 , 1/2 ,1/3 ,1/4 ,1/5,...`, does there exist an arithmetic sequence composed of terms from the aforementioned sequence?

  1. Of length 5

  2. Of any length

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Proof and Example -> Constructing an Example / Counterexample Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence Arithmetic -> Fractions Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM)
  Sources:
  • Tournament of Towns, 1981-1982, Spring