Advanced Number Theory

Adithya B., Brian L., William W., Daniel X.

9/9

§1 Quadratic Residues
When we are working with natural numbers, it is easy to tell if a number has a square root
- just check if it is a perfect square. However, it is much harder when we are working with
modular arithmetic. For example, 3 is definitely not a perfect square, yet in (mod 1)1,
we have that 52 ≡ 3 (mod 11), showing that it is a square under some modulos. As
it is often important to determine whether a number actually has a square root, this
motivates us to give perfect squares under modular arithmetic a special name:
Definition 1.1 (Quadratic residue). Let p be a prime number. We say a (mod p) is a
quadratic residue if there exists some integer x such that x2 ≡ a (mod p).

Lemma 1.2 (number of quadratic residues)

p+1
For an odd prime p, there are exactly 2 quadratic residues.

 2
p+1 p−1
Proof. We can try constructing a set of 2 quadratic residues. Note that 02 , 12 , . . . , 2
are all quadratic residues. To show that they are distinct, note that if a2 ≡ b2 (mod p)
for distinct a, b, then (a + b)(a − b) ≡ 0 (mod p). As a 6≡ b, we must have a + b ≡ 0
(mod p). However, for the perfect squares that we have listed above 0 < a + b < p, so
we have constructed p+1 2 distinct quadratic residues. To show that there are no other
quadratic residues, note that (p − x)2 ≡ x2 (mod p).

We notice that quadratic residues occur in exactly half of the nonzero residues modulo
p. To discuss further about quadratic residues, we will first introduce some notation.
Definition 1.3 (Legendre symbol). Let S be the set of quadratic residues modulo a
prime p. Then, for an integer a we define the Legendre symbol to be

   1 a 6≡ 0 (mod p) and a ∈ S
a
= −1 a 6∈ S .
p 
0 a ≡ 0 (mod p)


To determine whether a number is a quadratic residue, one method we can use is

exponentiation.

Theorem 1.4 (Euler’s criterion)

p−1
 
For an odd prime p, a 2 ≡ ap (mod p).

1
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

Proof. The result is obvious when a ≡ 0 (mod p), so assume otherwise. Let g be a
primitive root. If a is a quadratic residue, then a = g 2k for some k. In that case,
p−1
a 2 ≡ g k(p−1 ≡ 1 (mod p) from Fermat’s Little Theorem, as desired. If a is not a
p−1 2k+1
quadratic residue, then a ≡ g 2k+1 for some k. In that case, a 2 = g 2 (p−1) 6≡ 1
p−1
(mod p). However, since (a 2 )2 ≡ 1 (mod p) by Fermat’s Little Theorem again, and
p−1 p−1
a 2 6≡ 1 (mod p), we must have a 2 ≡ −1 (mod p).

Theorem 1.5
The Legendre symbol is multplicative. That is, we have
    
a b ab
= .
p p p

Proof. This is clear from Theorem 1.4. Note that

    
a b p−1 p−1 p−1 ab
≡ a 2 b 2 = (ab) 2 ≡ (mod p).
p p p

Since the Legendre symbol only takes the values {−1, 0, 1} and p is an odd prime, we
can conclude that the function is multiplicative.

Now, we will discuss one of the most important results in the theory of quadratic
residues, quadratic reciprocity.

Theorem 1.6 (Quadratic Reciprocity)

For distinct odd primes p, q,
  
p q 1
= (−1) 4 (p−1)(q−1) .
q p

Proof. We will present a clever proof by Eisenstein, which involves the following lemma.

Lemma 1.7 (Gauss)

Let a be an integer such that p - a, let rn be the unique integer congruent to an
p−1
  p) such that |rn | is minimum. Then, if R = {1 ≤ n ≤ 2 | rn < 0}, we have
(mod
a |R|
p = (−1) .

Proof. For 1 ≤ i ≤ p−1 2 , there is a unique n such that rn is equal to i or −i. To show
this, note that if |rx | = |ry |, then (rx ± ry ) = 0 =⇒ n(x ± y) ≡ 0 (mod p), which cannot
occur for 1 ≤ x, y ≤ p−1 p−1
2 . Therefore, each |rn | is distinct, and there are 2 values of n.
p−1
Since 1 ≤ |rn | ≤ 2 , each value is obtained exactly once, as desired. Now, this means

2
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

that
 
p−1 Y Y Y
!= i= (−rn ) · rn
2
1≤i≤ p−1
2
1≤n≤ p−1
2
,n∈R 1≤n≤ p−1
2
,n6∈R
p−1
2
Y
|R|
= (−1) rn
n=1
p−1
Y2

≡ (−1)R (an)
n=1
 
p−1
p−1
= (−1)|R| a 2 ! (mod p)
2
  p−1
 
Therefore, we see a
p ≡a 2 ≡ (−1)|R| (mod p), so ap = (−1)|R| .


We can use this to prove another result about the Legendre symbol.

Lemma 1.8
  P p−1
2
j k
an
a n=1
We have that p = (−1) p
.

Proof. By the previous lemma, we have

p−1 p−1
2    2
X an X Y X
an − = (rn + p) · rn = p|R| + rn .
p
n=1 1≤n≤ p−1 ,n∈R 1≤n≤ p−1 ,n6∈R n=1
2 2

p−1
Since |rn | takes all values from 1 to 2 .

p−1 p−1 p−1

2
X 2
X 2
X
rn = |rn | = an (mod 2).
n=1 n=1 n=1

P p−1 j k
an
Therefore, p|R| ≡ |R| ≡ 2
n=1 p (mod 2), so
  P p−1 j k
a |R|
2
n=1
an
= (−1) = (−1) p
.
p


To compute this sum, we will use the following lemma.

Lemma 1.9
If a, b are odd positive integers such that gcd(a, b) = 1,
b−1 a−1
2 j 2  
X an k X bn (a − 1)(b − 1)
+ = .
b a 4
n=1 n=1

3
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

Proof. Consider the rectangle bounded by the axes and the lines x = 2b and y = a2 . The
first sum counts the number of lattice points that are below the line y = ab x. The second
sum counts the number of points above this line. Since there are no lattice points on this
line inside the rectangle, as gcd(a, b) = 1, the total sum is equal to the number of lattice
points inside the rectangle or (a−1)(b−1)
4 . 

Combining all the lemmas above,

   P p−1 j k P q−1 j k
p q 2 qn 2 pn 1
= (−1) n=1 p · (−1) n=1 q = (−1) 4 (p−1)(q−1) .
q p

We would also like to know how to determine whether −1 and 2 are quadratic residues.

Theorem 1.10 (Quadratic reciprocity extensions for -1 and 2)

For an odd prime p,
   
−1 1 2 1 2
= (−1) 2
(p−1)
, = (−1) 8 (p −1)
p n

Proof. The first part of the theorem follows directly from work above. Observe that this
implies −1 is a quadratic residue if p ≡ 1 (mod 4) and −1 is not a quadratic residue if
p ≡ 3 (mod 4). For the second part of the theorem, note that
p−1 p−1
  bY4 c 2
p−1 p−1 Y
2 2 · ! = 2 · 4 · 6···p − 1 = (2k) · (2k)
2 p−1
k=1 k=b c+1
4
p−1 p+1
bYc4 bY4 c
p+1
≡ b
(2k) · (−1) 4 c (2k − 1)
k=1 k=1
p−1
2
p+1
≡ (−1)b 4 c
Y
k
k=1
 
p−1 p−1
≡ (−1)b 2 c !.
2
Therefore,  
2 p−1 p+1
≡ 2 2 ≡ (−1)b 4 c .
p
j k 2
We can verify easily for all odd primes that p+1
4 ≡ p 8−1 (mod 2), so we are done.

In particular, we see 2 is a quadratic residue when p ≡ 1 (mod 8) or p ≡ 7 (mod 8),

and 2 is a quadratic nonresidue when p ≡ 3 (mod 8) and p ≡ 5 (mod 8).
With that said, let’s move on to some basic examples.

Example 1.11
The positive integers a and b are such that the numbers 15a + 16b and 16a − 15b
are both squares of positive integers. Let S be the smallest possible value of a + b.
Compute S (mod 1000).

4
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

Solution. Let 15a + 16b = x2 and 16a − 15b = y 2 . Since we have two equations with
a and b, we can use these equations to solve for a and b in terms of x2 and y 2 . If we
multiply the first equation by 16 and subtract 15 times the second equation, we get

16x2 − 15y 2
481b = 16x2 − 15y 2 =⇒ b = .
481
15x2 +16y 2
Similarly, we get a = 481 . Note that 481 = 13 · 37. Therefore, since a is an integer,

15x2 + 16y 2 ≡ 0 (mod 13) =⇒ 2x2 ≡ −3y 2 (mod 13)

Multiplying both sides by 2−1 ≡ 7 (mod 13), we see x2 = 5y 2 (mod 13). If 13 - y, then
we could write  2
x
= 5 (mod 13).
y
But from quadratic reciprocity,
  
5 13 1
= (−1) 4 ·12·4 = 1.
13 5

Since 13 3



5 = 5 = −1, 5 is a quadratic nonresidue mod 13, which contradicts the work
above. Therefore, we must have 13 | y. If that is true, we directly see that 13 | x as well.
Now, let’s work mod 37. We know that 15x2 + 16y 2 ≡ 0 (mod 37). Therefore,
x ≡ −16 · 15−1 y 2 (mod 37). Note that 15 · 5 ≡ 1 (mod 37), so 15−1 ≡ 5 (mod 37).
2

Therefore, we get x2 = −6y 2 (mod 37).

Assume for the sake of contradiction that 37 - y. Then, it follows that −6 must be a
quadratic residue mod 37. Since the Legendre symbol is multiplicative,
     
−6 −1 2 3
= .
37 37 37 37

Since 37 ≡ 5 (mod 8), 2 is a quadratic non residue and 1 is a quadratic residue. Also, by
quadratic reciprocity,     
3 37 3
= 1 =⇒ = 1,
37 3 37
   
6 3
= −1 · = −1 · 1 = −1.
37 37
Therefore, we see 6 is not a quadratic residue, so we must have 37 | y. This also implies
37 | x.
Combing the above work, 481 | x and 481 | y. Let x = 481x1 and y = 481y1 . Then,

a = 481(15x21 + 16y12 ), b = 481(16x21 − 15y12 ).

We see that a + b is minimized when x1 = y1 = 1. Therefore, we obtain a + b =

481 · 32 ≡ 392 (mod 1000).

Example 1.12 (Folklore)

Find the number of ordered pairs (x, y) with 0 ≤ x, y < 2027 which satisfy

x2 + y 2 ≡ 1 (mod 2027)

5
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

Solution. Note that, for a fixed y, there is 1 solution for x if y 2 = 1, there are 2 if 1 − y 2
is a nonzero quadratic residue, and there are 0 if it is a non quadratic residue
 (NQR).
1−y 2
Letting p = 2027, it is easy to see that these values match with p + 1. So, the
number of solutions is
2026 2026
1 − y2 1 − y2
X   X 
1+ = 2028 +
p p
y=0 y=1

Call the sum on the RHS S. Note that y → y1 is a bijection on (Z/2027Z)× (the nonzero
residues mod 2027), so
  2 
X  1 − y1  2026
2026 X  y 2 − 1   1/y 2 
S= =
p p p

y=1 y=1

By the definition of quadratic residue, the second term should always be 1, so

2026
X  y2  2026
1 − y2
  X   
−1 −1 −1
S= = = S
p p p p
y=1 y=1
 
Now, since p ≡ 3 (mod 4), we know that −1p = −1. Hence, S = −S =⇒ S = 0. So,
our answer is
2028 + S = 2028

§1.1 Aside on the Jacobi Symbol

While the Legendre symbol is multiplicative of the top, we can extend this notion to
the Jacobi symbol so that it is multiplicative on both the top and the bottom. In order
words, the Jacobi symbol would also satisfy
 a  a a 
= .
mn n m
In this case, na = 0 when gcd(a, n) 6= 1. Also, na = m b




when a ≡ b (mod n).
For completeness, we will state the quadratic reciprocity theorem with Jacobi sym-
bols.

Theorem 1.13 (Quadratic reciprocity with Jacobi symbols)

If m and n are odd positive integers with gcd(m, n) = 1, then
m  n  1
= (−1) 4 (m−1)(n−1) .
n m
Also, we have
   
−1 1
(m−1) 2 1 2 −1)
= (−1) 2 , = (−1) 8 (m .
m m

6
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

a


Remark 1.14. It is important to note that n does
not necessarily detect quadratic
a a a



residues. That is, if m = −1 and n = −1, then mn
= 1, but this does not mean a is
a
a quadratic residue mod mn. On the other hand, if mn = −1, then we know that a is a
quadratic nonresidue mod mn.

Example 1.15 (2019 PRIMES M5)

Exhibit a function s : Z>0 → Z with the following property: if a and b are positive
integers such that p = a2 + b2 is an odd prime, then
p−1
s(a) ≡ a (mod p).
2

 
The right-hand side is known as the Jacobi symbol ap .

Solution. We claim the function is


1
 a≡1 (mod 2)
s(a) = −1 a≡2 (mod 4)

1 a≡0 (mod 4)


We can easily check this with quadratic reciprocity using Jacobi symbols. Since p = a2 +b2 ,
we must have p ≡ 1 (mod 4) since 0, 1 are the only quadratic residues mod 4. When
a ≡ 1 (mod 2),
   
a p 1
 p   a2 + b2   b2 
(a−1)(p−1)
= (−1) 4 = = = = 1.
p a a a a

When a ≡ 2 (mod 4), a2 ≡ 4 (mod 8) and b2 ≡ 1 (mod 8) (since b is odd), so p ≡ 5

(mod 8). In this case 2 is not a quadratic residue mod p. Then, we have
    a   2
a + b2
    2
a 2 2 p b
= = −1 · a = −1 · a = −1 · a = −1.
p p p 2 2 2

When a ≡ 0 (mod 4), let k be the maximal integer such that 2k | a. Let a = 2k a1 . In
this case a2 + b2 ≡ 0 + 1 ≡ 1 (mod 8). This means that 2 is a quadratic residue modulo
p. Then, since the Jacobi symbol is multiplicative,
   k        2k 2
2 a1 + b2
  2
a 2 a1 a1 p b
= = = = = = 1.
p p p p a1 a1 a1

Therefore, our function works and we are done.

§2 p-adic Valuations
Definition 2.1. Let p be a prime number and n be any positive integer. We define the
p-adic valuation of n to be the largest nonnegative integer k such that n is divisible by
pk . This integer k is often written as νp (n).

For example, ν2 (96) = 5 because 25 is the largest power of 2 that divides 96. There
are some elementary properties of the p-aidc valuation that you should check:

7
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

• νp (a + b) ≥ min(νp (a), νp (b)). (In fact, if νp (a) 6= νp (b) then equality holds.)

• νp (ab) = νp (a) + νp (b)

We discuss a couple of useful theorems regarding p-adic valuations:

Theorem 2.2 (Legendre’s Formula)

j k j k j k j k
For any prime p and positive integer n, νp (n!) = np + pn2 + pn3 + pn4 + · · · .
(Note that the sum on the right-hand side is finite as eventually all terms are 0.)

Proof. Let’s write n! = 1 · 2 · 3 · · · n.

j k
• All multiples of p in this product contribute a factor of p; there are np of these
multiples.
j k
• All multiples of p2 contribute an additional factor of p; there are pn2 of these.
j k
• All multiples of p3 contribute a third factor of p; there are n
p3
of these.

• ···

Adding up all of these contributions of factors of p, we get

       
n n n n
νp (n!) = + 2 + 3 + 4 + ··· .
p p p p

Theorem 2.3 (also Legendre’s Formula)

n−s (n)
p
νp (n!) = p−1 as well, where sp (n) is the sum of the digits of the base-p represen-
tation of n.

Proof. Let n = ak pk + ak−1 pk−1 + · · · + a1 p + a0 be the base-p representation of n. By

Legendre’s Formula
       
n n n n
νp (n!) = + 2 + 3 + 4 + ··· .
p p p p

But we have
 
n
= ak pk−1 + ak−1 pk−2 + · · · + a2 p + a1 ,
p
 
n
= ak pk−2 + ak−1 pk−3 + · · · + a2 ,
p2
··· ,
 
n
= ak .
pk

8
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

If we sum, we get
       
n n n n
νp (n!) = + 2 + 3 + 4 + ···
p p p p
= ak (pk−1 + pk−2 + · · · + 1) + ak−1 (pk−2 + · · · + 1) + · · · + a2 (p + 1) + a1
pk − 1 pk−1 − 1 p2 − 1 p−1
= ak + ak−1 + · · · + a2 + a1 .
p−1 p−1 p−1 p−1
n−sp (n)
Now let’s compare to p−1 . This is

1  
ak pk + ak−1 pk−1 + · · · + a1 p + a0 − ak − ak−1 − · · · − a0
p−1
which works out to
ak (pk − 1) + ak−1 (pk−1 − 1) + · · · + a2 (p2 − 1) + a1 (p − 1)
p−1
j k
and this is is identical to the expression we found by summing pni . So the two formulas
n−sp (n)
are the same: νp (n!) = p−1 .

Theorem 2.4 (Lifting the Exponent lemma)

Let p, a, b, and n be positive integers satisfying all three properties below:

• p is an odd prime,

• p does not divide a or b, and

• p divides a − b.

Then
νp (an − bn ) = νp (a − b) + νp (n).

Proof. We will induct on νp (n). Our base case is νp (n) = 0. We have to show that if
p - n, then νp (an − bn ) = νp (a − b), or alternatively that p does not divide

an − bn
= an−1 + an−2 b + · · · + bn−1 .
a−b
Let’s use the hypothesis p|a − b, from which we get a ≡ b (mod p). Then modulo p, we
have

an−1 + an−2 b + · · · + bn−1 ≡ an−1 + an−2 · a + · · · + an−1 ≡ nan−1 (mod p).

We assumed that p - n for our base case, and p - an−1 by assumption. So this is nonzero
modulo p, so the base case is complete.

For the inductive step, suppose that our lemma holds whenever νp (n) = k; we’ll prove
it for νp (n) = k + 1. Suppose that νp (n) = k + 1 and define N = np (which is an integer);
then νp (N ) = k. We wish to show

νp (an − bn ) = νp (a − b) + νp (n).

9
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

But n = pN so this is equivalent to

νp (apN − bpN ) = νp (a − b) + νp (N ) + 1.

By the inductive hypothesis we have

νp (aN − bN ) = νp (a − b) + νp (N )

so subtracting the above two equations we see it suffices to show

νp (apN − bpN ) = νp (aN − bN ) + 1

or equivalently that
apN − bpN
aN − bN
is divisible by p but not p2 . This is what we’ll prove.

Since p divides a − b, it also divides aN − bN . Let bN = M and aN = M + pk for some

integer k. By hypothesis p - M . Then

apN − bpN (M + pk)p − M p

= .
aN − bN pk
Let’s expand with the Binomial Theorem:
     
1 p p p
((M + pk)p − M p ) = M k−1 + M p−1 pk + M p−2 (pk)2 + · · · + (pk)p−1 .
pk 1 2 3

(check this!). All terms on the right-hand side are divisible by p, so the expression is
divisible by p. Now we have to check that it’s not divisible by p2 . All terms after the
second term are divisible by p2 (they contain a factor of at least p2 ). The second term
is also divisible by p2 ; it has

a factor of p, and since p is odd (this is where we 2use this
p
assumption!) p divides 2 as well. Finally, the first term is not divisible by p ; it has
a factor of p, but p - M k−1 . So the entire sum is divisible by p but not p2 , and we’re
done.

Example 2.5 (2020 AIME I # 12)

Let n be the least positive integer for which 149n − 2n is divisible by 33 · 55 · 77 . Find
the number of positive divisors of n.

Solution. Since we want large prime powers dividing numbers of the form 149n − 2n , we
can use Lifting the Exponent. Let’s try ν3 (149n − 2n ) first. We see that 3 is an odd
prime, 3|149 − 2, and 3 does not divide either of 149 and 2. So Lifting the Exponent tells
us that
ν3 (149n − 2n ) = ν3 (149 − 2) + ν3 (n) = ν3 (n) + 1.
Thus in order for 149n − 2n to be divisible by 33 we need ν3 (n) + 1 ≥ 3, so 32 |n.

Similarly, we see that 7 is odd, 7|149 − 2, and 7 does not divide either of 149 and 2, so

ν7 (149n − 2n ) = ν7 (149 − 2) + ν7 (n) = ν7 (n) + 2.

10
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

In order for 149n − 2n to be divisible by 77 we need ν7 (n) + 2 ≥ 7, so 75 |n.

Finally, we calculate ν5 (149n − 2n ), but we run into a problem: we can’t use Lifting
the Exponent because 5 - 149 − 2. We have

149n − 2n ≡ 4n − 2n ≡ 2n (2n − 1) (mod 5)

so if 5|149n − 2n then we need 5|2n − 1 (as 5 can’t divide 2n ). We can check that this
occurs precisely when n is divisible by 4. Let n = 4k; we now use Lifting the Exponent
in the following form:

ν5 (1494k − 24k ) = ν5 ((1494 )k − (24 )k )) = ν5 (1494 − 24 ) + ν5 (k) = ν5 (k) + 1

(check by hand that ν5 (1494 − 24 ) = 1). In order for 55 to divide 149n − 2n , we thus need
ν5 (k) + 1 ≥ 5, or 54 |k and thus 4 · 54 |n.

We now know that n must be divisible by 32 , 75 , and 4 · 54 , so n must be divisible by

their least common multiple,
22 · 32 · 54 · 75 .
Since n is a multiple of this number, it has at least as many factors. So the least possible
number of factors of n is simply the number of factors of this number, which is

(2 + 1)(2 + 1)(4 + 1)(5 + 1) = 270 .

Example 2.6 (ISL 1991)

Find the greatest power of 1991 which divides
1992 1990
19901991 + 19921991

Solution. We recognize this form as similar to that of LT E. The only problem is that
1991 is not prime, and we have a + instead of a −. Actually, we will see that none of
these prove to be problems.

As 1991 = 11 · 181, it suffices to find the ν11 and ν181 of the expression. We will
only show the former since the latter is analogous. What we want is to somehow apply
LTE on 1990
  2 1991 1990
S = 19901991 + 19921991
2
First, note that 19901991 +1992 ≡ 1+(−1)odd ≡ 0 (mod 11), and neither base is divisible
by 11. So, we are in the right setup to apply LTE. To deal with the +, note that both of
the exponents are odd, so we can actually write our expression as
1990
2 1991
  1990
S = 19901991 − (−1992)1991

and now normal LTE gives that

 2

ν11 (S) = 1990 + ν11 19901991 + 1992

11
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

Unfortunately, we can no longer

 use LTE on the remaining expression. However, we can
19912
split it up as 1990 + 1 + 1991, and the former has ν11 of 3 by another application
of LTE. As we are adding 1991, which has ν11 (1991) = 1, to a number divisible by 113 ,
the resulting sum is a number with ν11 = 1. Hence,
 2

ν11 (S) = 1990 + ν11 19901991 + 1992 = 1990 + 1 = 1991

The exact same logic holds for ν181 , so our answer is 1991 .

Example 2.7 (IMO 2019/4)

Find all pairs (k, n) of positive integers such that

k! = (2n − 1)(2n − 2)(2n − 4) . . . (2n − 2n−1 ).

Solution. Let’s first factor the right-hand side by pulling out as many powers of 2 out of
each factor as we can: we get
n(n−1)
k! = 2 2 (2n − 1)(2n−1 − 1) . . . (21 − 1).

From this we immediately see that v2 (k!) = n(n−1)

2 . By Legendre,
   
k k k k
v2 (k!) = + + . . . ≤ + + . . . = k.
2 4 2 4
n(n−1)
This tells us that k ≥ 2 ; in other words, k must be pretty large.

However, the presence of factors of the form 2i − 1 inspire us to try consider the νp
of other primes. Let’s try p = 3. In this case, 3|2i − 1 if and only if i is even. If i = 2j,
then by Lifting the Exponent

ν3 (2i − 1) = ν3 (4j − 1) = ν3 (4 − 1) + ν3 (j) = ν3 (j) + 1 = ν3 (i) + 1.

Therefore for all i, (

0 i odd
ν3 (2i − 1) =
ν3 (i) + 1 i even
Using the same method as the proof of Legendre’s Formula, we see that
n(n−1)
jnk jnk j n k
ν3 (2 2 (2n − 1)(2n−1 − 1) . . . (21 − 1)) = + + + ··· .
2 6 18
This is because in the product (21 − 1) · · · (2n − 1), each factor 2i − 1 with i a multiple
of 2 provides a factor of 3, each i a multiple of 6 provides a second factor of 3, each i a
multiple of 18 provides a third factor of 3, and so on. By Legendre we have
   
k k
ν3 (k!) = + + ···
3 9
so we have the equality
   
k k jnk jnk j n k
+ + ··· = + + + ··· .
3 9 2 6 18

12
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

This is pretty surprising; this tells us that k must be approximately proportional to n,

while our earlier result gave us that k is at least a quadratic in n. So let’s try to find an
upper bound on k in terms of n; maybe we’ll get a contradiction. We use the estimates
jnk jnk jnk n n n 3
+ + + ··· ≤ + + + ··· = n
2 6 18 2 6 18 4
and      
k k k k
+ + ... > > −1
3 9 3 3
This tells us that
3 k 9
n > − 1 =⇒ k < n + 3.
4 3 4
n(n−1)
But we know that k ≥ 2 ; this implies

9 n(n − 1)
n+3> .
4 2
This only holds for n ≤ 6 (check this!) so now we only have to calculate possible solutions
with n ≤ 6.

• n = 1: Plugging in, we get k! = 1, and k = 1 works.

• n = 2: k! = 6, which has k = 3 as a solution.

• n = 3: k! = 168 which clearly has no solutions.

• n = 4: k! = 26 · 32 · 5 · 7, which is impossible as v2 (k!) 6= 6 (v2 (7!) = 4 but v2 (8!) = 7).

• n = 5: k! = 210 · 32 · 5 · 7 · 31, which is impossible as 31 divides k! but not 29 (both

29 and 31 are prime).

• n = 6: k! = 215 · 34 · 5 · 72 · 31, which is impossible as 31 divides k! but not 29.

We conclude that (1, 1) and (3, 2) are the only solutions.

13
Adithya B., Brian L., William W., Daniel X. (9/9) Advanced Number Theory

§3 Problems
Problem 3.1 (2014 PUMaC NT #3). Find the number of ending zeros of 2014! in base
9. Give your answer in base 9.

Problem 3.2 (2013 PUMaC NT #2). What is the smallest positive integer n such that
2013n ends in 001 (i.e. the rightmost three digits of 2013n are 001?

Problem 3.3. Characterize all primes p which divide x2 − 3 for some x.

Problem 3.4 (2013 PUMaC NT #8). Find the number of primes p between 100 and
200 for which x11 + y 16 ≡ 2013 (mod p)

Problem 3.5 (2012 PUMaC NT #6). Let p1 = 2012 and pn = 2012pn−1 for n > 1. Find
the largest integer k such that p2012 − p2011 is divisible by 2011k .

Problem 3.6. Show that 2 is a primitive root mod 3k for any k.

Problem 3.7 (2019 OMO Fall #21). Let p and q be prime numbers such that (p−1)q−1 −1
is a positive integer that divides (2q)2p − 1. Compute the sum of all possible values of pq.

Problem 3.8. Let a, b be distinct reals such that ak − bk is an integer for any k ∈ N.
Prove that a, b are both integers.

Problem 3.9 (Folklore). Find the number of solutions to x2 + y 2 ≡ 1 (mod p) for fixed
prime p.

Problem 3.10 (USOMO 2020/3). Let p be an odd prime. An integer x is called a

quadratic non-residue if p does not divide x − t2 for any integer t.
Denote by A the set of all integers a such that 1 ≤ a < p, and both a and 4 − a are
quadratic non-residues. Calculate the remainder when the product of the elements of A
is divided by p.

Problem 3.11 (USA TST 2014/2). Let a1 , a2 , a3 , . . . be a sequence of integers, with

the property that every consecutive group of ai ’s averages to a perfect square. More
precisely, for every positive integers n and k, the quantity
an + an+1 + · · · + an+k−1
k
is always the square of an integer. Prove that the sequence must be constant (all ai are
equal to the same perfect square).

14