Inmotc NT

INMOTC: Number Theory
Rohan Goyal
January 2023
§1 Problems
Problem 1.1. We call natural number n crazy iff there exist natural numbers a, b > 1
such that n = ab + b. Whether there exist 2023 consecutive natural numbers among
which are 2021 crazy numbers?
Problem 1.2. Let p be an odd prime. How many non-empty subsets of
{1, 2 · · · p − 1}
have a sum which is divisible by p?

Problem 1.3. Let a0 = 4 and define a sequence of terms using the formula an =
a2n−1 − an−1 for each positive integer n:
1. Prove that there are infinitely many prime numbers which are factors of atleast
one term in the sequence?
2. Are there infinitely many prime numbers which are factors of no terms in the
sequence?
Problem 1.4. Which positive integers can be written in the form
lcm(x, y) + lcm(y, z)
lcm(x, z)
for positive integers x, y, z?
Problem 1.5. Prove that for any prime p, there exists a positive integer n such that
1n + 2n−1 + 3n−2 + · · · + n1 ≡ 2023 (mod p).
Problem 1.6. Is there an infinite sequence of positive integers where no two terms are
relatively prime, no term divides any other term, and there is no integer larger than 1
that divides every term of the sequence?
Problem 1.7. Let m > 1 be a fixed positive integer. For a nonempty string of base-ten
digits S, let c(S) be the number of ways to split S into contiguous nonempty strings of
digits such that the base-ten number represented by each string is divisible by m. These
strings are allowed to have leading zeroes.
In terms of m, what are the possible values that c(S) can take?
For example, if m = 2, then c(1234) = 2 as the splits 1234 and 12|34 are valued, while
the other six splits are invalid.
1
Rohan Goyal (January 2023) INMOTC: Number Theory
Problem 1.8. The set of positive integers is partitioned into n disjoint infinite arithmetic
progressions S1 , S2 , . . . , Sn with common differences d1 , d2 , . . . , dn , respectively. Prove
that there exists exactly one index 1 ≤ i ≤ n such that
n
1 Y
dj ∈ Si .
di
j=1
Problem 1.9. Suppose a1 , a2 , . . . is an infinite strictly increasing sequence of positive

integers and p1 , p2 , . . . is a sequence of distinct primes such that pn | an for all n ≥ 1. It
turned out that an − ak = pn − pk for all n, k ≥ 1. Prove that the sequence (an )n consists
only of prime numbers.
Problem 1.10. Prove that there exist infinitely many positive integers n such that the
largest prime divisor of n4 + n2 + 1 is equal to the largest prime divisor of (n + 1)4 +
(n + 1)2 + 1.
Problem 1.11. Alice had picked positive integers a, b, c and then tried to find positive
integers x, y, z such that a = lcm(x, y), b = lcm(x, z), c = lcm(y, z). It so happened that
such x, y, z existed and were unique. Alice told this fact to Bob and also told him the
numbers a and b. Prove that Bob can find c.
Problem 1.12. Find all functions from positive integers to themselves, such that for
any positive integers m, n the two conditions below are equivalent:
• n divides m.
• f (n) divides f (m) − n.
Problem 1.13. Denote by E(n) the number of 1’s in the binary representation of a
positive integer n. Call n interesting if E(n) divides n. Prove that:
• there cannot be five consecutive interesting numbers, and
• there are infinitely many positive integers n such that n, n + 1 and n + 2 are each
interesting.
2018
Problem 1.14. Given a sequence of positive integers a1 , a2 , a3 , ... defined by an = ⌊n 2017 ⌋.
Show that there exists a positive integer N such that among any N consecutive terms in
the sequence, there exists a term whose decimal representation contain digit 5.
Problem 1.15. The integer N is positive. There are exactly 2005 ordered pairs (x, y) of
positive integers satisfying
1 1 1
+ = .
x y N
Prove that N is a perfect square.
Problem 1.16. Prove that for every positive integer n, there exists a polynomial with
integer coefficients whose values at points 1, 2, . . . , n are pairwise different powers of 2.
Problem 1.17. Prove that if from any 2007 consecutive terms of an infinite arithmetic
progression of integers starting with 2, one can choose a term relatively prime to all the
2006 other terms, then there is also a term amongst any 2008 consecutive terms relatively
prime to the rest.
Problem 1.18. Mad scientist Kyouma writes N positive integers on a board. Each
second, he chooses two numbers x, y written on the board with x > y, and writes the
number x2 − y 2 on the board. After some time, he sends the list of all the numbers on
the board to Christina. She notices that all the numbers from 1 to 1000 are present on
the list. Aid Christina in finding the minimum possible value of N.
2
Problem 1.19. Show that there are infinitely many pairs of positive integers (m, n)
such that
m+1 n+1
+
n m
is a positive integer.
Problem 1.20. Find all natural numbers m, n such that m2 + 3 = n3
Problem 1.21. Find all positive integers n such that for any integer k there exists an
integer a for which a3 + a − k is divisible by n.
Problem 1.22. Determine all the pairs (p, n) of a prime number p and a positive integer
p +1
n for which npn +1 is an integer.
Problem 1.23. Let m, n be distinct positive integers. Prove that
gcd(m, n) + gcd(m + 1, n + 1) + gcd(m + 2, n + 2) ≤ 2|m − n| + 1.
Further, determine when equality holds.
Problem 1.24. For n ∈ N, let P (n) denote the product of distinct prime factors of n,
with P (1) = 1. Show that for any a0 ∈ N, if we define a sequence ak+1 = ak + P (ak ) for
k ≥ 0, there exists some k ∈ N with ak /P (ak ) = 2015.
Problem 1.25. A function f is defined on the positive integers by f (1) = 1 and, for
n > 1,
2n − 1 2n
f (n) = f +f
3 3
Problem 1.26. The real number x between 0 and 1 has decimal representation
0.a1 a2 · · ·
with the property that the number of distinct blocks of the form
ak ak+1 · · · ak+2022
as k ranges through all positive integers is at most 2023. Prove that x is rational.
Problem 1.27. Prove that for every positive integer n, there exists a 2n-digit number
a2n a2n−1 · · · a1 for which the following equality holds:
a2n · · · a1 = (an · · · a1 )2
Problem 1.28. Determine all positive integers k for which there exist a positive integer
m and a set S of positive integers such that any integer n > m can be written as a sum
of distinct elements of S in exactly k ways.
Problem 1.29. Find all positive integers n such that n3 − 5n2 + 9n − 6 is a perfect
square.
Problem 1.30. The integer x is atleast 3 and n = x6 − 1. Let p be a prime and k be a

positive integer such that pk is a factor of n. Show that p3k < 8n.
Problem 1.31. Is there a natural number n > 101000 which is not divisible by 10 and
which satisfies: in its decimal representation one can exchange two distinct non-zero
digits such that the set of prime divisors does not change.
3
Problem 1.32. Let p and q be (not necessarily distinct) primes. Prove that at most
p−1
2 numbers n satisfy:
p! + n! + q = p(np )
Problem 1.33. Find all pairs of integers (a, b) so that each of the two cubic polynomials
x3 + ax + b and x3 + bx + a
has all the roots to be integers.
Problem 1.34. The function f is defined on the set of positive integers by f (1) = 1,
f (2n) = 2f (n) and nf (2n + 1) = (2n + 1)(f (n) + n) for all n ≥ 1.
• Prove that f (n) is always an integer.

• For how many positive itnegers less than 2023 is f (n) = 2n?
Problem 1.35. Let n and M be positive integers such that M > nn−1 . Prove that there
are n distinct primes p1 , p2 , p3 · · · , pn such that pj divides M + j for all 1 ≤ j ≤ n.
Problem 1.36. Alice has an integer N > 1 on the blackboard. Each minute, she deletes
the current number x on the blackboard and writes 2x + 1 if x is not the cube of an
integer, or the cube root of x otherwise. Prove that at some point of time, she writes a
number larger than 10100 .
p
Problem 1.37. Let m = 4 3−1 , where p is a prime number exceeding 3. Prove that 2m−1
has remainder 1 when divided by m.
Problem 1.38. Let a > 1 and c be natural numbers and let b ̸= 0 be an integer. Prove
that there exists a natural number n such that the number an + b has a divisor of the
form cx + 1, x ∈ N.
Problem 1.39. Find all permutations (a1 , a2 , ..., a2021 ) of (1, 2, ..., 2021), such that for
every two positive integers m and n with difference bigger than 2021 , the following
inequality holds: GCD(m + 1, n + a1 ) + GCD(m + 2, n + a2 ) + ... + GCD(m + 2021, n +
a2021 ) < 2|m − n|.
Problem 1.40. For his birthday, math prodigy Tom received a positive integer m and
two
increasing positive sequences {an } and {bn }. Tom claims that no element of the set
2
ai bj + m | (i, j) ∈ N has a prime divisor larger than 2023!. Prove that young Tom’s a
liar.
Problem 1.41. For each positive integer n, the Bank of Cape Town issues coins of
denomination n1 . Given a finite collection of such coins (of not necessarily different
denominations) with total value at most most 99 + 12 , prove that it is possible to split
this collection into 100 or fewer groups, such that each group has total value at most 1.
Problem 1.42. For a positive integer n define Sn = 1! + 2! + . . . + n!. Prove that there
exists an integer n such that Sn has a prime divisor greater than 102021 .

Inmotc NT

Uploaded by

Copyright:

Available Formats

Inmotc NT

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Inmotc NT

Uploaded by

Copyright:

Available Formats

INMOTC: Number Theory

have a sum which is divisible by p?

1n + 2n−1 + 3n−2 + · · · + n1 ≡ 2023 (mod p).

Problem 1.9. Suppose a1 , a2 , . . . is an infinite strictly increasing sequence of positive

Problem 1.20. Find all natural numbers m, n such that m2 + 3 = n3

Problem 1.23. Let m, n be distinct positive integers. Prove that

gcd(m, n) + gcd(m + 1, n + 1) + gcd(m + 2, n + 2) ≤ 2|m − n| + 1.

Further, determine when equality holds.

Problem 1.30. The integer x is atleast 3 and n = x6 − 1. Let p be a prime and k be a

has all the roots to be integers.

• Prove that f (n) is always an integer.

You might also like