Number Theory, Modular Arithmetic / Remainder Arithmetic, Divisibility Rules

Divisibility rules are shortcuts to determine if an integer is exactly divisible by another smaller integer without performing the full division. Questions involve applying these rules for various divisors (e.g., 2, 3, 4, 5, 9, 10, 11) to test numbers or find missing digits.

• Question

  Let a₁, a₂, ..., a₁₀₁ be a permutation of 2, 3, 4, ..., 102. Find all permutations such that a_i is divisible by i for all i.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 3

• Question

  Given two natural numbers `k`  and `m` that differ only in the order of their digits (that is, one is obtained from the other by swapping the order of the digits).

  a. Prove that the sum of the digits of `2k` is equal to the sum of the digits of `2m`.

  b. Prove that if `k` and `m` are even, then the sum of the digits of \(k\over 2\)  is equal to the sum of the digits of \({m \over 2}\).

  c. Prove that the sum of the digits of `5k` is equal to the sum of the digits of `5m`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Division -> Parity (Even/Odd)

• Question

  The number `458` is written on the board. In each single step, you are allowed to either multiply the number written on the board by `2`, or erase its last digit.

  Is it possible to obtain the number `14` using these operations?

  Topics:

  Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  Is it possible for the sum of three natural numbers to be divisible by each of them?

  Topics:

  Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Constructing an Example / Counterexample
  Sources:
  • problems.ru web site

• Question

  Prove that the difference of squares of two consecutive odd numbers is divisible by `8`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Algebra -> Algebraic Techniques -> Short Multiplication Formulas / Algebraic Identities
  Sources:
  • problems.ru web site

• Question

  Prove that the product of three consecutive numbers is divisible by `6`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Division -> Parity (Even/Odd) Number Theory -> Prime Numbers -> Prime Factorization

• Question

  Prove that the product of four consecutive numbers is divisible by `24`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Prime Numbers -> Prime Factorization

• Question

  Prove that for every prime number `p>3 ` the following holds: `p^2-1` is divisible by `6`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Algebra -> Algebraic Techniques -> Short Multiplication Formulas / Algebraic Identities Number Theory -> Division -> Parity (Even/Odd) Proof and Example Number Theory -> Prime Numbers -> Prime Factorization

• Question

  `a,b` are two distinct natural numbers. The sum of the divisors of each is equal to the same natural number `n`. What is the smallest possible value of `n`?

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Prime Numbers -> Prime Factorization
  Sources:
  • Beno Arbel Olympiad, 2013, Grade 7 Question 1

• 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