Number Theory, Modular Arithmetic / Remainder Arithmetic

Modular Arithmetic (or Remainder Arithmetic) is a system where numbers 'wrap around' after reaching a certain value, the modulus. It deals with congruences and remainders. Questions involve solving equations in modular systems, finding powers modulo `n`, and applications in patterns or cryptography.

• Question

  Prove that there exist two powers of `2` such that their difference is divisible by `2017`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Pigeonhole Principle
  Sources:
  • problems.ru web site

• Question

  Given a positive integer N, consider the following process: Let `S(N)` denote the sum of the digits of N. Take the sum of the digits of `S(N)`. Repeat this operation until a single-digit number is obtained. We call the number of times we performed the above process until we obtained a single-digit number the "depth" of N. For example, the depth of 49 is `S(49)=13 -> S(13)=4`, the operation was performed twice (and the depth of 45 is 1).

  a) Prove that for every number N there is indeed a finite depth, that is, a single-digit number is always obtained at some stage of the process.

  b) Let `x(n)` denote the minimum number (with the smallest value) with depth N. Find the remainder of `x(5776)` when divided by 6. Justify your answer!

  c) Find the remainder of the number `x(5776) - x(5708)` when divided by 2016. Justify your answer!

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Induction (Mathematical Induction) Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence
  Sources:
  • Gillis Mathematical Olympiad, 2015-2016 Question 3

• Question

  Prove that among five integers, it is possible to choose two whose difference is divisible by `4`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Pigeonhole Principle Number Theory -> Division -> Parity (Even/Odd) Arithmetic -> Division with Remainder

• Question

  The numbers from `1` to `2n` are written in a row in some order. Add to each number the index of the position it stands on. Prove that among the `2n` sums we obtained, there are two whose difference is divisible by `2n`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Pigeonhole Principle Proof and Example -> Proof by Contradiction

• 777

  What is the last digit of the number `777^777`?

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic

• Question

  What is the last digit of the number `43^43-17^17`?

  Show hint

  Log in here to receive the hint
  Topics:

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

• Question

  Does there exist a perfect square that ends with the digits `...2017`?

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  Given natural numbers m, n such that `m/n <= sqrt 23`, prove that `m/n+3/{mn} <= sqrt 23`

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Algebra -> Inequalities Proof and Example -> Proof by Contradiction Algebra -> Algebraic Techniques -> Roots / Radicals
  Sources:
  • Mink Exercises and Additional Competition Materials, 2018-2019, Exercise 3 Question 4

• Question

  Is there a solution in natural numbers to the equation `x^2 + 12 = y^3` such that

  a. x is even (easier)

  b. x is odd

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Prime Numbers Number Theory -> Modular Arithmetic / Remainder Arithmetic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Arithmetic -> Division with Remainder Algebra -> Equations -> Diophantine Equations
  Sources:
  • Mink Exercises and Additional Competition Materials, 2018-2019, Exercise 3 Question 6

• Sums of Factorials

  For every positive integer n, let us denote `n! = 1*2*3*...*n`

  Find all integers n such that the sum `1! + 2! + 3! + ... + n!` is the square of an integer.

  (Solution format: a,b,c,... i.e., the three smallest numbers separated by commas with no spaces, and three dots after if there are more solutions)

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Algebra -> Sequences
  Sources:
  • Grossman Math Olympiad, 2022, Seniors Question 1