MOPSS, 5th July 2025
Determine if the product of some four consecutive integers can be equal to the product of a few consecutive primes.
Click here for the spoiler!
The product of any four consecutive positive integers is a multiple of \(4\).
Suppose we are given a positive integer, and any of its digits is equal to \(0\) or \(6\). Show that the given integer is not a perfect square.
Click here for the spoiler!
- Show that the last two digits of a square cannot be \(06\) or \(66\).
- Conclude that the last two digits are equal to \(00\).
- Use this argument repeatedly.
(Bay Area MO 1999 P1) Prove that among any \(12\) consecutive positive integers, there is at least one which is smaller than the sum of its proper divisors. (The proper divisors of a positive integer \(n\) are all positive integers other than \(1\) and \(n\) which divide \(n\). For example, the proper divisors of \(14\) are \(2\) and \(7\).)
Click here for the spoiler!
\(3, 4, \dots\)!
Note that
\[\begin{align*} 2^2 & = 4, \\ 2^6 & = 64, \\ 2^5 & = 32, \\ 2^{25} & = 33554432 \end{align*}\]holds. This shows that there are distinct powers of \(2\) whose last digits are equal, and that there are distinct powers of \(2\) whose blocks of last two digits are the same.
The above leads to the following problems.
Are there two powers of \(2\) such that the blocks of their last three digits are the same?
Click here for the spoiler!
Apply the pigeonhole principle to all powers of \(2\), considering their last three digits.
Are there two powers of \(2\) such that the blocks of their last \(2025\) digits are the same?
Observe that both of the integers \(3457, 7453\) leave a remainder of \(1\) when divided by \(9\). Note that
- \(3000\) differs from \(3\) by a multiple of \(9\),
- \(400\) differs from \(4\) by a multiple of \(9\),
- \(50\) differs from \(5\) by a multiple of \(9\),
- \(7\) differs from \(7\) by a multiple of \(9\),
and hence \(3457\) differs from the sum \(3 + 4 + 5 + 7\) by a multiple of \(9\).
Suppose we are given a positive integer. We interchange its digits to form another integer. Show that these two integers leave the same remainder when divided by \(9\).
Click here for the spoiler!
Does the above remark help?
Note that \(3, 5, 7\) are three consecutive odd integers and all of them are primes. How many such examples of three consecutive odd integers are there such that all of them are primes?
Examples of three consecutive odd integers include
- \(11, 13, 15\),
- \(25, 27, 29\),
- \(37, 39, 41\).
Prove that if a prime number is divided by \(30\), the remainder is a prime or \(1\).
(Infinitude of primes, by Saidak) Let \(a_1, a_2, a_3, a_4, a_5, \dots\) be a sequence of integers such that
\[\begin{align*} a_1 & = 2, \\ a_2 & = a_1 (a_1 + 1),\\ a_3 & = a_2( a_2 + 1),\\ a_4 & = a_3 (a_3 + 1), \\ a_5 & = a_4 (a_4 + 1), \\ a_6 & = a_5 (a_5 + 1) \end{align*}\]etc. holds, that is, for any positive integer \(n\),
\[a_{n + 1} = a_n (a_n + 1)\]holds. Show that \(a_n\) has at least \(n\) distinct prime factors for any positive integer \(n\).
Click here for the spoiler!
Check it for first few values to \(n\). Expect that the pattern will continue! Try to figure out what more to do to see/get convinced/prove/establish that the pattern does continue.
This is important since the statement that
every positive integer \(n\) is smaller than \(1000\)
is true for first few values of \(n\)! However, the pattern does not continue in this case. The upshot is that observing a pattern does not guarantee its validity all throughout.
Click here for the spoiler!
- Show that \(a_n \geq 2\) for any integer \(n \geq 1\).
- Note that the integers \(a_n, a_n + 1\) have no common prime factor.
- Conclude using induction.
This shows that the list of primes does not stop anywhere, that is, there are infinitely many primes.
Show that for any odd prime number \(p\), the numerator of the rational number
\[1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{p - 1}\]is divisible by \(p\).
Click here for the spoiler!
Let \(S\) denote the above sum. Consider \(2S\) and arrange the summands suitably.
Among any four consecutive positive integers, one of them is coprime to (that is, has no common factor with) the remaining three.
Click here for the spoiler!
Show that among any four consecutive positive integers, at least one of the odd integers is not divisible by \(3\). Consider the case when this odd integer is equal to \(1\), and the case when it it greater than one. In the second case, find a suitable prime divisor of this odd integer.
Click here for the spoiler!
Note that among any four consecutive positive integers, at least one of the odd integers is not divisible by \(3\), and hence, either it is equal to \(1\), in which case it is coprime to the remaining ones, or it is greater than one, and its smallest prime factor is at least \(5\), and hence, it is coprime to the remaining ones.
(Tournament of Towns, Spring 2019, Junior, O Level, P4 by Boris Frenkin) The product of two positive integers \(m\) and \(n\) is divisible by their sum. Prove that \(m + n \leq n^2\).
Click here for the spoiler!
Note that if \(m + n\) divides \(mn\), then \(m + n\) divides \(n(m + n) - mn\).
Show that a perfect square leaves \(0\) or \(1\) as the remainder upon division by \(4\).
Click here for the spoiler!
Consider the squares of \(2n\) and \(2n + 1\).
If an integer leaves a remainder of \(3\) upon division by \(4\), then it cannot be expressed as a sum of two squares.
Click here for the spoiler!
Use the above Exercise.
Is \(2025^{2025}\) divisible by \(23\)? If not, what would be the remainder when it is divided by \(23\)?
Click here for the spoiler!
Check that \(2025 \equiv 1 \pmod{23}\).
Determine the remainder to be obtained when \(133^{133}\) is divided by \(13\).
No integer that leaves a remainder of \(7\) upon division by \(8\) can be expressed as a sum of three squares.
Click here for the spoiler!
Try to read the squares modulo \(8\).
(Tournament of Towns, Fall 2019, Junior, O Level, P4, by Boris Frenkin) There are given \(1000\) integers \(a_1, \dots, a_{1000}\). Their squares \(a_1^2, \dots, a_{1000}^2\) are written along the circumference of a circle. It so happened that the sum of any \(41\) consecutive numbers on this circle is a multiple of \(41^2\). Is it necessarily true that every integer \(a_1, \dots, a_{1000}\) is a multiple of \(41\)?
Replace \(1000\) by \(10\) and \(41\) by \(7\), and work on the problem.
(India RMO 2017a P2, AoPS) Show that the sum of the cubes of any seven consecutive integers cannot be expressed as the sum of the fourth powers of two consecutive integers.
Click here for the spoiler!
Read it modulo \(\hbox to 2em{\thinspace\hrulefill\thinspace}\)!
(China TST 1995 Day 1 P1) Find the smallest prime number \(p\) that cannot be represented in the form \(|3^{a} - 2^{b}|\), where \(a\) and \(b\) are non-negative integers.
Click here for the spoiler!
- Any prime smaller than \(41\) can be expressed as the absolute value of the difference of a nonnegative power of \(3\) and a nonnegative power of \(2\).
- If \(41 = 2^b - 3^a\), then \(b \geq 3\) and hence \(3^a \equiv -1 \bmod 8\), which is impossible.
- Assume that \(41 = 3^a - 2^b\). Considering congruence modulo \(3\), show that \(b\) is an even positive integer. Reduce modulo \(4\) to show that \(a\) is even.
- Write \(a = 2x, b = 2y\), and factorize \(41\).
- Conclude by obtaining a contradiction.
(India RMO 1998 P2, AoPS) Let \(n\) be a positive integer and \(p_1, p_2, \dots, p_n\) be \(n\) prime numbers all larger than \(5\) such that \(6\) divides \(p_1^2 + p_2^2 + \dots + p_n^2\). Prove that \(6\) divides \(n\).
Click here for the spoiler!
Observe that any prime larger than \(5\) is congruent to \(\pm 1\) modulo \(6\).
(India RMO 2023a P2, AoPS) Given a prime number \(p\) such that \(2p\) is equal to the sum of the squares of some four consecutive positive integers. Prove that \(p-7\) is divisible by \(36\).
Click here for the spoiler!
Show that the sum of four consecutive squares is congruent to \(6\) modulo \(8\), and conclude that \(p \equiv 3 \bmod 4\). Considering congruence conditions modulo \(3\), prove that the smallest of the four consecutive numbers is a multiple of \(3\). Deduce that the sum of the four consecutive squares is \(5\) modulo \(9\).
(India RMO 2023b P1, AoPS) Let \(\mathbb{N}\) be the set of all positive integers and
\[S=\left\{(a, b, c, d) \in \mathbb{N}^4: a^2+b^2+c^2=d^2\right\}.\]Find the largest positive integer \(m\) such that \(m\) divides \(abcd\) for all \((a, b, c, d) \in S\).
Click here for the spoiler!
- Show that \((1, 2, 2, 3)\) lies in \(S\), and deduce that \(m\) divides \(12\).
- Let \((a, b, c, d)\) be an element of \(S\). Show that at least one of \(a, b, c, d\) is divisible by \(3\), and at least one of them is even.
- Prove that if \(d\) is even, then at least one of \(a, b, c\) is even, and that if \(d\) is odd, then at least two of \(a, b, c\) are even.
- Conclude that \(m\) is divisible by \(2 \cdot 2 \cdot 3\).