Number Theory A Solutions

1. Find the integer x for which 1353 + 1383 = x3 − 1.

Proposed by Sunay Joshi
Answer: 172
We claim that x = 172.
First, we show that x lies in the interval [138, 184]. That the lower bound holds is clear. To
see the upper bound, note that
√
x3 = 1353 + 1383 + 1 ≤ 2 · 1383 → x ≤ 2 · 138
3

√
Let 3 2 = 1 + h; then
√ (1 + h)3 = 2. By Bernoulli’s Inequality, 1 + 3h ≤ (1 + h)3 , implying that
h ≤ 3 and hence 2 ≤ 34 . Our upper bound is therefore x ≤ 43 · 138 = 184, as claimed.
1 3

Next, we consider the equation x3 = 1353 + 1383 + 1 modulo p for p = 5, 11. We choose these
values of p because for p ̸= 1 (mod 3), the cubing map x 7→ x3 is a bijection from Z/pZ to
itself. For p = 5, we compute x3 ≡ 03 + 33 + 1 ≡ 3 (mod 5), hence x ≡ 2 (mod 5). For p = 11,
we compute x3 ≡ 33 + 63 + 1 ≡ 2 (mod 11), hence x ≡ 7 (mod 11). By the Chinese Remainder
Theorem, it follows that x ≡ 7 (mod 55), and it is easy to see that the unique number of the
form 55k + 7 in the interval [138, 184] is 172.
Remark: This identity was discovered by Ramanujan.
2. A number is called good if it can be written as the sum of the squares of three consecutive
positive integers. A number is called excellent if it can be written as the sum of the squares
of four consecutive positive integers. (For instance, 14 = 12 + 22 + 32 is good and 30 =
12 + 22 + 32 + 42 is excellent.) A good number G is called splendid if there exists an excellent
number E such that 3G−E = 2025. If the sum of all splendid numbers is S, find the remainder
when S is divided by 1000.
Proposed by Sunay Joshi
Answer: 447
Any good number can be written as (n − 1)2 + n2 + (n + 1)2 = 3n2 + 2 for some n ≥ 2.
Similarly any excellent number can be written as (m − 1)2 + m2 + (m + 1)2 + (m + 2)2 =
(2m + 1)2 + 5 for some m ≥ 2. Therefore, a good number 3n2 + 2 (with n ≥ 2) is excellent
iff there exists m ≥ 2 such that 3(3n2 + 2) − ((2m + 1)2 + 5) = 2025. Rearranging, this
is equivalent to 9n2 − (2m + 1)2 = 2024. By the difference of squares, this becomes (3n −
(2m + 1))(3n + (2m + 1)) = 23 · 11 · 23. Since the two factors add to the even number 6n,
it is clear that each must be even. The possible factor pairs (x, y) with x < y and x, y > 0
are thus (2, 4 · 11 · 23), (4, 2 · 11 · 23), (2 · 11, 4 · 23), and (4 · 11, 2 · 23). These correspond to
(n, m) = (169, 252), (85, 125), (19, 17), (15, 0). Since we require m, n ≥ 2, only the first three
pairs are valid solutions. It follows that n ∈ {169, 85, 19}, so the set of splendid numbers is
{3 · 1692 + 2, 3 · 852 + 2, 3 · 192 + 2}. Thus S = (3 · 1692 + 2) + (3 · 852 + 2) + (3 · 192 + 2), which
is congruent to 447 (mod 1000).
3. Call an arrangement of n not necessarily distinct nonnegative integers in a circle wholesome
when, for any subset of the integers such that no pair of them is adjacent in the circle, their
average is an integer. Over all wholesome arrangements of n integers where at least two of
them are distinct, let M (n) denote the smallest possible value for the maximum of the integers
in the arrangement. What is the largest integer n < 2023 such that M (n + 1) is strictly greater
than M (n)?

1
 Proposed by Austen Mazenko
Answer: 2018
The idea is as follows: consider any k ≤ ⌊(n − 1)/2⌋ not pairwise adjacent integers in a
wholesome arrangement. By Pigeonhole, at least one of them can be replaced by one of its
neighbors to get another subset such that no two are pairwise adjacent; this integer and its
neighbor are thus equivalent modulo k, and by symmetry around the circle, this means that
all of the intgers are congruent modulo k for all such k. If n is odd, this covers all possible
integers; letting them all be 0 except for one which is lcm(1, 2, ..., ⌊(n − 1)/2⌋) is therefore
optimal, and M (n) equals this least common multiple in such cases. If n is even, we have to
consider the two disjoint subsets consisting of n/2 of the integers with no two adjacent. In this
case, their sum must be a multiple of n/2, but evidently generalizing the previous construction
such that the integers in the circle are alternating with values 0 and lcm(1, 2, ..., ⌊(n − 1)/2⌋)
shows M (2m) = M (2m − 1) (since M (2m) ≥ M (2m − 1) obviously holds by just ignoring one
of the extra integers, and we just showed equality is achievable). Now, M (2m + 1) = M (2m)
whenever lcm(1, 2, ..., m) = lcm(1, 2, ..., m − 1). Thus the desired condition holds precisely
when m ∤ lcm(1, 2, ..., m − 1), meaning m is a prime power. Specifically, we want to find the
largest m such that 2m < 2023 and m is a prime power. A quick check shows that m = 1009
is prime, so our answer is 2018.
4. What is the smallest possible sum of six distinct positive integers for which the sum of any
five of them is prime?
Proposed by Austen Mazenko
Answer: 74
The smallest possible sum is 74, achieved for the integers 1, 3, 7, 15, 21, 27.
Consider the sum of the smallest five integers, which is 47 in this case. Suppose there was a
more optimal solution with a smallest sum larger than 47. Now, the five other sums must be
distinct prime numbers greater than this value, meaning the sum of the largest five integers is
at least six primes greater than 47; in particular, it’s at least 73, meaning the sum of all six
integers is at least 74 as claimed.
Now, suppose the sum of the smallest five integers is p < 47, and let the integers be a1 , a2 , ..., a6
in increasing order. Thus, a1 +a2 +a3 +a4 +a5 = p, and since subbing out any of the summands
for a6 gives another prime sum, p + a6 − ai is prime for 1 ≤ i ≤ 5. Since p ̸= 2, it’s odd,
so a6 − ai is even meaning all the ai have the same parity; hence, they’re all odd. Thus,
p ≥ 1 + 3 + 5 + 7 + 9 = 25, so we need to check p = 29, 31, 37, 41, 43. Define pi := p + a6 − ai ,
so pi is some prime larger than p. Summing the equation a6 − ai = pi − p for 1 ≤ i ≤ 5 gives
p+ 5i=1 (pi −p)
P5 P
5a6 − p = i=1 (pi − p), so a6 = 5 . Since the ai are increasing, p1 is the largest
difference, and thus a6 = a1 + p1 − p > p1 − p. For a fixed p1 , we maximize a6 by taking
p+ 5i=1 (pi −p)
P
p2 , p3 , p4 , p5 to be the four primes just less than p1 . Then, we need 5 > p1 − p,
which is equivalent to
P5 5
p+ i=1 (pi − p1 + p1 − p) X
> p1 − p ⇔ p > (p1 − pi ) ⋆.
5 i=1

Looking at differences of consecutive primes

Pat least 29 and at most 73, namely 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
5
we see that the minimal possible value for i=1 (p1 −pi ) is 2+(2+4)+(2+4+6)+(2+4+6+2) =
P5
34, so p = 29, 31 do not work. Finally, since p + i=1 (pi − p) must be a multiple of 5, sim-
ply checking p = 37, 41, 43 gives the result. Specifically, if p = 43, then p1 = 67 or 71. To
accommodate the modulo 5 constraint, the only values for the other pi are 47, 53, 59, 61 and
47, 53, 59, 67, respectively, but these do not satisfy ⋆. If p = 41, then to accommodate the

2
 modulo 5 constraint either p1 = 71 in which case the other primes must be 43, 47, 61, 67 or
47, 53, 61, 67, neither of which satisfy ⋆, or p1 = 67 so the other primes are 43, 47, 53, 59 which
also fail. Finally, if p = 37, then in order for ⋆ to be satisfied, we must have p1 = 71 and the
other primes are 53, 59, 61, 67, but this violates the modulo 5 condition, so we may conclude.
5. You play a game where you and an adversarial opponent take turns writing down positive
integers on a chalkboard; the only condition is that, if m and n are written consecutively on
the board, gcd(m, n) must be squarefree. If your objective is to make sure as many integers
as possible that are strictly less than 404 end up on the board (and your opponent is trying to
minimize this quantity), how many more such integers can you guarantee will eventually be
written on the board if you get to move first as opposed to when your opponent gets to move
first?
Proposed by Austen Mazenko
Answer: 94
Note that you can always write squarefree numbers on the board, and thus regardless of
whether you move first or second, you can guarantee all squarefree numbers less than 404 get
written. Now, if you go second, your opponent can guarantee that you can only write squarefree
numbers by simply writing multiples of 22 · 32 · 52 · · · 4012 on the board. Thus, it suffices to
find the maximum number of non-squarefree numbers you can guarantee get written on the
board if you go first. For any prime p, if you ever write a number m such that p2 ∤ m, then
your opponent can continually choose multiples of p2 that are greater than 404 which prevents
you from writing any more multiples of p2 . Note also that writing any number greater than
404 functionally just stalls the game by a round and cannot give you any advantage. Thus, to
play optimally, you should thus write all multiples of 22 · 32 = 36 less than 404, after which
you should write everything expressible as 4 times a number with no odd divisors that are the
squares of a prime, then finally squarefree integers. Tallying, we see there are 11 multiples of
36. Then, looking at 4 times an odd number, we see there are 26 possibilities (odd primes
and 1) plus 9 possibilities (3 times an odd prime) plus 5 possibilities (5 times an odd prime)
plus 2 possibilities (7 times an odd prime). Next, looking at 8 times an odd number, we see
there are 15 possibilities (odd primes and 1) plus 4 possibilities (3 times an odd prime) plus 1
possibility (35); next, looking at 16 times an odd number, we see there are 9 possibilities plus
2 possibilities; next, looking at 32 times an odd number, we see that there are 5 possibilities,
then for 64 there are 3 possibilities, for 128 there are 2, and for 256 there is just the 1. In
total, we get 11 + 26 + 9 + 5 + 2 + 15 + 4 + 1 + 9 + 2 + 5 + 3 + 2 = 94.
6. How many positive integers n ≤ lcm(1, 2, . . . , 100) have the property that n gives different
remainders when divided by each of 2, 3, . . . , 100?
Proposed by Daniel Zhu
Answer: 1025
Observe that, of the remainders 0, 1, ..., 99, exactly one will not be used. Moreover, notice that
choosing a remainder for each integer 2, 3, ..., 100 uniquely determines n ≤ lcm(1, 2, ..., 100) by
Chinese remainder theorem (CRT).
If 0 isn’t the excluded remainder, let a be the unique number that n leaves a remainder of
0 divided by, so a|n. Clearly, a must be prime, as otherwise n would also leave a remainder
when divided by a factor of a greater than 1. Assume for now that a > 2. Considering the
remainders of n modulo 2, 3, 4, ..., a − 1, we note that they are fixed; because 0 is already used
modulo a, the only possible remainder modulo 2 is 1; since 0 and 1 are already used, the only
possible remainder modulo 3 is 2, and so on. Looking at n (mod a + 1), because a is prime
a+1 isn’t, so by Chinese remainder theorem n must be −1 modulo the factors of a+1 meaning
n ≡ a (mod a + 1). Now, if 2a ≤ 100, because a|n we must have that n modulo 2a is either 0

3
 or a, contradiction as both of these remainders have already used. Thus, a must be a prime
between 50 and 100.
Now, suppose that n is odd, meaning n ≡ 1 (mod 2). We claim that n ≡ k − 1 (mod k)
for all 2 ≤ k ≤ 100 such that k is not a prime between 50 and 100. This follows by strong
induction. The base case k = 2 holds by assumption. Then, for higher k, if k is composite then
by Chinese remainder theorem on its factors and the inductive hypothesis we have n ≡ −1
(mod k). Contrarily, if k is prime, by induction the possible unused remainders are 0 and
k − 1, but we showed earlier that if 0 is a remainder it must be mod 2 or a prime greater
than 50, so it can’t be the remainder of n modulo k. This establishes the claim. Next, let
p1 < p2 < · · · < p10 denote the primes between 50 and 100. We thus want to find the number
of ways to allocate all but one of the elements in the set {0} ∪ {p1 − 1, ..., p10 − 1} as remainders
of n modulo the elements in {p1 , ..., p10 }. Assigning the remainder to p1 first, then p2 , etc., up
to p10 , note there are two choices at each step, for a total of 210 distinct allocations.
The remaining case is that n is even; we claim this forces n ≡ k−2 (mod k) for all 2 ≤ k ≤ 100.
But, we see by induction the even remainders are fixed, and then by induction again for odds
k we see that k − 1, k − 2 are the only possible remainders, but k − 1 is the remainder modulo
the even number k + 1, so it must be k − 2. Thus, this contributes one additional possible
value for n, making our answer 210 + 1 = 1025.
7. Define f (n) to be the smallest integer such that for every positive divisor d|n, either n|dd or
dd |nf (n) . How many positive integers b < 1000 which are not squarefree satisfy the equation
f (2023) · f (b) = f (2023b)?
Austen Mazenko
Answer: 5
The crux of the problem is the following claim:
Lemma 1: Let n = i pei i be the prime factorization of n. Then f (n) = n
Q
e .
mini pi i
n
Proof : To prove it, we first show that this value is necessary. Let d = e |n. Denoting
mini pi i
k := arg mini pei i , trivially pk |n but d = n
e
pkk
d
=⇒ pk ∤ d =⇒ pk ∤ d , so n ∤ d . d

Because dd |nf (n) , νpi (dd ) ≤ νpi (nf (n) ) which, for i ̸= k, is ei · pnek ≤ ei · f (n), so n
e
mini pi i
≤ f (n)
k
as claimed.
n
ei
To see that it’s sufficient, we split into cases to show that d|n implies n|dd or dd |n mini pi .
First, suppose there exists some prime pj |n that doesn’t divide d. Denote dj := nej . Then,
pj
n
d d ei
d
d|dj =⇒ d |dj j , and dj j |n mini pi because for any ℓ ̸= j,
 n 
d n ei
νpℓ (dj j ) = eℓ · dj ≤ eℓ · = ν pℓ n mini pi .
mini pei i

It remains to address the case where d possesses the same prime factors as n. Write d = i pai i
Q
with 1 ≤ ai ≤ eiQfor each i, and consider when n|dd . It holds whenever for each ℓ we Q have
νpℓ (n) = eℓ ≤ aℓ · i pai i = νpℓ (dd ). Next, suppose there exists some k such that ek > ak · i pai i .
n
ei
It suffices to show Q that in this case we have dd |n mini pi , which by Q looking at valuations
is the same as aℓ · i pai i ≤ eℓ · minn pei for each ℓ. By assumption, i pai i < maxi aeii , so
i i
aℓ Q ai a ℓ ek n
eℓ · i pi < eℓ · ak ≤ mini pei which implies the result. To see why this last inequality holds,
i
note that if n is a prime power then we have equality as ℓ = k. Otherwise,
n √ Y e /2 ek aℓ
ei ≥ n= pi i ≥ 21/2 · 2ek /2 ≥ ek ≥ · ,
mini pi i
ak eℓ

4
 which is precisely the claimed bound. □
n
To finish the problem, for simplicity denote g(n) := f (n) , so g(n) is the smallest prime power
m n
appearing in the prime factorization of n. Notice f (m) · f (n) = f (mn) ⇐⇒ g(m) · g(n) =
mn
g(mn) ⇐⇒ g(mn) = g(m) · g(n), so it suffices to solve g(2023b) = g(2023) · g(b) = 7g(b).
Now, g(b) and g(2023b) are both prime powers, and thus must both be powers of 7. If 49|g(b),
then either g(b) = 49 or 343 because otherwise g(b) must have some other prime power factor,
but this would have to exceed 49, so b > 492 > 1000. However, if b ≥ 49 is a power of 7 then
g(2023b) is not, contradiction. Thus, g(b) = 7, forcing g(2023b) = 49. Writing b = 7a for
some 7 ∤ a, we see that any prime power dividing a other than 17 must be at least 49. If 17|a,
then either 172 |a =⇒ b > 1000 or a is 7 · 17· some prime power greater than 49, which again
forces b > 1000. Thus, the only possibilities are a is a prime power greater than 49 (and with
exponent greater than 1) such that 7a < 1000. Tabulating, we see the only possibilities are
b = 7 · 64, 7 · 81, 7 · 121, 7 · 125, 7 · 128, giving a final answer of 5.
8. Let S0 = 0, S1 = 1, and for n ≥ 2 let Sn = Sn−1 + 5Sn−2 . What is the sum of the five smallest
primes p such that p | Sp−1 ?
Proposed by Owen Yang
Answer: 185
 √ n  √ n 
√1 1+ 21 1− 21
Claim 1: Sn = 21 2 − 2

Proof: We proceed by strong induction. Our base cases are S0 = 0 and S1 = 1 which can be
easily checked to work. For the inductive step, we have that
√ !2 √ √ √
1 + 21 22 + 2 21 11 + 21 1 + 21
= = = +5
2 4 2 2

and similarly
√ !2 √ √ √
1− 21 22 − 2 21 11 − 21 1 − 21
= = = +5
2 4 2 2
so if the formulas work for Sn−1 and Sn then we have
√ !n √
 !n−1
1  1 + 21 1+ 21
Sn+1 = Sn + 5Sn−1 = √ +5
21 2 2

√ !n √ !n−1 
1− 21 1− 21
− −5 
2 2
√ !n √ !n !
1 1+ 21 1− 21
=√ −
21 2 2
as desired.
Claim 2:
2 ⌋
P⌊ n−1 n


k=0 2k+1 21k
Sn =
2n−1
Proof: We compute the coefficients in the binomial expansions of the formula from Claim 1.
We have Pn n
√ i Pn n
√ i !
1 i=0 i 21 − i=0 i (− 21)
Sn = √
21 2n

5
for which the coefficients cancel when i is even and are doubled when i is odd. Re-indexing
with i = 2k + 1, we find that

⌊ 2 ⌋
 P n−1
n

k √  P⌊ n−1 2 ⌋ n

k
1  k=0 2 2k+1 21 21  k=0 2k+1 21
Sn = √ =
21 2n 2n−1

as desired.
p−1 p−1
Claim 3: For prime p ̸= 2, we have that Sp ≡ 21 mod p and Sp+1 ≡ 2−1 (1+21 2 ) mod p.
2

Proof: Note that since p is prime, p divides all binomial coefficients nk with n = p except

for k = 0 and k = p. Then since the sum formula from Claim 2 contains only coefficients with
k odd, the only one not divisible by p is the last one, pp = 1 (here we use the fact that p is

odd). Then we find that

⌊X2 ⌋
p−1

p−1 p p−1
2 Sp = 21k ≡ 21 2 (mod p)
2k + 1
k=0

p−1
and since 2p−1 ≡ 1 (mod p) by Fermat’s Little Theorem, we obtain that Sp ≡ 21 2 (mod p)
as desired. Similarly, for n = p + 1 we know that p divides all coefficients between k = 2 and
p − 1, inclusive. The odd values of k are 1 and p, so

⌊X
2⌋
p
    
p p+1 p+1
k 0 p+1 p−1
2 Sp+1 = 21 ≡ 21 + 21 2 (mod p)
2k + 1 1 p
k=0

p−1 p−1
≡ (p + 1)(1 + 21 2 ) (mod p) ≡ 1 + 21 2 (mod p)
so that p−1
2p Sp+1 ≡ 2Sp+1 ≡ 1 + 21 2 (mod p)
p−1
=⇒ Sp+1 ≡ 2−1 (1 + 21 ) (mod p) 2

 
Claim 4: For prime p ̸= 2, 3, 5, 7, p | Sp−1 ⇐⇒ 21
p = 1.
Proof:
  First note that Sp+1 ≡ Sp + 5Sp−1 (mod p) =⇒ Sp−1 ≡ 5−1 (Sp+1 − Sp ). Now
p−1
if 21
p = 1 then 21 2 ≡ 1 (mod p) and from Claim 3 we calculate that Sp ≡ Sp+1 ≡ 1
(modp). Then Sp−1 ≡ 5−1 (Sp+1 − Sp ) ≡ 0 (mod p) as desired. For the inverse, since p ∤ 21 we
p−1
have 21
p = −1, so that 21 2 ≡ −1 (mod p). In particular, Sp ≡ −1 (mod p) and Sp+1 ≡ 0
(mod p), so Sp−1 ≡ 5−1 ̸≡ 0 (mod p).
Now we can explicitly check the edge cases: we have 2 ∤ S1 = 1, 3 ∤ S2 = 1, 5 ∤S4 = 11,
and 7 ∤ S6 = 86. Therefore, we just need to find the smallest five primes such that 21p = 1.
     (p−1)
(1+3) p p p p
By quadratic reciprocity, we have that 21 = p3 7





p = (−1) 7 = 3 7 .
2
p 3
Then p must be either a residue or non-residue in both moduli, i.e. both p ≡ 1 (mod 3) and
p ≡ 1, 2, or 4 (mod 7), or both p ≡ 2 (mod 3) and p ≡ 3, 5, or 6 (mod 7). The smallest five
primes with this property are 17, 37, 41, 43, and 47, so our final answer is 17+37+41+43+47 =
185 .