Olympiad Number Theory Through Challenging Problems

Olympiad Number Theory Through

Challenging Problems

Justin Stevens

THIRD EDITION

Contents

1 Divisibility 4

1.1 Euclidean and Division Algorithm . . . . . . . . . . . . . . . . . . 5

1.2 Bezout’s Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3 Fundamental Theorem of Arithmetic . . . . . . . . . . . . . . . . 22

1.4 Challenging Division Problems . . . . . . . . . . . . . . . . . . . . 27

1.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2 Modular Arithmetic 38

2.1 Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.2 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . 40

2.3 Euler’s Totient Theorem and Fermat’s Little Theorem . . . . . . . 45

2.4 The equation x

≡ −1 (mod p) . . . . . . . . . . . . . . . . . . . 57

2.5 Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3 p-adic Valuation 69

3.1 Deﬁnition and Basic Theorems . . . . . . . . . . . . . . . . . . . . 69

3.2 p-adic Valuation of Factorials . . . . . . . . . . . . . . . . . . . . 72

3.3 Lifting the Exponent . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.4 General Problems for the Reader . . . . . . . . . . . . . . . . . . 84

4 Diophantine equations 85

4.1 Bounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

4.2 The Modular Contradiction Method . . . . . . . . . . . . . . . . . 85

4.3 General Problems for the Reader . . . . . . . . . . . . . . . . . . 92

5 Problem Solving Strategies 93

5.1 Chicken Mcnuggets anyone? . . . . . . . . . . . . . . . . . . . . . 93

5.2 Vieta Jumping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

5.3 Wolstenholme’s Theorem . . . . . . . . . . . . . . . . . . . . . . . 102

5.4 Bonus Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

For Cassie Stevens.

January 30th, 2000 to July 17th, 2013

“You never know how strong you are until being strong is the only choice you have.”

Divisibility

In this chapter, we will explore divisibility, the building block of number theory.

This chapter will introduce many important concepts that will be used throughout

the rest of the book. Divisibility is an extremely fundamental concept in number

theory, and has applications including puzzles, encrypting messages, computer se-

curity, and many algorithms. An example is checking whether Universal Product

Codes (UPC) or International Standard Book Number (ISBN) codes are legiti-

mate.

Figure 1.1: An example of a UPC code.

In order for the 12 digit UPC code above to be legitimate, we order the digits

, x

, ··· , x

. The expression

+ x

+ 3x

+ x

+ 3x

+ x

+ 3x

+ x

+ 3x

+ x

+ 3x

+ x

then must be divisible by 10. We indeed verify that the above code gives

0×3+3×1+6×3+0×1+0×3+0×1+2×3+9×1+1×3+4×1+5×3+2×1 = 60,

which is divisible by 10. Therefore the above UPC code is valid.

Justin Stevens 5

1.1 Euclidean and Division Algorithm

When the concept of division is ﬁrst introduced in primary school, quotients and

remainders are used. We begin with a simple picture that should be familiar to

the reader, and we explore its relevance.

Figure 1.2: Division in primary school.

Source: CalculatorSoup

The process above used to divide 487 by 32 can be formalized through the

division algorithm.

Theorem 1.1.1 (Division Algorithm). For every integer pair a, b, there exists

distinct integer quotient and remainders, q and r, that satisfy

a = bq + r, 0 ≤ r < b

Proof. We will prove that this is true for when a and b are positive. The other

cases when one or both of a and b are negative follow very similarly. There are

two parts in this proof:

• Proving that for every pair (a, b) we can ﬁnd a corresponding quotient and

remainder.

• Proving that this quotient and remainder pair are unique.

For proving the existance of the quotient and remainder, given two integers a

and b with varying q, consider the set

{a − bq with q an integer and a − bq ≥ 0}.

1.1. Euclidean and Division Algorithm 6

By the well-ordering principle we know that this set must have a minimum, say

when q = q

. Clearly from the condition on the set, we must have a−bq

= r ≥ 0.

It now serves to prove that a −bq

= r < b. For the sake of contradiction, assume

that a − bq

≥ b. However, then

a − b(q

+ 1) ≥ 0,

therefore it also should be a member of the above set. Furthermore,

a − b(q

+ 1) < a − bq

contradicting the minimality of q

. Therefore, it is impossible for a −bq

≥ b, and

we have 0 ≤ a − bq

< b.

The second part of this proof is to show that the quotient and remainder are

unique. Assume for the sake of contradiction that a can be represented in two

ways:

a = bq

+ r

= bq

+ r

b(q

− q

) = r

− r

This implies that b | r

− r

. However,

b > r

− r

> −b

since 0 ≤ r

, r

< b. Since r

−r

is a multiple of b, we must have r

−r

= 0 =⇒

= r

and q

= q

For instance, when a = 102 and b = 18, applying the division algorithm

gives 102 = 18 × 5 + 12, therefore q = 5 and r = 12. Furthermore, note that

gcd(a, b) = gcd(102, 18) = 6 and gcd(b, r) = gcd(18, 12) = 6. This leads us to our

next interesting result.

Theorem 1.1.2 (Euclid). For natural numbers a, b, we use the division al-

gorithm to determine a quotient and remainder, q, r, such that a = bq + r.

Then gcd(a, b) = gcd(b, r).

Proof. I claim that the set of common divisors between a and b is the same as

the set of common divisors between b and r. If d is a common divisor of a and b,

then since d divides both a and b, d divides all linear combinatinations of a and

b. Therefore, d | a − bq = r, meaning that d is also a common divisor of b and r.

Conversely, if d is a common divisor of b and r, then d is a common divisor

of all linear combinations of b and r, therefore, d | bq + r = a. Hence, d is also a

common divisor of a and b.

We have established that the two sets of common divisors are equivalent,

therefore, the greatest common divisor must be equivalent.

Justin Stevens 7

Corollary 1.1.1 (Euclidean Algorithm). For two natural a, b, a > b, to ﬁnd

gcd(a, b) we use the division algorithm repeatedly

a = bq

+ r

b = r

+ r

= r

+ r

···

n−2

= r

n−1

+ r

n−1

= r

n+1

Then we have gcd(a, b) = gcd(b, r

) = gcd(r

, r

) = ··· = gcd(r

n−1

, r

) = r

Proof. For each of the equations above, simply use Euclid’s Theorem to arrive at

the equality chain.

Example 1.1.1. Find gcd(110, 490).

Solution.

490 = 110 × 4 + 50

110 = 50 × 2 + 10

50 = 10 × 5.

The division algorithm also works in Q[x], the set of polynomials with rational

coeﬃcients, and R[x], the set of all polynomials with real coeﬃcients. For the sake

of our study, we will only focus on Q[x]. If a(x) and b(x) are two polynomials,

then we can ﬁnd a unique quotient and remainder polynomial, q(x), r(x) ∈ Q[x],

such that

a(x) = b(x)q(x) + r(x), deg(r) < deg(b) or r(x) = 0.

We present a proof after an example. We can ﬁnd q(x) and r(x) using long division

for polynomials.

Example 1.1.2. Calculate q(x) and r(x) such that a(x) = b(x)q(x) + r(x)

for a(x) = x

+ 3x

+ 10 and b(x) = x

− x.

1.1. Euclidean and Division Algorithm 8

Solution. We begin by dividing the leading term of a(x) by the leading term of

b(x):

= x

. Therefore, we multiply b(x) by x

and subtract the result from

a(x):

+ 3x

+ 10 = (x

− x)(x

) + (4x

+ 10).

Now, in order to get rid of the 4x

term in the remainder, we have to divide this by

the leading term of b(x), x

= 4x. We add this to the quotient and subtract

this multiplication from the remainder in order to get rid of the cubic term:

+ 3x

+ 10 = (x

− x)(x

+ 4x) + (4x

+ 10.)

One may be tempted to stop here, however, the remainder and b(x) are both

quadratic and we need deg(r(x)) < deg(b(x)). Therefore, in order to remove the

quadratic term from the remainder, we divide this term, 4x

, by the leading term

of b(x), x

= 4. We then add this to the quotient, and subtract, in order to

get

+ 3x

+ 10 = (x

− x)(x

+ 4x + 4) + (4x + 10).

Therefore, q(x) = x

+4x+4 and r(x) = 4x+10. We verify that indeed deg(r(x)) =

1 < deg(b(x)) = 2, therefore, we are ﬁnished.

Note: The numbers will not always come out as nicely as they did in the above

expression, and we will occasionally have fractions.

Theorem 1.1.3. For two polynomials, a(x), b(x) ∈ Q[x], prove that there

exists a unique quotient and remainder polynomial, q(x) and r(x), such that

a(x) = b(x)q(x) + r(x), deg(r) < deg(b) or r(x) = 0.

Proof. For any two polynomials a(x) and b(x), we can ﬁnd q(x) and r(x) such

that a(x) = b(x)q(x) + r(x) by repeating the procedure above. The main idea is

to eliminate the leading term of r(x) repeatedly, until deg(r(x)) < deg(b(x)).

• Divide the leading term of a(x) by the leading term of b(x) in order to obtain

the polynomial q

(x). In the example above, we found q

(x) =

= x

and

(x) = 4x

+ 10. Then,

a(x) = b(x)q

(x) + r

(x).

• Divide the leading term of r

(x) by the leading term of b(x) in order to obtain

the polynomial q

(x). In the example above, we found q

(x) =

= 4x.

Then, add this quotient to q

(x) and subtract in order to ﬁnd r

(x):

a(x) = b(x) (q

(x) + q

(x)) + r

(x).

In the example above, r

(x) = 4x

+ 10.

Justin Stevens 9

• Repeat the above step of dividing the leading term of r

(x) by the leading

term of b(x) and adding this quotient to the previous quotients. So long as

deg(r

(x)) ≥ deg(b(x)), this will decrease the degree of the remainder poly-

nomial by eliminating its leading term. Stop once deg(r

(x)) < deg(b(x)),

at which point q(x) =

i=1

(x)) and r(x) = r

(x).

For the uniqueness part, note that if there exists distinct quotients q

(x),

(x) and remainders r

(x), r

(x) with deg(r

(x)) < deg(b(x)) and deg(r

(x)) <

deg(b(x)) found through the division algorithm, we will arrive at a contradiction:

a(x) = b(x)q

(x) + r

(x)

a(x) = b(x)q

(x) + r

(x)

b(x)(q

(x) − q

(x)) = r

(x) − r

(x).

However, assuming that q

(x) and q

(x) are distinct, we have

deg [b(x)(q

(x) − q

(x)] ≥ deg(b(x)).

On the other hand, since deg(r

(x)) < deg(b(x)) and deg(r

(x)) < deg(b(x)), we

know that

deg (r

(x) − r

(x)) < deg(b(x)).

Therefore, it is impossible for the left hand side of the equation above to equal

the right hand side since the degrees of the polynomials are diﬀerent.

Using the division algorithm for polynomials, we can extend Euclid’s Algo-

rithm for polynomials. Note that by convention, the greatest common divisor of

two polynomials is chosen to be the monic polynomial of highest degree that

divides both polynomials. The word monic means that the leading coeﬃcient is

1. For instance, gcd(x

− 4, x − 2) = x − 2.

Using the same reasoning we used for Euclid’s theorem above, we can arrive

at a similar theorem for polynomials.

Theorem 1.1.4. If a(x) = b(x)q(x) + r(x) with deg(r(x)) < deg(b(x)), then

gcd(a(x), b(x)) = gcd(b(x), r(x)).

Proof. We invoke the same method we used above by showing that the set of

common divisors between a(x) and b(x) is the same as the set of common divisors

between b(x) and r(x).

1.1. Euclidean and Division Algorithm 10

Extending this method, we can calculate gcd(a(x), b(x)):

a(x) = b(x)q

(x) + r

(x)

b(x) = r

(x)q

(x) + r

(x)

(x) = r

(x)q

(x) + r

(x)

···

n−1

(x) = r

(x)q

n+1

(x) + r

n+1

(x)

(x) = r

n+1

(x)q

n+2

(x).

Then we have

gcd(a(x), b(x)) = gcd(b(x), r

(x)) = gcd(r

(x), r

(x)) = ··· = r

n+1

(x),

the ﬁnal non-zero remainder.

Example 1.1.3. Find the greatest common divisor of x

+ x

− 4x

+ x + 5

and x

+ x

− 9x − 9.

Solution. Using polynomial division, we ﬁnd that

+ x

− 4x

+ x + 5 = (x

+ x

− 9x − 9)x +



+ 10x + 5



Next, we have to divide x

+ x

− 9x − 9 by 5x

+ 10x + 5. We ﬁnd that

+ x

− 9x − 9 = (5x

+ 10x + 5)



−



+ (−8x − 8) .

Finally, we divide 5x

+ 10x + 5 by −8x −8 and ﬁnd that

+ 10x + 5 = (−8x − 8)



−

(x + 1)



This is the ﬁnal non-zero remainder. However, remembering that the greatest

common divisor of two polynomials must be monic, we get rid of the

−5

term and

determine that gcd(x

+ x

− 4x

+ x + 5, x

+ x

− 9x − 9) = x + 1 .

As a quick veriﬁcation, we note that x = −1 is a root of both of the polynomials

above.

We now move onto some contest style questions that involve the Euclidan

Algorithm or the Division Algorithm.

Justin Stevens 11

Example 1.1.4 (Duke). What is the sum of all integers n such that n

+2n+2

divides n

+ 4n

+ 4n − 14?

Solution. Using long division for polynomials, we ﬁnd that

+ 4n

+ 4n − 14 = (n

+ 2n + 2)(n + 2) + (−2n − 18).

In order for n

+ 2n + 2 to divide n

+ 4n

+ 4n − 14, it must also divide the

remainder:

+ 2n + 2) | (−2n − 18).

The only way that this is possible is either when | − 2n − 18| ≥ |n

+ 2n + 2| or

when −2n−18 = 0. In the ﬁrst case, this inequality only holds when −4 ≤ n ≤ 4.

We test all n within this range, and determine that the values of n which work

are n = −4, −2, −1, 0, 1, 4. In the second case, we additionally ﬁnd that n = −9

works. Therefore, the sum is −11 .

Example 1.1.5 (AIME 1986). What is the largest positive integer n such

that n

+ 100 is divisible by n + 10?

Solution. Let

+ 100 = (n + 10)



+ an + b



+ c

= n

+ n

(10 + a) + n (b + 10a) + 10b + c.

Equating coeﬃcients yields











10 + a = 0

b + 10a = 0

10b + c = 100.

Solving this system yields a = −10, b = 100, and c = −900. Therefore, by the

Euclidean Algorithm, we get

n + 10 = gcd(n

+ 100, n + 10) = gcd(−900, n + 10) = gcd(900, n + 10)

The maximum value for n is hence n = 890 .

1.1. Euclidean and Division Algorithm 12

Example 1.1.6 (AIME 1985). The numbers in the sequence 101, 104, 109,

116, . . . are of the form a

= 100+n

, where n = 1, 2, 3, . . . . For each n, let

be the greatest common divisor of a

and a

n+1

. Find the maximum value

of d

as n ranges through the positive integers.

Solution. Since d

= gcd (100 + n

, 100 + (n + 1)

), d

must divide the diﬀerence

between these two, or d

| (100 + (n + 1)

) − (100 + n

) = 2n + 1. Therefore

= gcd(100 + n

, 100 + (n + 1)

) = gcd(n

+ 100, 2n + 1).

Since 2n + 1 will always be odd, 2 will never be a common factor, hence we can

multiply n

+ 100 by 4 without aﬀecting the greatest common divisor:

= gcd(4n

+ 400, 2n + 1) = gcd



+ 400 − (2n + 1)(2n −1), 2n + 1



= gcd (401, 2n + 1) .

Therefore, in order to maximize the value of d

, we set n = 200 to give a greatest

common divisor of 401 .

The following theorem is very useful for problems involving exponents.

Theorem 1.1.5. For natural numbers a, m, n, gcd(a

−1, a

−1) = a

gcd(m,n)

−

Outline. Note that by the Euclidean Algorithm, we have

gcd(a

− 1, a

− 1) = gcd(a

− 1 − a

m−n

− 1), a

− 1)

= gcd(a

m−n

− 1, a

− 1).

We can continue to reduce the exponents using the Euclidean Algorithm, until we

ultimately have gcd(a

− 1, a

− 1) = a

gcd(m,n)

− 1.

Example 1.1.7. Let the integers a

and b

be deﬁned by the relationship

+ b

√

2 =



1 +

√



for all integers n ≥ 1. Prove that gcd(a

, b

) = 1 for all integers n ≥ 1.

Justin Stevens 13

Solution. We use induction. For the base case, note that when n = 1, we have

= 1, b

= 1, therefore, gcd(a

, b

) = 1.

For the inductive hypothesis, we assume that it holds for n = k, therefore,

when a

√

2 =



1 +

√



, we have gcd(a

, b

) = 1. We now show that it holds

for n = k + 1. Note that

k+1

+ b

k+1



1 +

√



k+1



1 +

√



1 +

√





1 +

√



+ b

√



= (a

+ 2b

) +

√

2 (a

+ b

) .

Therefore, a

k+1

= a

+ 2b

and b

k+1

= a

+ b

. It is now left to show that

gcd(a

k+1

, b

k+1

) = 1. Note that by the Euclidean Algorithm,

gcd(a

+ 2b

, a

+ b

) = gcd(b

, a

+ b

) = gcd(b

, a

) = 1.

Therefore, by induction, we have shown that n = k =⇒ n = k + 1, and we are

done.

Example 1.1.8. If p is an odd prime, and a, b are relatively prime positive

integers, prove that

gcd



a + b,

+ b

a + b



= 1 or p.

Solution. We attempt to simplify the problem to the case when b = 1. Our goal

is to now show that

gcd(a + 1,

+ 1

a + 1

) = 1or p.

Factoring gives

+ 1

a + 1

= a

p−1

− a

p−2

+ a

p−3

− a

p−4

+ ··· − a + 1.

In order to calculate gcd(a + 1,

a+1

), we attempt to reduce the above expression

mod a + 1. Using the fact that p is an odd prime, we know that p − 1 is even,

therefore:

+ 1

a + 1

= a

p−1

− a

p−2

+ ··· + a

− a

2x−1

+ ··· − a + 1

≡ (−1)

p−1

− (−1)

p−2

+ ··· + (−1)

− (−1)

2x−1

− a + 1 (mod a + 1)

≡ 1 + 1 + ··· + 1

| {z }

p terms

≡ p (mod a + 1).

1.1. Euclidean and Division Algorithm 14

Now, by the Euclidan Algorithm, we have

gcd(a + 1,

+ 1

a + 1

) = gcd(a + 1, p).

Since p is a prime, the above expression can only be equal to 1 or p, depending on

a. We have now solved the problem for b = 1. We wish to generalize the method

to any b.

Using a similar factorization as above, we have

+ b

a + b

= a

p−1

− a

p−2

b + a

p−3

− a

p−4

+ ··· − ab

p−2

+ b

p−1

In order to invoke the Euclidean Algorithm, we wish to evaluate this expression

mod a + b. Using the fact that a ≡ −b (mod a + b) and that p − 1 is even, we

can simplify as follows:

p−1

− a

p−2

b + a

p−3

− ··· + b

p−1

≡ (−b)

p−1

− (−b)

p−2

b + (−b)

p−3

+ ···

≡ (−1)

p−1





p−1

+ b

p−1

+ ··· + b

p−1

| {z }

p terms





≡ pb

p−1

(mod a + b).

Therefore, by the Euclidean Algorithm, we arrive at

gcd



+ b

a + b

, a + b



= gcd(pb

p−1

, a + b).

Now, in the problem statement, it was given that a and b are relatively prime.

Hence, similarly, gcd(b, a + b) = 1, and we can simplify the above expression

further:

gcd(pb

p−1

, a + b) = gcd(p, a + b) = 1 or p.

Example 1.1.9 (Japan 1996). Let m, n be relatively prime positive integers.

Calculate gcd(5

+ 7

, 5

+ 7

Solution. Without Loss Or Generality (WLOG), let m > n. Note that

+ 7

= (5

+ 7

)



m−n

+ 7

m−n



− 5

m−n

− 5

m−n

We now have two cases.

Justin Stevens 15

• If m < 2n, then factor out 5

m−n

from the right hand side of the above

equation in order to get

+ 7

= (5

+ 7

)



m−n

+ 7

m−n



− 5

m−n



2n−m

+ 7

2n−m



Therefore, by the Euclidean Algorithm,

gcd(5

+ 7

, 5

+ 7

) = gcd



m−n

2n−m

+ 7

2n−m

), 5

+ 7



= gcd(5

2n−m

+ 7

2n−m

, 5

+ 7

Since 5 and 7 both do not divide 5

+ 7

• If m > 2n, then factor out 5

from the right hand side of the ﬁrst equation

in order to get

+ 7

= (5

+ 7

)



m−n

+ 7

m−n



− 5



m−2n

+ 7

m−2n



Therefore, by the Euclidean Algorithm, and using the same logic as above,

gcd(5

+ 7

, 5

+ 7

) = gcd(5

+ 7

, 5

m−2n

+ 7

m−2n

Let a

m,n

= gcd(5

+ 7

, 5

+ 7

) for simplicity. In summary from the two cases

above, if m < 2n, then a

m,n

= a

n,2n−m

. On the other hand, if m > 2n, then

m,n

= a

n,m−2n

If, for instance, we begin with m = 12 and n = 5, then the chain will go as

follows:

12,5

→ a

2,5

→ a

2,1

→ a

0,1

Note that each step in the process decreases the sum of the two values, and

furthermore, the parity of the sum remains the same at each step. Since m and

n are relatively prime and the process is invariant mod 2, if m + n is odd, trying

out a few other cases will reveal that following this chain always give

m,n

= a

0,1

= gcd(5

+ 7

, 5

+ 7

) = 2.

On the other hand, if for instance m = 13 and n = 5, then the chain will go as

follows:

13,5

→ a

3,5

→ a

3,1

→ a

1,1

If m + n is even, then we will always have

m,n

= a

1,1

= gcd(5

+ 7

, 5

+ 7

) = 12.

In conclusion,

gcd(5

+ 7

, 5

+ 7

) =

(

12 if 2 | m + n

2 if 2 - m + n

1.2. Bezout’s Identity 16

1.2 Bezout’s Identity

One of the immediate applications of the Euclidean Algorithm is Bezout’s Identity

(sometimes also called Bezout’s Lemma).

Theorem 1.2.1 (Bezout’s Identity). For a, b natural, there exist x, y ∈ Z

such that ax + by = gcd(a, b).

Proof. We present two proofs.

Euclidean Algorithm: Run the Euclidean Algorithm backwards.

gcd(a, b) = r

n−2

− r

n−1

= r

n−2

− (r

n−3

− r

n−2

n−1

) q

= r

n−2

(1 + q

n−1

) − r

n−3

)

= ···

= ax + by.

Where x and y are some combination of the quotients. The two variables run

through at every step in the equation are:

n−2

, r

n−1

) → (r

n−2

, r

n−3

) → (r

n−4

, r

n−3

) ··· → (b, r

) → (a, b).

Extremal Method: Consider the set

S = {ax + by > 0 with x, y integers}.

By the well-ordering principle, this set must have a minimum, say d = min(S).

Since d is a member of the set, there exists integers x

and y

such that d =

+ by

. Now, we go about proving that d = gcd(a, b). To begin, we must show

that d is a divisor of both a. By the division algorithm, say

a = dq + r, 0 ≤ r < d.

Substituting d = ax

+ by

into the above equation gives

a = d(ax

+ by

) + r =⇒ r = a(1 − dx

) + b(−dy

Therefore, if r is positive, then r is a member of the set S above. However, we

know that 0 ≤ r < d, contradicting the minimality of d. Hence, we must have

r = 0 =⇒ d | a. Similarly, we can show that d | b. We have now shown that d is

a common divisor of a and b.

It is now left to show that d is the greatest common divisor of a and b. Indeed,

let d

be another common divisor of a and b. Therefore, d

also divides any linear

combination of a and b, speciﬁcally d

| ax

+ by

= d. Therefore, every common

divisor of a and b divides d, therefore, d = gcd(a, b) and we are ﬁnished.

Justin Stevens 17

Example 1.2.1. Express 5 as a linear combination of 45 and 65.

Solution. We use the Euclidean Algorithm in reverse. Using the Euclidean Algo-

rithm on 45 and 65, we arrive at

65 = 45 × 1 + 20

45 = 20 × 2 + 5

20 = 5 × 4.

Therefore, we run the process in reverse to arrive at

5 = 45 − 20 × 2

= 45 − (65 − 45 × 1)2

= 45 × 3 − 65 × 2.

Example 1.2.2. Express 10 as a linear combination of 110 and 380.

Solution. We again, use the Euclidean Algorithm to arrive at

380 = 110 × 3 + 50

110 = 50 × 2 + 10

50 = 10 × 5.

Now, running the Euclidean Algorithm in reverse gives us

10 = 110 − 50 × 2

= 110 − (380 − 110 × 3) × 2

= 7 × 110 − 2 × 380.

Example 1.2.3. Express 3 as a linear combination of 1011 and 11, 202.

Solution. We use the Euclidean Algorithm to arrive at

11202 = 1011 × 11 + 81

1011 = 81 × 12 + 39

81 = 39 × 2 + 3

39 = 3 × 13.

1.2. Bezout’s Identity 18

Now, runing the Euclidean Algorithm in reverse, we arrive at:

3 = 81 − 39 × 2

= 81 − (1011 − 81 × 12) × 2 = 81 × 25 − 1011 × 2

= (11202 − 1011 × 11) × 25 − 1011 × 2 = 11202 × 25 − 1011 ×277.

Furthermore, Bezout’s identity holds for any number of variables.

Theorem 1.2.2 (General Bezout’s Identity). For integers a

, a

, ··· , a

, there

exists integers x

, x

, ··· , x

such that

+ a

+ ··· + a

i=1

= gcd(a

, a

, ··· , a

Proof. Again, two methods can be used (either the Extremal Method or using

induction). We show the induction proof for moving from 2 to 3 variables and

challenge the reader to attempt using both methods to prove the general case.

For 3 variables, we use 2 variable Bezout’s twice:

gcd(a

, a

) = gcd (a

, gcd(a

, a

))

= a

+ c gcd(a

, a

)

= a

+ c (x

+ x

) = a

+ a

(cx

) + a

(cx

)

Theorem 1.2.3 (Euclid’s Lemma). If a | bc and gcd(a, b) = 1, prove that

a | c.

Proof. By Bezout’s identity, gcd(a, b) = 1 implies that there exist x, y such that

ax + by = 1.

Next, multiply this equation by c to arrive at

c(ax) + c(by) = c.

Finally, since a | ac and a | bc, we have a | ac(x) + bc(y) = c.

Justin Stevens 19

Bezout’s identity for polynomials works the same exact way as it does for

integers. Assume f(x), g(x) ∈ Z[x], then using Euclid’s Algorithm, we can ﬁnd

u(x), v(x) ∈ Q[x] such that

f(x)u(x) + g(x)v(x) = gcd(f(x), g(x)).

Here is an example for clarity.

Example 1.2.4. Find polynomials u, v ∈ Q[x] such that

− 1)u(x) + (x

− 1)v(x) = (x − 1).

Solution. First oﬀ, we use Euclid’s Algorithm on x

− 1, x

− 1. Notice that

− 1 = (x

− 1)x

+ x

− 1

− 1 = x(x

− 1) + x − 1

− 1 = (x − 1)(x

+ x + 1).

Therefore,

x − 1 = x

− 1 − x(x

− 1)

= x

− 1 − x



− 1 −



− 1







− 1



+ x



− 1



− x



− 1





− 1



+ 1



− x



− 1



Therefore u(x) = x

+ 1, v(x) = −x.

The following example illustrates how to approach problems when the numbers

are not as nice as above.

Example 1.2.5. Find u, v ∈ Q[x] such that (2x

−1)u(x)+(3x

−1)v(x) = 1.

Solution. By the division algorithm, note that

− 1 =



− 1









x − 1



Now, for the second step of the Euclidean Algorithm, we have to divide 2x

− 1

x −1. We start by dividing the leading terms:

x. Therefore, we have

− 1 =



x − 1







x − 1



1.2. Bezout’s Identity 20

Next, we divide the leading term of r

(x),

x, by the leading term of the dividend,

. We add this to the quotient and get

− 1 =



x − 1



x +



−

Running these steps in reverse, we see that

−



− 1



−



x +



x − 1





− 1



−



x +





− 1



−



− 1









− 1





1 −



x +



−





− 1





−



x +





− 1





x + 1





− 1





−



x +



Finally, we have to multiply both sides by −9 in order to give 1 on the left hand

side:

1 = (2x

− 1)(−18x

− 12x − 9) + (3x

− 1)(12x + 8).

Therefore u(x) = −18x

− 12x − 9 and v(x) = 12x + 8 .

Example 1.2.6. Suppose you have a 5 litre jug and a 7 litre jug. We can

perform any of the following moves:

• Fill a jug completely with water.

• Transfer water from one jug to another, stopping if the other jug is ﬁlled.

• Empty a jug of water.

The goal is to end up with one jug having exactly 1 litre of water. How do we

do this?

Solution. Note that at every stage, the jugs will contain a linear combination of 5

and 7 litres of water. We ﬁnd that 1 = 5 ×3 + 7 ×(−2), therefore, we want to ﬁll

the jug with 5 litres 3 times, and empty the one with 7 litres twice. In order to

keep track of how much water we have in each step, we use an ordered pair (a, b),

where a is the amount in the 5 litre jug and b is the amount in the 7 litre jug:

(0, 0) → (5, 0) → (0, 5) → (5, 5) → (3, 7) → (3, 0) → (0, 3) → (5, 3) → (1, 7).

Justin Stevens 21

Example 1.2.7. Use Bezout’s identity to prove the theorem in Section 1.1,

gcd(a

− 1, a

− 1) = a

gcd(m,n)

− 1.

Proof. Let d = gcd(a

− 1, a

− 1). Therefore, a

≡ 1 (mod d) and a

≡ 1

(mod d). By Bezout’s identity, let gcd(m, n) = mx + ny. Using the above two

relations, we also have

gcd(m,n)

≡ a

mx+ny

≡ a

≡ 1 (mod d).

Therefore, d | a

gcd(m,n)

− 1. We now show that a

gcd(m,n)

− 1 | d.

Since gcd(m, n) | m, we have

gcd(m,n)

− 1 | a

− 1.

We can similarly show that a

gcd(m,n)

−1 | a

−1. Since a

gcd(m,n)

−1 divides both

− 1 and a

− 1, it must also divide their greatest common divisor:

gcd(m,n)

− 1 | gcd(a

− 1, a

− 1) = d.

Since d | a

gcd(m,n)

−1 and a

gcd(m,n)

−1 | d, we must have d = gcd(a

−1, a

−1) =

gcd(m,n)

− 1.

Example 1.2.8. (Putnam 2000) Prove that the expression

gcd(m, n)





is an integer for all pairs of integers n ≥ m ≥ 1.

Solution. By Bezout’s identity, there exist integers a and b such gcd(m, n) =

am + bn. Next, notice that

gcd(m, n)





am + bn









+ b





We must now prove that





is an integer. Note that







m!(n − m)!



(n − 1)!

(m − 1)!(n − m)!



n − 1

m − 1



Therefore,

gcd(m, n)





= a



m − 1

n − 1



+ b





which is clearly an integer.

1.3. Fundamental Theorem of Arithmetic 22

1.3 Fundamental Theorem of Arithmetic

Next, we use Bezout’s Identity to prove the Fundamental Theorem of Arithmetic,

which, as the name suggests, is incredibly fundamental to mathematics.

Theorem 1.3.1. (Fundamental Theorem of Arithmetic) Every integer n ≥ 2

has a unique prime factorization.

Proof. We divide this problem into two parts. The ﬁrst part is showing that

every integer n ≥ 2 has a prime factorization. To do this, we use strong induction

on n. To establish the base case, note that n = 2, 3, 4 all have a unique prime

factorization. For the inductive hypothesis, assume that every integer n < k has

a prime factorization, and we show that n = k then has a prime factorization.

If k is prime, then it has a prime factorization (itself). On the other hand, if k

is composite, then let p be a prime divisor of k. We can now write k = p





. We

know that

can be written as the product of primes by the inductive hypothesis

(

< k), therefore k = p





similarly can be.

The second part of the problem is to prove uniqueness, for which we again

use induction. The base cases of n = 2, 3, 4 all have unique prime factorizations.

Assume that every integer n < k has a unique prime factorization, and we prove

that n = k then must have a unique prime factorization. For the sake of contra-

diction, let k have two distinct prime factorizations, where repeated primes are

allowed in the products:

n = p

···p

= q

···q

Note that we must have p

| q

···q

. By Euclid’s Lemma (from Section 1.1),

we know that we must have p

| q

for some integer m with 1 ≤ m ≤ j. Therefore

= q

since they are primes. Now, we can cancel this from both sides of the

expression in order to get

= p

···p

= q

···q

m−1

m+1

···q

By the inductive hypothesis,

has a unique prime factorization, therefore

the two products above contain the same exact primes with the same multiplicity

(although they may be slightly rearranged). Similarly, since p

= q

, the two

initial products are exactly identical, and n has a unique prime factorization.

Justin Stevens 23

Theorem 1.3.2. Let the prime factorizations of two integers a, b be

a = p

···p

b = p

···p

The exponents above can be zero and the p

’s are distinct. Then,

gcd(a, b) = p

min(e

)

min(e

)

···p

min(e

)

and lcm[a, b] = p

max(e

)

max(e

)

···p

max(e

)

Corollary 1.3.1. For a, b ∈ Z

, gcd(a, b) lcm[a, b] = ab.

We now present several problems involving prime factorization, beginning with

some more computational problems, and ending with some challenging olympiad

problems.

Example 1.3.1. (Classic) The cells in a jail are numbered from 1 to 100

and their doors are activated from a central button. The activation opens a

closed door and closes an open door. Starting with all the doors closed the

button is pressed 100 times. When it is pressed the k-th time the doors that

are multiples of k are activated. Which doors will be open at the end?

Solution. In order for a door to be open at the end, it will have to have been

activated an odd number of times (since it initially was closed). For a given door

d, it will be activated only when the button is pressed the k-th time if and only if

k is a divisor of d. Therefore, we desire to ﬁnd numbers that have an odd number

of divisors.

Using the prime factorization of a in the theorem above, we calculate the

number of prime divisors a has. In order to do this, we construct an arbitrary

divisor of a. For each prime p

in the prime factorization of a, we have e

+ 1

choices for the exponent. Therefore, we can see that the number of divisors of a

is simply

τ(a) =

i=1

+ 1) .

For this number to be odd, each exponent e

must be even, implying that a

must be a perfect square. Therefore, the doors which are open at the end are

simply the doors that are perfect squares, namely 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

1.3. Fundamental Theorem of Arithmetic 24

Example 1.3.2 (AIME 1998). For how many values of k is 12

the least

common multiple of 6

, 8

, and k?

Solution. We ﬁnd the prime factorizations of these numbers. We have 12

·3

, 6

= 2

·3

and 8

= 2

. Let k = 2

. Since lcm[2

·3

, 2

, k] = 2

·3

we must have k

= 12. On the other hand, since the second term above has 24

2’s, there are no limitations on k

other than 0 ≤ k

≤ 24, giving 25 possibilities.

Therefore, there are 25 · 1 = 25 possible values of k.

Example 1.3.3 (AIME 1987). Let [r, s] denote the least common multiple of

positive integers r and s. Find the number of ordered triples a, b, c such that

[a, b] = 1000, [b, c] = 2000, [c, a] = 2000.

Solution. Notice that 1000 = 2

× 5

, 2000 = 2

× 5

. Since we are working with

least common multiples, set

a = 2

, b = 2

, c = 2

If a

or b

were at least 4, then 2

would divide [a, b], therefore, this is impossible.

On the other hand, [b, c] and [c, a] both are multiples of 2

, therefore, we have

= 4. Amongst a

and b

, at least one of them must be 3 in order to have

| [a, b]. Therefore, we have the pairs

, b

, c

) = (0, 3, 4), (1, 3, 4), (2, 3, 4), (3, 3, 4), (3, 2, 4), (3, 1, 4), (3, 0, 4).

for 7 in total.

Now, for the power of 5, in order to have all three of the least common multiples

above be divisible by 5

, at least two of the set a

, b

, c

must be 3. This gives us

a total of 4 cases, when all of the numbers are 3 or when two of them are, and

the third is less than 3:

, b

, c

) = (3, 3, 3), (3, 3, x), (3, x, 3), (x, 3, 3).

We know that 0 ≤ x < 3, therefore, there are 3 possibilities for each of the x’s

above. Therefore, there are a total of 3 × 3 + 1 = 10 possibilities for the powers

of 5.

In conclusion, there is a total of 7 × 10 = 70 ordered triples a, b, c which

work.

Justin Stevens 25

Example 1.3.4 (Canada 1970). Given the polynomial

f(x) = x

+ a

n−1

+ a

n−2

+ ··· + a

n−1

x + a

with integer coeﬃcients a

, a

, . . . , a

, and given also that there exist four

distinct integers a, b, c and d such that

f(a) = f(b) = f(c) = f(d) = 5,

show that there is no integer k such that f(k) = 8.

Solution. Set g(x) = f(x) − 5. Since a, b, c, d are all roots of g(x), we must have

g(x) = (x − a) (x − b) (x −c) (x − d) h(x)

for some h(x) ∈ Z[x]. Let k be an integer such that f(k) = 8, giving g(k) =

f(k) − 5 = 3. Using the factorization above, we ﬁnd that

3 = (k −a) (k − b) (k − c) (k − d) h(x).

By the Fundamental Theorem of Arithmetic, we can only express 3 as the product

of at most three distinct integers (−3, 1, −1). Since k − a, k − b, k − c, k − d

are all distinct integers, we have too many terms in the product, leading to a

contradiction.

Example 1.3.5. Let a, b, c be positive integers. If gcd(a, b, c)lcm[a, b, c] = abc,

prove that gcd(a, b) = gcd(b, c) = gcd(c, a) = 1.

Solution. Consider a prime p that divides into at least one of a, b, c. I will show

that it can divide into only one of the set a, b, c, hence, proving that a, b, c are

pairwise relatively prime. We use the notation p

|| a to denote p

fully dividing

a, meaning that p

| a, however, p

k+1

- a. Another form of this notation that will

be seen later is v

(a) = k.

For integers a

, b

, c

, let p

|| a, p

|| b, p

|| c. By the deﬁnition of greatest

common divisor, p

min(a

)

|| gcd(a, b, c). Similarly, by the deﬁnition of least

common multiple, p

max(a

)

|| lcm[a, b, c]. We assume WLOG that a

≥ b

≥ c

;

hence min(a

, b

, c

) = c

and max(a

, b

, c

) = a

Therefore, the power of p which divides into gcd(a, b, c)lcm[a, b, c] is max(a

, b

, c

min(a

, b

, c

) = a

+ c

. Therefore,

|| gcd(a, b, c)lcm[a, b, c].

1.3. Fundamental Theorem of Arithmetic 26

Note that, on the other hand,

|| abc.

In order for this to be true, we must then have

+ c

= a

+ b

+ c

=⇒ b

= 0.

By the WLOG assumption above, we had a

≥ b

≥ c

. Since b

= 0, we must

then have c

= 0. Therefore, p can only divide one of the set a, b, c. The same

argument holds for any prime p that divides into the set {a, b, c}, therefore, a, b, c

are pairwise relatively prime.

Example 1.3.6 (USAMO 1973). Show that the cube roots of three distinct

prime numbers cannot be three terms (not necessarily consecutive) of an arith-

metic progression.

Solution. Assume for the sake of contradiction that three such distinct primes

exist, and let these primes be

√

. By deﬁnition of an arithmetic

sequence, set

√

= a,

√

= a + kd,

√

= a + md, m > k.

Subtracting gives:

√

−

√

= kd

√

−

√

= md.

Multiply the ﬁrst equation by m and the second by k in order to equate the two

√

− m

√

= k

√

− k

√

= mkd.

Rearraging this equation, we get

√

− k

√

= (m − k)

√

. (1.1)

Now, cubing this gives Using this equation and some rearrangement, we get:

− 3







+ 3







− k

= (m − k)

Moving the integer terms over to the RHS and factoring out 3







from

the LHS gives





i

− mp



= (m − k)

− m

+ k

Justin Stevens 27

From Equation 1.1, we know that kp

− mp

= (k − m)

√

. Therefore, substi-

tuting this into the above equation gives





(k − m)

√



= (m − k)

− m

+ k

Leaving only the cube roots on the left hand side gives

√

(m − k)

− m

+ k

3mk(k − m)

. (1.2)

Lemma. If

√

a is rational, then

√

a is an integer.

Proof. Set

√

a =

where the fraction is in lowest terms, therefore gcd(x, y) = 1.

We desire to show that we must have the denominator, y, equal to 1. Cubing this

equation and rearranging gives ay

= x

. Assume for the sake of contradiction

that y has a prime divisor, say p. If p | y then we must also have p | x from

= x

. However, this contradicts gcd(x, y) = 1. Therefore, it is impossible for

y to have any prime divisors, and we must have y = 1, implying that

√

a is an

integer.

Since the RHS of Equation 1.2 is a rational number, the Lemma above implies

that

√

must be an integer. From the Fundamental Theorem of Arithmetic,

this means that we must have p

= p

, contradiction.

1.4 Challenging Division Problems

In this section, I will show some of my favorite problems involving divisibility

and concepts from this chapter. I highly recommend attempting these problems

before reading the provided solutions.

These ﬁrst few examples illustrate how to use inequalities and fractions with

divisibility.

Example 1.4.1 (St. Petersburg 1996). Find all positive integers n such that

n−1

+ 5

n−1

| 3

+ 5

Solution. Notice that 3

n−1

+ 5

n−1

also divides 5 times itself:

n−1

+ 5

n−1

| 5



n−1

+ 5

n−1



= 3

+ 2 · 3

n−1

+ 5

1.4. Challenging Division Problems 28

Subtracting the given equation from this gives us

n−1

+ 5

n−1



+ 2 · 3

n−1

+ 5



− (3

+ 5

)

=⇒ 3

n−1

+ 5

n−1

| 2 · 3

n−1

However, for n > 1, we have 3

n−1

> 2·3

n−1

, leading to the above divisibility

being impossible. We then check that n = 1 is the only possible solution.

Example 1.4.2 (APMO 2002). Find all pairs of positive integers a, b such

that

+ b

− a

and

+ a

− b

are both integers.

Solution. For these conditions to be met, we must have

+ b ≥ b

− a b

+ a ≥ a

− b

(a + b) (a − b + 1) ≥ 0 (a + b) (b − a + 1) ≥ 0

a ≥ b − 1 b ≥ a − 1.

For these two inequalities to be satisﬁed, we must have a = b, b −1, b + 1. Notice

that the cases a = b − 1 and a = b + 1 are identical because we can simply ﬂip

the pair after we ﬁnish. Therefore, we consider the below two cases.

Case 1: a = b.

The expression

+ a

− a

must then be an integer. Simplifying this expression

shows that

+ a

− a

a + 1

a − 1

= 1 +

a − 1

Therefore, a−1 must be a divisor of 2, giving a = 2, 3. This results in the solution

pairs (a, b) = (2, 2), (3, 3).

Case 2: a = b − 1.

Note that

+ b = (b − 1)

+ b = b

− b + 1 = b

− a.

Therefore,

+ b

− a

= 1. The only expression which we then have to check whether

it is an integer is

+ a

− b

. Expanding and simplifying shows:

+ a

− b

+ b − 1

(b − 1)

− b

+ b − 1

− 3b + 1

= 1 +

4b − 2

− 3b + 1

Justin Stevens 29

For b ≥ 7, however, we then have b

− 3b + 1 > 4b − 2, meaning that the above

expression cannot be an integer. We therefore test b ∈ {1, 2, 3, 4, 5, 6} to see when

4b−2

−3b+1

is an integer, and ﬁnd that b = 1, 2, 3 all work. However, when b = 1, this

gives a non-positive value for a, therefore, we discard this solution. Therefore, the

two solution pairs we ﬁnd are (a, b) = (1, 2), (2, 3).

The a = b + 1 case gives the permutations of the two above solutions, for a

complete solution set of (a, b) = (2, 2), (3, 3), (1, 2), (2, 3), (2, 1), (3, 2).

Example 1.4.3. (1998 IMO) Determine all pairs (x, y) of positive integers

such that x

y + x + y is divisible by xy

+ y + 7.

Solution. We desire to simplify the above expression by cancelling some terms.

If we multiply the divisor xy

+ y + 7 by x and subtract this from y times the

dividend, then the x

and xy terms will cancel in the subtraction:

+ y + 7 | y



y + x + y



− x



+ y + 7



= y

− 7x.

If y

− 7x > 0, then in order to have the above divisibility, we must have

+ y + 7 ≤ y

− 7x. However, for positive integers x, y, the LHS of the

inequality is a lot larger, leading to this being impossible.

If y

− 7x = 0, then we have the solution pair (x, y) = (7m

, 7m) for positive

integer m.

Finally, if y

− 7x < 0, then 7x − y

> 0. For a positive integer d, let

7x − y

+ y + 7

= d =⇒ 7x − y

= d(xy

+ y + 7).

Expanding and isolating all the terms involving x to the LHS of the equation,

we ﬁnd that

x(7 − dy

) = y

+ dy + 7d.

Now, notice that the RHS must be positive since y and d are both positive

integers. Therefore, similarly, the LHS must also be positive. However, for y ≥ 3,

we have 7 − dy

< 0, therefore, we test y = 1, 2.

If y = 1, then we have

x(7 − d) = 8d + 1

=⇒ x =

8d + 1

7 − d

= −8 +

7 − d

The divisors of 57 are 1, 3, 19, 57. We want both x and d to be positive integers,

therefore, we have 7 − d = 1, 3. In the ﬁrst case, we have x = −8 +

= 49. In

1.4. Challenging Division Problems 30

the second case, we have x = −8 +

= 11. Therefore, we arrive at the solutions

(x, y) = (11, 1), (49, 1).

If y = 2, then we have

x(7 − 4d) = 9d + 4.

However, since the LHS must be positive, we are forced to have d = 1, giving

x =

9 · 1 + 4

7 − 4 · 1

, which is not an integer.

The solutions are hence (x, y) = (11, 1), (49, 1), (7m

, 7m) .

Example 1.4.4. (1992 IMO) Find all integers a, b, c with 1 < a < b < c such

that

(a − 1)(b − 1)(c − 1)

divides abc − 1.

Solution. In order to simplify the above expression, we set a = x+1, b = y +1, c =

y + 1. We then arrive at

xyz | (x + 1) (y + 1) (z + 1) − 1.

Expanding and simplifying give

xyz | (xyz + xy + xz + yz + x + y + z + 1) − 1

xyz | xy + xz + yz + x + y + z.

Finally, dividing the two expressions, we see that we must have

∈ Z.

From 1 < a < b < c, we get 1 ≤ x < y < z. The maximum possible value of

this sum is when x = 1, y = 2, z = 3:

S =

≤

1 × 2

1 × 3

2 × 3

= 2

Therefore, S ∈ {1, 2}. Furthermore, if we have x, y, z ≥ 3, then the maximum

possible value of S would be when (x, y, z) = (3, 4, 5), giving S =

≤ 1. There-

fore, it is impossible for S to be an integer since it is less than 1. Since x is the

smallest, we must have x ∈ {1, 2}. We have now greatly limited the possibilities

for S and x, and we can do casework in order to ﬁnd the corresponding values of

y and z.

Justin Stevens 31

Case 1: If x = 1, then we get

= 1 or 2.

In the case that S = 1, note that the LHS is greater than 1, therefore this is

impossible. When S = 2, multiplying by yz and simplifying gives

2y + 2z + 1 = yz =⇒ (y −2)(z − 2) = 5 =⇒ (y, z) = (3, 7)

In conclusion, we have the solution (x, y, z) = (1, 3, 7).

Case 2: If x = 2, then we get

= 1 or 2.

When S = 1, multiplying by 2yz and simplifying gives

3y + 3z + 2 = yz =⇒ (y −3)(z − 3) = 11 =⇒ (y, z) = (4, 14).

When S = 2, multiplying by 2yz and simplifying gives

3y + 3z + 2 = 3yz.

However, since 2 is not a multiple of 3, this is impossible. In conclusion, we

have the solution (x, y, z) = (2, 4, 14).

In summary of the cases above, we found two solutions:

(x, y, z) = (2, 4, 14), (1, 3, 7) =⇒ (a, b, c) = (3, 5, 15), (2, 4, 8).

We conclude this chapter with a few interesting problems involving prime

numbers and divisibility.

Example 1.4.5 (Iran 2005). Let n, p > 1 be positive integers and p be prime.

Given that n | p − 1 and p | n

− 1, prove that 4p − 3 is a perfect square.

Solution. Since n | p − 1, let p − 1 = kn for some positive integer k, therefore

p = kn + 1. This satisﬁes the ﬁrst condition of the requirement. We now look at

the second condition, which is p | n

− 1 = (n − 1)(n

+ n + 1). Note that since

p = kn + 1, we have p ≥ n −1, and because p is a prime, gcd(p, n − 1) = 1:

p | (n − 1)(n

+ n + 1) =⇒ p = kn + 1 | n

+ n + 1.

1.4. Challenging Division Problems 32

In order for this to be true, kn + 1 ≤ n

+ n + 1 =⇒ k ≤ n + 1. Since

+ n + 1 | k(n

+ n + 1), we also have

p = kn + 1 | kn

+ kn + k

=⇒ kn + 1 | kn

+ kn + k −n(kn + 1) = kn + k − n.

Similarly, to have this divisibility, kn + k −n ≥ kn + 1 =⇒ k ≥ n + 1. However,

above we found that k ≤ n + 1, therefore, k = n + 1. Substituting this in for p

gives p = (n + 1)n + 1 = n

+ n + 1, giving

4p − 3 = 4n

+ 4n + 4 − 3 = 4n

+ 4n + 1 = (2n + 1)

Example 1.4.6 (David M. Bloom). Let p be a prime with p > 5, and let

S = {p −n

|n ∈ N, n

< p}. Prove that S contains two elements a and b such

that a|b and 1 < a < b.

Solution. We try a few examples. For p = 23, S = {23 −1

, 23 −2

, 23 −3

, 23 −

} = {22, 19, 14, 7} and 7 | 14. For p = 19, S = {18, 15, 10, 3} and 3 | 18. For

p = 29, S = {28, 25, 20, 13, 4} and 4 | 20. It appears as if the smallest element of

S always divides another element.

Let k be so that k

< p < (k + 1)

. Therefore, p − k

is the smallest element

in S.

If p − k

= 1, note that since p > 5, it must be an odd prime, therefore, k is

even. Then, set a = p − (k − 1)

= 2k and b = p − 1

= k

. Since k is even, we

have a = 2k | b = k

In the case that p − k

6= 1, then let a = p − k

. Note that since k

≡ p

(mod a), we also have (k −a)

≡ (a − k)

≡ p (mod a). Therefore,

a | p − (k − a)

and a | p − (a − k)

It is now left to show that p −(k −a)

or p −(a −k)

∈ S, depending on the sign

of k − a.

If k > a, then let n = k − a ∈ N. Furthermore, since k

< p, we also have

= (k −a)

< k

< p, therefore b = p − (k − a)

∈ S and we have a | b.

If k = a, then we would have k = p−k

=⇒ p = k(k +1), which is impossible

for prime p > 5.

Finally, if k < a, then let n = a − k ∈ N. Furthermore, we have

a = p − k

< (k + 1)

− k

= 2k + 1 =⇒ a ≤ 2k.

Justin Stevens 33

However, if a = 2k, then we would have a = p−k

=⇒ p = k

+2k = k(k+2),

which is impossible for prime p > 5. Therefore, a < 2k and we have a − k < k.

Since k

< p, we also have n

= (a −k)

< k

< p, therefore, b = p −(a −k)

∈ S

and a | b.

Example 1.4.7. (Iran 1998) Suppose that a and b are natural numbers such

that

p =

2a − b

2a + b

is a prime number. Find all possible values of a, b, p.

Solution. If b is odd then 2a−b is odd so henceforth

2a−b

2a+b

cannot be an integer.

We consider two cases: b = 4k, or b = 2m where m is odd.

Case 1: b = 4k.

p = k

2a − 4k

2a + 4k

= k

a − 2k

a + 2k





a − 2k

a + 2k

a + 2p

k = k

a − 2k

a(k

− p

) = 2k(k

+ p

)

a =

2k(k

+ p

)

− p

We know that a must be an integer. Consider the cases p | k and p - k. The

ﬁrst case gives us k = dp for some positive integer d. Substituting this into the

above equation gives

a =

2dp(d

+ p

)

− p

2dp(d

+ 1)

− 1

We have gcd(d, d

− 1) = 1 therefore we must have

2p(d

+ 1)

− 1

= 2p



1 +

− 1



∈ Z

=⇒

− 1

∈ Z.

When d is even we must have (d

− 1) | p =⇒ p = d

− 1 = (d − 1)(d + 1)

since p is a prime. The only way for this to be possible is when d − 1 = 1, which

1.4. Challenging Division Problems 34

gives the solution (p, d) = (3, 2). Substituting this into the formulas above gives

(a, b, p) = (20, 24, 3).

When d is odd, we ﬁnd that (p, d) = (2, 3). Substituting this into the formulas

above gives (a, b, p) = (15, 24, 2).

Now when p - k, a =

2k(k

+ p

)

− p

must again be an integer. From the Eu-

clidean Algorithm, gcd(k, k

− p

) = gcd(k, p

) = 1, therefore

gcd(2k(k

+ p

), k

− p

) = gcd(2k

+ 2p

, k

− p

)

= gcd(2k

+ 2p

− 2(k

− p

), k

− p

)

= gcd(4p

, k

− p

By similar logic to above, gcd(p

, k

− p

) = gcd(p

, k

) = 1, therefore we can

further simplify:

gcd(4p

, k

− p

) = gcd(4, k

− p

Since k

− p

is the denominator of the fraction, we desire for the above ex-

pression to be equal to k

−p

. However, this gives











− p

= 1

− p

= 2

− p

= 4

of which none

gives any positive solution for p.

In conclusion, we have found that (a, b, p) = (20, 24, 3), (15, 24, 2).

Case 2: b = 2m where m is odd.

p =

2a − 2m

2a + 2m

Using similar algebraic manipulation as before, we ﬁnd that this is equivalent

a =

m(m

+ 4p

)

− 4p

We again have two cases to consider: p | m and p - m. The ﬁrst case p | m.

Let m = dp for some integer d. We arrive at

a =

pd(p

+ 4p

)

− 4)

pd(d

+ 4)

− 4

Remembering that since m is odd, d must also be odd, we have gcd(d, d

− 4) =

gcd(d, 4) = 1 and gcd(d

+ 4, d

−4) = gcd(8, d

−4) = 1. Therefore, in order for

a to be an integer,

− 4

must be an integer. Since the only divisors of a prime

are 1 and itself,

− 4 = (d − 2)(d + 2) = p.

Justin Stevens 35

This is only possible when d = 3 which gives p = 5. Substituting these values into

the above expressions gives the solution triple (a, b, p) = (39, 30, 5).

On the other hand, when p - m, gcd(m, m

− 4p

) = gcd(m, 4p

) = 1 since m

is odd. Therefore, since a must be an integer, we have

+ 4p

− 4p

= 1 +

− 4p

∈ Z.

Furthermore, we also have gcd(m

− 4p

, 8p

) = 1 since m is odd, therefore we

must have m

− 4p

| 8. This gives the cases:











− 4p

= 1

− 4p

= 2

− 4p

= 4

− 4p

= 8.

which yields no

valid integer solutions.

In conclusion, the three solutions are (a, b, p) = (39, 30, 5), (20, 24, 3), (15, 24, 2).

1.5 Problems

1.1. Calculate gcd(301, 603).

1.2. Calculate gcd(153, 289).

1.3. Calculate gcd(133, 189).

1.4. The product of the greatest common factor and least common multiple of

two positive numbers is 384. If one number is 8 more than the other number,

compute the sum of two numbers.

1.5. Use long division on a(x) = x

+ 4x

+ 2x and b(x) = x

+ 2x

in order to

calculate q(x) and r(x).

1.6. [AHSME 1990] For how many integers N between 1 and 1990 is the improper

fraction

N+4

not in lowest terms?

1.7. [IMO 1959] Prove that for natural n the fraction

21n+4

14n+3

is irreducible.

1.8. Use the Euclidean Algorithm for polynomials to calculate gcd(x

−x

, x

−x).

1.9. [AHSME 1988] If a and b are integers such that x

− x − 1 is a factor of

+ bx

+ 1, then what are the values of a and b?

1.5. Problems 36

1.10. Prove that any two consecutive terms in the Fibonacci sequence are rela-

tively prime.

1.11. Prove that the sum and product of two positive relatively prime integers

are themselves relatively prime.

1.12. Find integers x, y such that 5x + 97y = 1.

1.13. Find integers x, y such that 1110x + 1011y = 3.

1.14. Prove that there are no integers x, y such that 1691x + 1349y = 1.

1.15. Find all integers x, y such that 5x + 13y = 1.

1.16. Let n ≥ 2 and k be positive integers. Prove that (n − 1)

| (n

− 1) if and

only if (n − 1) | k.

1.17. Prove that

√

2 is irrational.

1.18. Prove that log

(2) is irrational.

1.19. [AIME 2008] How many positive integer divisors of 2004

2004

are divisible

by exactly 2004 positive integers?

1.20. Find polynomials u, v ∈ Q[x] such that

(5x

− 1)u(x) + (x

− 1)v(x) = 1.

1.21. Find u, v ∈ Z[x] such that (x

− 1)u(x) + (x

− 1)v(x) = (x − 1).

1.22. For relatively prime naturals m, n, do there exist polynomials u, v ∈ Q[x]

such that (x

− 1)u(x) + (x

− 1)v(x) = (x − 1)?

1.23. For positive integers a, b, n > 1, prove that

− b

- a

+ b

1.24. [HMMT] Compute gcd(2002 + 2, 2002

+ 2, 2002

+ 2, ···).

1.25. Let n be a positive integer. Calculuate

gcd (n! + 1, (n + 1)!) .

Note: This problem requires Wilson’s theorem.

1.26. [PUMAC 2013] The greatest common divisor of 2

−2 and 2

−2 can

be expressed in the form 2

− 2. Calculuate x.

Justin Stevens 37

1.27. [Poland 2004] Find all natural n > 1 for which value of the sum 2

+ 3

··· + n

equals p

where p is prime and k is natural.

1.28. Prove that if m 6= n, then

gcd(a

+ 1, a

+ 1) =

(

1 if a is even

2 if a is odd

1.29. Prove that for positive integers a, b > 2 we cannot have 2

− 1 | 2

+ 1.

1.30. [USAMO 2007] Prove that for every nonnegative integer n, the number

+ 1 is the product of at least 2n + 3 (not necessarily distinct) primes.

Modular Arithmetic

2.1 Inverses

Deﬁnition 2.1.1. We say that the inverse of a number a modulo m when a and

m are relatively prime is the number b such that ab ≡ 1 (mod m).

Example. The inverse of 3 mod 4 is 3 because 3·3 = 9 ≡ 1 (mod 4). The inverse

of 3 mod 5 is 2 because 3 · 2 = 6 ≡ 1 (mod 5).

The following theorem is incredibly important and helps us to prove Euler’s

Totient Theorem and the existence of an inverse. Make sure that you understand

the proof and theorem as we will be using it down the road.

Theorem 2.1.1. Let a and m be relatively prime positive integers. Let

the set of positive integers relatively prime to m and less than m be R =

, a

, ··· , a

φ(m)

}. Prove that S = {aa

, aa

, ··· , aa

φ(m)

} is the same as

R when reduced mod m.

Proof. Notice that every element of S is relatively prime to m. Also R and S

have the same number of elements. Because of this, if we can prove that no two

elements of S are congruent mod m we would be done. However

≡ aa

(mod m) =⇒ a(a

− a

) ≡ 0 (mod m) =⇒ a

≡ a

(mod m)

which happens only when x = y therefore the elements of S are distinct mod m

and we are done.

Theorem 2.1.2. When gcd(a, m) = 1, a always has a distinct inverse mod

Justin Stevens 39

Proof. We notice that 1 ∈ R where we deﬁne R = {a

, a

, ··· , a

φ(m)

} to be the

same as above. This must be the same mod m as an element in {aa

, aa

, ··· , aa

φ(m)

}

by Theorem 1 henceforth there exists some a

such that aa

≡ 1 (mod m).

Corollary 2.1.1. The equation ax ≡ b (mod m) always has a solution when

gcd(a, m) = 1.

Proof. Set x ≡ a

−1

b (mod m).

Example. Find the inverse of 9 mod 82.

Solution. Notice that 9 · 9 ≡ −1 (mod 82) therefore 9 · (−9) ≡ 1 (mod 82). The

inverse of 9 mod 82 is hence 82 − 9 = 73.

Example 2.1.1. Let m and n be positive integers posessing the following

property: the equation

gcd(11k − 1, m) = gcd(11k −1, n)

holds for all positive integers k. Prove that m = 11

n for some integer r.

Solution. Deﬁne v

(a) to be the number of times that the prime p occurs in the

prime factorization of a

. The given statement is equivalent to proving that

(m) = v

(n) when p 6= 11 is a prime. To prove this, assume on the contrary

that WLOG we have

(m) > v

(n)

Write m = p

b, n = p

d where b and d are relatively prime to p. We have a > c.

By Theorem 2 we know that there exists a solution for k such that 11k ≡ 1

(mod p

). However, we now have

| gcd(11k − 1, m)

but p

| gcd(11k −1, n) implies that p

| n contradicting a > c. We are done.

We explore this function more in depth later

2.2. Chinese Remainder Theorem 40

Example 2.1.2. Let a and b be two relatively prime positive integers, and

consider the arithmetic progression a, a + b, a + 2b, a + 3b, ···. Prove that

there are inﬁnitely many pairwise relatively prime terms in the arithmetic

progression.

Solution. We use induction. The base case is trivial. Assume that we have a set

with m elements that are all relatively prime. Let this set be S = {a + k

b, a +

b, ··· , a + k

b}. Let the set {p

, p

, ··· , p

} be the set of all distinct prime

divisors of elements of S. I claim that we can construct a new element. Let

a + xb ≡ 1 (mod p

· p

· ···p

)

We know that there exists a solution in x to this equation which we let be x =

m+1

. Since gcd (a + k

m+1

b, a + k

b) = 1, we have constructed a set with size

m + 1 and we are done.

2.2 Chinese Remainder Theorem

Theorem 2.2.1 (Chinese Remainder Theorem). The system of linear con-

gruences











x ≡ a

(mod b

x ≡ a

(mod b

···

x ≡ a

(mod b

where b

, b

, ··· , b

are pairwise relatively prime (aka gcd(b

, b

) = 1 iﬀ i 6= j)

has one distinct solution for x modulo b

···b

Proof. We use induction. I start with proving that for the case

(

x ≡ a

(mod b

x ≡ a

(mod b

there exists a unique solution mod b

. To do so, consider the set of numbers

S = {kb

+ a

, 0 ≤ k ≤ b

− 1}.

By Corollary 1 it follows that the equation kb

+ a

≡ a

(mod b

) has a distinct

solution in k. We have shown the unique existence of a solution to the above

system of linear congruences.

Justin Stevens 41

Assume there is a solution for n = k and I prove that there is a solution for

n = k + 1. Let the following equation have solution x ≡ z (mod b

···b

) by

the inductive hypothesis:











x ≡ a

(mod b

)

x ≡ a

(mod b

)

···

x ≡ a

(mod b

Therefore to ﬁnd the solutions to the k + 1 congruences it is the same as ﬁnding

the solution to

(

x ≡ z (mod b

···b

)

x ≡ a

k+1

(mod b

k+1

For this we can use the exact same work we used to prove the base case

along with noting that from gcd(b

k+1

, b

) = 1 for i ∈ {1, 2, ··· , k}, we have

gcd(b

k+1

, b

···b

) = 1.

Example 2.2.1. Find the solution to the linear congruence

(

x ≡ 3 (mod 5),

x ≡ 4 (mod 11).

Solution. Notice that we may write x in the form 5k + 3 and 11m + 4.

x = 5k + 3 = 11m + 4

Taking this equation mod 5 we arrive at 11m + 4 ≡ 3 (mod 5) =⇒ m ≡ −1

(mod 5). We substitute m = 5m

−1 to give us x = 11(5m

−1) + 4 = 55m

−7.

Therefore x ≡ 48 (mod 55) which means x = 55k + 48

for some integer k.

Example 2.2.2 (AIME II 2012). For a positive integer p, deﬁne the positive

integer n to be p-safe if n diﬀers in absolute value by more than 2 from all mul-

tiples of p. For example, the set of 10-safe numbers is 3, 4, 5, 6, 7, 13, 14, 15, 16, 17, 23, ....

Find the number of positive integers less than or equal to 10, 000 which are

simultaneously 7-safe, 11-safe, and 13-safe.

2.2. Chinese Remainder Theorem 42

Solution. We notice that if x is 7-safe, 11-safe, and 13-safe then we must have











x ≡ 3, 4 (mod 7)

x ≡ 3, 4, 5, 6, 7, 8 (mod 11)

x ≡ 3, 4, 5, 6, 7, 8, 9, 10 (mod 13)

By Chinese Remainder Solution this renders solutions mod 1001. We have 2

choices for the value of x mod 7, 6 choices for the value of x mod 11 and 8 choices

for the value of x mod 13. Therefore, we have 2 · 6 · 8 = 96 total solutions mod

1001.

We consider the number of solutions in the set

{1, 2, ··· , 1001}, {1002, ··· , 2002}, {2003, ··· , 3003}, ··· , {9009, ··· , 10010}.

From above there are 96 ·10 = 960 total solutions. However we must subtract the

solutions in the set {10, 001; 10, 002; ··· ; 10, 010}.

We notice that only x = 10, 006 and x = 10, 007 satisfy x ≡ 3, 4 (mod 7).

10, 006 10, 007

(mod 7) 3 4

(mod 11) 7 8

(mod 13) 9 10

These values are arrived from noting that 10, 006 ≡ −4 (mod 7 · 11 · 13) and

10, 007 ≡ −3 (mod 7 ·11 ·13). Therefore x = 10, 006 and x = 10, 007 are the two

values we must subtract oﬀ.

In conclusion we have 960 − 2 = 958 solutions.

Example 2.2.3. Consider a number line consisting of all positive integers

greater than 7. A hole punch traverses the number line, starting frrom 7 and

working its way up. It checks each positive integer n and punches it if and

only if





is divisible by 12. (Here





(n−k)!k!

.) As the hole punch checks

more and more numbers, the fraction of checked numbers that are punched

approaches a limiting number ρ. If ρ can be written in the form

, where m

and n are positive integers, ﬁnd m + n.

Solution. Note that





(n − 7)!7!

n(n − 1)(n − 2)(n − 3)(n − 4)(n − 5)(n − 6)

· 3

· 5 · 7

Justin Stevens 43

In order for this to be divisible by 12 = 2

· 3, the numerator must be divisible

by 2

·3

. (We don’t care about the 5 or the 7; by the Pigeonhole Principle these

will be canceled out by factors in the numerator anyway.) Therefore we wish to

ﬁnd all values of n such that

· 3

|n(n − 1)(n − 2)(n − 3)(n − 4)(n − 5)(n − 6).

We start by focusing on the factors of 3, as these are easiest to deal with. By

the Pigeonhole Principle, the expression must be divisible by 3

= 9. Now, if

n ≡ 0, 1, 2, 3, 4, 5, or 6 (mod 9), one of these seven integers will be a multiple of

9 as well as a multiple of 3, and so in this case the expression is divisible by 27.

(Another possibility is if the numbers n, n − 3, and n − 6 are all divisible by 3,

but it is easy to see that this case has already been accounted for.)

Now, we have to determine when the product is divisible by 2

. If n is even,

then each of n, n −2, n −4, n −6 is divisible by 2, and in addition exactly two of

those numbers must be divisible by 4. Therefore the divisibility is sure. Otherwise,

n is odd, and n − 1, n − 3, n − 5 are divisible by 2.

• If n − 3 is the only number divisible by 4, then in order for the product to

be divisible by 2

it must also be divisible by 16. Therefore n ≡ 3 (mod 16)

in this case.

• If n −1 and n −5 are both divisible by 4, then in order for the product to be

divisible by 2

one of these numbers must also be divisible by 8. Therefore

n ≡ 1, 5 (mod 8) =⇒ n ≡ 1, 5, 9, 13 (mod 16).

Pooling all our information together, we see that





is divisible by 12 iﬀ n

is such that

(

n ≡ 0, 1, 2, 3, 4, 5, 6 (mod 9),

n ≡ 0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14 (mod 16).

There are 7 possibilities modulo 9 and 13 possibilities modulo 16, so by CRT there

exist 7 × 13 = 91 solutions modulo 9 × 16 = 144. Therefore, as more and more

numbers n are checked, the probability that





is divisible by 12 approaches

144

. The requested answer is 91 + 144 = 235 .

2.2. Chinese Remainder Theorem 44

Example 2.2.4 (Austin Shapiro). Call a lattice point “visible” if the greatest

common divisor of its coordinates is 1. Prove that there exists a 100 × 100

square on the board none of whose points are visible.

Solution. Let the points on the grid be of the form

(x, y) = (a + m, b + n), 99 ≥ m, n ≥ 0.

We are going to use the Chinese Remainder Theorem to have every single

term have a common divisor among the two coordinates. For the remainder of the

problem assume that the sequence {p

} is a sequence of distinct prime numbers.

Let a ≡ 0

mod

100

i=1

. Then let











b ≡ 0 (mod p

)

b + 1 ≡ 0 (mod p

)

···

b + 99 ≡ 0 (mod p

100

We ﬁnd that repeating this process with letting a + 1 ≡ 0

mod

200

i=101

and

deﬁning similarly











b ≡ 0 (mod p

101

)

b + 1 ≡ 0 (mod p

102

)

···

b + 99 ≡ 0 (mod p

200

)

gives us the following:











a ≡ 0

mod

100

i=1

a + 1 ≡ 0

mod

200

i=101

···

a + 99 ≡ 0

mod

10000

i=9901

and











b ≡ 0

mod

i=0

100i+1

b + 1 ≡ 0

mod

i=0

100i+2

···

b + 99 ≡ 0

mod

100

i=1

100i

Justin Stevens 45

This notation looks quite intimidating; take a moment to realize what it is

saying. It is letting each a + k be divisible by 100 distinct primes, then letting b

be divisible by the ﬁrst of these primes, b + 1 be divisible by the second of these

primes and so forth. This is precisely what we did in our ﬁrst two examples above.

By CRT we know that a solution exists, therefore we have proven the existence

of a 100 × 100 grid.

Motivation. This problem requires a great deal of insight. When I solved this

problem, my ﬁrst step was to think about completing a 1 × 100 square as we did

above. Then you have to think of how to extend this method to a 2 ×100 square

and then generalizing the method all the way up to a 100 × 100 square. Notice

that our construction is not special for 100, we can generalize this method to a

x × x square!

2.3 Euler’s Totient Theorem and Fermat’s Little

Theorem

Theorem 2.3.1 (Euler’s Totient Theorem). For a relatively prime to m, we

have a

φ(m)

≡ 1 (mod m).

Proof. Using Theorem 2.1.1 the sets {a

, a

, ··· , a

φ(m)

} and {aa

, aa

, ··· , aa

φ(m)

}

are the same mod m. Therefore, the products of each set must be the same mod

φ(m)

···a

φ(m)

≡ a

···a

φ(m)

(mod m) =⇒ a

φ(m)

≡ 1 (mod m).

Corollary 2.3.1 (Fermat’s Little Theorem). For a relatively prime to a prime

p, we have a

p−1

≡ 1 (mod p).

Proof. Trivial.

Example. Find 2

(mod 33).

We do this problem in two diﬀerent ways.

2.3. Euler’s Totient Theorem and Fermat’s Little Theorem 46

Solution. Notice that we may not directly use Fermats Little Theorem because

33 is not prime. However, we may use Fermats little theorem in a neat way:

Notice that 2

≡ 1 (mod 3) and 2

≡ 1 (mod 11) from Fermats Little Theorem.

We will ﬁnd 2

(mod 3) and 2

(mod 11) then combine the results to ﬁnd 2

(mod 33).

≡ (2

)

≡ 1

≡ 1 (mod 3),

≡



)





≡ 2

≡ 256 ≡ 3 (mod 11).

Let x = 2

. Therefore, x ≡ 1 (mod 3) and x ≡ 3 (mod 11). Inspection gives us

x ≡ 25 (mod 33).

Solution. We will use Euler’s Totient Theorem. Notice that φ(33) = 33(1−

)(1−

) = 20, therefore 2

≡ 1 (mod 33). Now, notice that

x = 2

= (2

)

−2

≡ 4

−1

(mod 33).

Therefore, since x ≡ 4

−1

(mod 33) =⇒ 4x ≡ 1 (mod 33). Using quick analysis,

x ≡ 25 (mod 33) solves this hence 2

≡ 25 (mod 33). Our answer matches our

answer above so we feel fairly conﬁdent in it.

Example 2.3.1 (Brilliant.org). For how many integer values of i, 1 ≤ i ≤

1000, does there exist an integer j, 1 ≤ j ≤ 1000, such that i is a divisor of

− 1?

Solution. For i even it is clear that we can’t have i|(2

−1). For i odd let j = φ(i)

to give us 2

φ(i)

− 1 ≡ 0 (mod i). Since φ(i) < 1000 it follows that for i odd there

is always a value of j and hence the answer is

1000

= 500 .

Example 2.3.2 (Brilliant.org). How many prime numbers p are there such

that 29

+ 1 is a multiple of p?

Solution. When p = 29 we have 29 - 29

+ 1. Therefore we have gcd(p, 29) = 1.

By Fermat’s Little Theorem

+ 1 ≡ 29 + 1 ≡ 0 (mod p).

Therefore it follows that p | 30 and hence p = 2, 3, 5 for a total of 3 numbers.

Justin Stevens 47

Example 2.3.3 (AIME 1983). Let a

= 6

+ 8

. Determine the remainder

on dividing a

by 49.

Solution. Notice that φ(49) = 42. Therefore, 6

≡ 1 (mod 49) and 8

≡ 1

(mod 49).

+ 8

≡ (6

)(6

−1

) + (8

)(8

−1

) (mod 49)

≡ 6

−1

+ 8

−1

(mod 49)

Via expanding both sides out we ﬁnd:

−1

+ 8

−1

≡ (6 + 8)6

−1

(mod 49)

≡ (14) 48

−1

(mod 49)

≡ (14) (−1) (mod 49)

≡ 35 (mod 49)

Tip 2.3.1. When dealing with a

φn−1

(mod n) it is often easier to compute a

−1

(mod n) then to compute a

φn−1

(mod n) directly.

Example 2.3.4 (All Russian MO 2000). Evaluate the sum













+ ··· +



1000



Solution. Note that we have

≡

(

1 (mod 3) when x is even,

2 (mod 3) when x is odd.

Therefore

1000

n=0





= 0 +

500

n=1



2n−1







500

n=1



2n−1

− 2

− 1



500

n=1

2n−1

+ 2

− 1) =

1000

n=1

− 500 =

1001

− 2) − 500 .

2.3. Euler’s Totient Theorem and Fermat’s Little Theorem 48

Tip 2.3.2. When working with ﬂoor functions, try to ﬁnd a way to make the

fractions turn into integers.

Example 2.3.5 (HMMT 2009). Find the last two digits of 1032

1032

. Express

your answer as a two-digit number.

Solution.

(

1032

≡ 0 (mod 4)

1032

≡ 7

1032

≡ (−1)

516

≡ 1 (mod 25)

=⇒ 1032

1032

≡ 76

(mod 100)

Tip 2.3.3. When we have to calculuate a (mod 100) it is often more helpful to

ﬁnd

(

a (mod 4)

a (mod 25)

and then using the Chinese Remainder Theorem to ﬁnd a

(mod 100). We can do similar methods when dealing with a (mod 1000).

Example 2.3.6 (Senior Hanoi Open MO 2006). Calculuate the last three

digits of 2005

+ 2005

+ ··· + 2005

2006

Solution. By reducing the expression modulo 1000, it remains to ﬁnd the last

three digits of the somewhat-less-daunting expression

2005

+ 2005

+ ··· + 2005

2006

≡ 5

+ 5

+ ··· + 5

2006

(mod 1000).

Notice that 5

+ 5

+ ··· + 5

2006

≡ 0 (mod 125).

Next, we want 5

+ 5

+ ··· + 5

2006

(mod 8). Notice that 5

≡ 1 (mod 8)

and therefore 5

≡ 1 (mod 8) and 5

2k+1

≡ 5 (mod 8). Henceforth

+ 5

+ ··· + 5

2006

≡

1996

(1 + 5) ≡ 4 (mod 8)

Therefore 5

+ 5

+ ··· + 5

2006

≡ 500 (mod 1000).

Justin Stevens 49

Example 2.3.7 (PuMAC

). Calculuate the last 3 digits of 2008

2007

2006

···

Princeton University Mathematics Competition

Solution. To begin we notice 2008

2007

2006

···

≡ 0 (mod 8).

Next, we notice via Euler’s Totient:

2008

2007

2006

···

≡ 2008

2007

2006

···

(mod φ(125))

(mod 125)

Now notice

2007

2006

···

≡ 7

2006

···

(mod 100) ≡ 1 (mod 100)

since 7

≡ 1 (mod 100). Therefore 2008

2007

2006

···

≡ 2008

≡ 8 (mod 125).

Henceforth

2008

2007

2006

···

≡ 8 (mod 1000).

Tip 2.3.4. When a and n are relatively prime we have

≡ a

b (mod φ(n))

(mod n)

It then suﬃces to calculuate b (mod φ(n)).

Example 2.3.8 (PuMAC 2008). Deﬁne f(x) = x

. Find the last two digits

of f(17) + f(18) + f(19) + f(20).

Solution. We compute each individual term seperately.

• f(20) ≡ 0 (mod 100)

•

(

f(19) ≡ (−1)

≡ −1[4]

f(19) ≡ 19

(mod φ25)

≡ 19

−1

≡ 4[25]

=⇒ f(19) ≡ 79[100]

•

(

≡ 0[4]

≡ 1[25] =⇒ 18

≡ 1 (mod 25)

=⇒ f(18) ≡ 76[100]

2.3. Euler’s Totient Theorem and Fermat’s Little Theorem 50

•

f(17) ≡ 1 (mod 4)











f(17) ≡ 17

(mod 20)

(mod 25)

φ(20) = 8 =⇒ 17

≡ 17 (mod 20)

f(17) ≡ 17

(mod 25)

≡ (17

)

≡ ((14)

)

≡



(−4)



≡ 16

≡ 6 (mod 25)

=⇒ f(17) ≡ (17) (6) ≡ 2 (mod 25)

−→ f(17) ≡ 77 (mod 100)

Therefore

f(17) + f(18) + f (19) + f(20) ≡ 77 + 76 + 79 + 0 ≡ 232 ≡ 32 (mod 100)

Example 2.3.9 (AoPS). Show that for c ∈ Z and a prime p, the congruence

≡ c (mod p) has a solution.

Solution. Suppose that x satisﬁes the congruences

(

x ≡ c (mod p),

x ≡ 1 (mod p −1).

Then by Fermat’s Little Theorem we have

≡ x

x (mod p−1)

≡ x

≡ c (mod p).

All that remains is to show that there actually exists a number with these proper-

ties, but since (p, p−1) = 1, there must exist such a solution by Chinese Remainder

Theorem. 

Justin Stevens 51

Example 2.3.10 (Balkan). Let n be a positive integer with n ≥ 3. Show that

− n

is divisible by 1989.

Solution. Note that 1989 = 3

×13×17. Therefore, we handle each case separately.

• First, we prove that

≡ n

(mod 9)

for all n. If 3|n then we are done. Otherwise, since φ(9) = 6, the problem

reduces itself to proving that

≡ n

(mod 6)

This is not hard to show true. It is obvious that n

≡ n

(mod 2), and

(as long as n is not divisible by 3) showing the congruence modulo 3 is

equivalent to showing that n

≡ n (mod φ(3)), which is trivial since n and

have the same parity.

• Next, we prove that

≡ n

(mod 13)

This is a very similar process. If 13|n we are done; otherwise, the problem

is equivalent to showing that

≡ n

(mod 12)

We have already shown that these two expressions are congruent modulo

3, and showing that they are equivalent modulo 4 is equivalent to showing

that n

≡ n (mod φ(4)), and since φ(4) = 2 this is trivial. Therefore they

are congruent modulo 12 and this second case is complete.

• Finally, we prove that

≡ n

(mod 17)

, which once again is quite similar. If 17|n we are done, otherwise the

problem reduces itself to proving that

≡ n

(mod 16)

If 2|n in this case then the problem is solved; otherwise, it reduces itself

again to proving that n

≡ n (mod 8). This is the most diﬃcult case of this

2.3. Euler’s Totient Theorem and Fermat’s Little Theorem 52

problem, but it is still not hard. Note that since n is odd, n

≡ 1 (mod 8).

Therefore n

n−1

≡ 1 (mod 8) and n

≡ n (mod 8). Through this, we have

covered all possibilities, and so we are done with the third case.

We have shown that the two quantities are equivalent modulo 9, 13, and 17, so by

Chinese Remainder Theorem they must be equivalent modulo 9 ×13 ×17 = 1989,

as desired.

Example 2.3.11 (Canada 2003). Find the last 3 digits of 2003

2002

2001

Solution. Taking the number directly mod 1000 doesn’t give much (try it out and

see!) Therefore we are going to do it in two diﬀerent parts: Find the value mod

8 and ﬁnd the value mod 125 then combine the two values. First oﬀ note that

φ(8) = 4 and φ(125) = 100.

(

2003

2002

2001

≡ 3

2002

2001

(mod 8)

2002

2001

≡ 0 (mod φ(8))

=⇒ 3

2002

2001

≡ 3

≡ 1 (mod 8)

Now notice that 2003

2002

2001

≡ 3

2002

2001

(mod 125). To ﬁnd this we must ﬁnd

2002

2001

≡ 2

2001

(mod φ(125) = 100). We split this up into ﬁnding 2

2001

(mod 4)

and 2

2001

(mod 25):

(

2001

≡ 0 (mod 4)

2001

= 2

)

100

= 2

φ(25)

)

100

≡ 2 (mod 25)

=⇒ x ≡ 52 (mod 100)

Therefore we have 3

2002

2001

≡ 3

(mod 125). It is a tedious work but as this

problem appeared on a mathematical olympiad stage it should be done by hand.

≡ (3

)

) (mod 125)

≡ (−7)

(9) (mod 125) ≡ (49)

(9) (mod 125)

≡





(49)(9) (mod 125) ≡ (26

)(49)(9) (mod 125)

≡ (51)(49)(9) (mod 125) ≡ −9 ≡ 116 (mod 125)

Let x = 2003

2002

2001

(

x ≡ 1 (mod 8) =⇒ x = 8k + 1

x ≡ 116 (mod 125) =⇒ x = 125m + 116

Justin Stevens 53

Therefore, x = 125m + 116 = 8k + 1. Taking mod 8 of this equation we arrive

at 5m + 4 ≡ 1 (mod 8) or 5m ≡ 5 (mod 8) hence m ≡ 1 (mod 8). Henceforth

we have m = 8m

+ 1 or

x = 125(8m

+ 1) + 116 = 1000m

+ 241.

Therefore x ≡ 241 (mod 1000).

Tips. These are very helpful tips for dealing with problems involving expo-

nentation.

• When dealing with a

φn−1

(mod n) it is often easier to compute a

−1

(mod n)

then to compute a

φn−1

(mod n) directly.

• When we have to calculuate a (mod 100) it is often more helpful to ﬁnd

(

a (mod 4)

a (mod 25)

and then using the Chinese Remainder Theorem to ﬁnd a

(mod 100). We can do similar methods when dealing with a (mod 1000).

• When a and n are relatively prime we have

≡ a

b (mod φ(n))

(mod n)

It then suﬃces to calculuate b (mod φ(n)).

Example 2.3.12 (Balkan MO 1999). Let p > 2 be a prime number such that

3|(p − 2). Let

S = {y

− x

− 1|0 ≤ x, y ≤ p −1 ∩ x, y ∈ Z}

Prove that there are at most p elements of S divisible by p.

Solution. Despite the intimidiating notation, all that it is saying for S is that S

is the set of y

− x

− 1 when x and y are positive integers and 0 ≤ x, y ≤ p − 1

(essentially meaning x, y are reduced mod p).

Lemma. When a 6≡ b (mod p) we have a

6≡ b

(mod p).

2.3. Euler’s Totient Theorem and Fermat’s Little Theorem 54

Proof. Assuming to the contrary that for some a, b with a 6≡ b (mod p) we have

≡ b

(mod p). Since

p−2

is an integer raising both sides to that power gives us

)

p−2

≡ (b

)

p−2

(mod p)

p−2

≡ b

p−2

(mod p)

−1

≡ b

−1

(mod p)

a ≡ b (mod p)

With the last step following from the fact that every element has a unique

inverse mod p.

We now count how many ways we have y

−x

−1 ≡ 0 (mod p). Notice that

we must have x

≡ y

−1 (mod p). For each value of y there is at most one value

of x which corresponds to it. Since there are a total of p values of y there is at

most p pairs (x, y) such that y

− x

− 1 ≡ 0 (mod p).

Motivation. The motivation behind this solution was trying a simple case. When

p = 5 we notice that we have:

x (mod 5) x

(mod 5) x

(mod 5)

0 0 0

1 1 1

2 4 3

3 4 2

4 1 4

We need for the diﬀerence of an x

and y

to be 1. We notice that for each

value of x

there can only be one value of y

that goes along with it. Then we go

on to prove the general case.

Example 2.3.13 (USAMO 1991). Show that, for any ﬁxed integer n ≥ 1,

the sequence

2, 2

, 2

, . . . (mod n)

is eventually constant.

[The tower of exponents is deﬁned by a

= 2, a

i+1

= 2

. Also a

(mod n)

means the remainder which results from dividing a

by n.]

Justin Stevens 55

Solution. First, deﬁne the recursive sequence {a

} such that a

= 2 and a

i+1

= 2

for each i ≥ 1. It is clear that the sequence of a

’s maps to the sequence of integers

described in the original problem.

In addition, for each positive integer n, consider a recursive sequence {b

} such

that b

is the largest odd integer that evenly divides n and for each i ≥ 1, b

i+1

is the largest odd integer that evenly divides φ(b

). For example, when n = 62,

= 31, b

= 15, and b

= 1. Note that it is obvious that at some positive integer

i we have b

= 1, since the sequence of b

’s is monotonically decreasing.

Now consider a term of the sequence of towers of 2 with a suﬃcient number

of 2s, say a

. We wish to have for all suﬃciently large m:

m+1

≡ a

(mod n)

Note that we can write n in the form 2

, where k

is a nonnegative integer. By

Chinese Remainder Theorem, it suﬃces to check

(

m+1

≡ a

(mod 2

m+1

≡ a

(mod b

Since m is suﬃciently large, a

m+1

≡ a

≡ 0 (mod 2

). All that remains is to

check if a

m+1

≡ a

(mod b

). By Euler’s Totient Theorem, since gcd(2, b

) = 1

we have 2

φ(b

)

≡ 1 (mod b

), so

= 2

m−1

≡ 2

m−1

mod φ(b

)

(mod b

Therefore, we now want a

≡ a

m−1

(mod φ(b

)). Since φ(b

) = 2

we must

check

(

≡ a

m−1

(mod 2

≡ a

m−1

(mod b

Because m is suﬃciently large

≡ a

m−1

≡ 0 (mod 2

and so it suﬃces to check if a

≡ a

m−1

(mod b

). We can continue this method

all the way down to the integer i such that b

= 1 at which point the equation

≡ a

m−1

≡ 0 (mod b

) is clearly true so hence we have arrived at a true

statement. Therefore a

m+1

≡ a

(mod n) for suﬃciently large m and we are

done.

Motivation. The choice for the b

sequence may be a bit confusing therefore I try

my best to explain the motivation here.

2.3. Euler’s Totient Theorem and Fermat’s Little Theorem 56

When wishing to prove a

m+1

≡ a

(mod n) by Euler’s Totient we try to see

if we can have a

≡ a

m−1

(mod φ(n)). If φ(n) was odd then we could continue

on this method until we have φ (φ(···φ(n))) = 1 at which point since we have

chosen m to be suﬃciently large we would get a true statement.

Thankfully we patch the arugment by considering the largest odd divisor of

φ(n) and using Chinese Remainder Theorem. That is where the idea for the b

sequence comes from.

Example 2.3.14 (ISL 2005 N6). Let a, b be positive integers such that b

+ n

is a multiple of a

+ n for all positive integers n. Prove that a = b.

Solution. I desire to prove that for all primes b ≡ a (mod p). Fix a to be a

constant value and I construct a way to ﬁnd the corresponding value of n which

tells us that b ≡ a (mod p). Notice that the following conditions are the same:

+ n) | (b

+ n) ⇐⇒ (a

+ n) | (b

− a

We set

(

n ≡ −a (mod p),

n ≡ 1 (mod p − 1).

Because n ≡ 1 (mod p − 1) we have a

≡ a (mod p) via Fermat’s Little

Theorem. Also, because n ≡ −a (mod p) we have p|(a

+ n) =⇒ p|(b

− a

)

However, b

≡ b (mod p) and a

≡ a (mod p) from n ≡ 1 (mod p − 1) therefore

b ≡ a (mod p) for all primes p hence b = a.

Motivation. The way I solved this problem was consider the case when a = 1 at

ﬁrst. In this case we must have (n + 1) | b

+n. We desire to prove b ≡ 1 (mod p)

for all primes p. We notice that b

+ n ≡ b

−1 (mod n + 1). If we have p|(n + 1)

and b

≡ b (mod p) then we would be done. The condition b

≡ b (mod p) is

satisﬁed when n ≡ 1 (mod p − 1) and the condition p|(n + 1) is satisﬁed when

n ≡ −1 (mod p). Therefore we have proven the problem for a = 1.

2.3.1 Problems for the reader

2.1. (2003 Polish) Find all polynomials W with integer coeﬃcients satisfying the

following condition: for every natural number n, 2

− 1 is divisible by W (n).

Justin Stevens 57

2.4 The equation x

≡ −1 (mod p)

Theorem 2.4.1 (Wilson’s). (p − 1)! ≡ −1 (mod p) for all odd primes p.

Proof. Start out with looking at a few examples. p = 5 gives 4! = 24 ≡ −1

(mod 5). However, another way to compute this is to note that

4! = (1 · 4)(2 ·3) ≡ (4)(6) ≡ (1)(4) ≡ −1 (mod 5).

We test p = 7 which gives 6! = 720 = 7(103) − 1 ≡ −1 (mod 7) Also,

6! = (1 · 6) (2 ·4) (3 · 5) = (6)(8)(15) ≡ (6)(1)(1) ≡ −1 (mod 7).

What we are doing is we are looking at all the terms in (p −1)! and ﬁnding groups

of two that multiply to 1 mod p. I will now prove that this method always works.

Notice that for all x ∈ {2, 3, ··· , p − 2} there exists a y 6= x such that xy ≡ 1

(mod p) by Theorem 2 and the fact that x

≡ 1 (mod p) ⇐⇒ x ≡ ±1 (mod p).

Since p is odd, we can pair the inverses oﬀ into

p−3

pairs. Let these pairs be

, y

), (x

, y

), (x

, y

), ···(x

(p−3)/2

, y

(p−3)/2

)

Therefore,

(p − 1)! ≡ (1)(p − 1) (x

) (x

) ···



(p−3)/2



(mod p)

≡ (1)(p − 1) (1) (1) ···(1) (mod p)

≡ −1 (mod p).

Theorem 2.4.2. There exists an x with x

≡ −1 (mod p) if and only if p ≡ 1

(mod 4).

Proof. For the ﬁrst part notice that

≡ −1 (mod p)

)

p−1

≡ (−1)

p−1

(mod p)

p−1

≡ (−1)

p−1

(mod p)

1 ≡ (−1)

p−1

(mod p),

which happens only when p ≡ 1 (mod 4).

2.4. The equation x

≡ −1 (mod p) 58

Now proving the other way requires a bit more work. First oﬀ from Wilsons

theorem (p − 1)! ≡ −1 (mod p). Therefore our equation turns into x

≡ (p − 1)!

(mod p). Notice that

(p − 1)! = [(1)(p −1)] [(2)(p − 2)] ···



p − 1



p + 1



≡ [(1)(−1)] [(2)(−2)]



p − 1



−

p − 1



(mod p)

≡ (−1)

p−1



p − 1





(mod p)

≡



p − 1





(mod p)

Therefore x =



p−1



! solves the equation and we have proven the existence of

Example 2.4.1. Prove that there are no positive integers x, k and n ≥ 2 such

that x

+ 1 = k(2

− 1).

Solution. Notice that the condition is equivalent to x

+ 1 ≡ 0 (mod 2

− 1).

Since 2

− 1 ≡ 3 (mod 4) it follows that there exists a prime divisor of 2

− 1

that is of the form 3 (mod 4) (if not then 2

−1 ≡ 1 (mod 4)). Label this prime

divisor to be p. Therefore we have

+ 1 ≡ 0 (mod p) →←

Example 2.4.2 (Korea 1999). Find all positive integers n such that 2

− 1

is a multiple of 3 and (2

− 1)/3 is a divisor of 4m

+ 1 for some integer m.

Solution. Since 2

−1 ≡ 0 (mod 3), we must have n = 2k. Therefore, our desired

equation is

−1

|4m

+ 1. I claim that k = 2

for m ≥ 0 is a solution to this.

To prove this requires using diﬀerence of squares and then the Chinese remainder

theorem:

− 1

m−1

+ 1)(4

m−2

+ 1) ···(4 + 1)(4 −1)

= (4

m−1

+ 1)(4

m−2

+ 1) ···(4 + 1).

Justin Stevens 59

We must have 4m

+ 1 ≡ 0 (mod (4

m−1

+ 1)(4

m−2

+ 1) ···(4 + 1)). To use the

Chinese Remainder Theorem to seperate this into diﬀerent parts we must have

all numbers in the product to be relatively prime. To prove this we notice that

+ 1 = 2

a+1

+ 1 and then use the following lemma.

Lemma. Deﬁne F

= 2

+ 1 to be a Fermat number. Prove that all Fermat

numbers are pairwise relatively prime.

Proof. ([12])

Start out with noting that F

= F

m−1

m−2

···F

+ 2. To prove this we use

induction. Notice that for m = 1, we have F

= F

+ 2 since F

= 2

+ 1 = 5 and

= 2

+ 1 = 3. Assume this holds for m = k and I prove it holds for m = k + 1.

m+1

= F

m−1

···F

+ 2

⇐⇒ F

m+1

= F

− 2) + 2 from inductive hypothesis

⇐⇒ F

m+1

= F

− 2F

+ 2

⇐⇒ F

m+1

= (F

− 1)

+ 1

⇐⇒ F

m+1

= (2

)

+ 1

The last step is true by deﬁnition therefore our induction is complete.

Now for 0 ≤ i ≤ m − 1,

gcd(F

, F

) = gcd [F

m−1

m−2

···F

+ 2 − F

m−1

m−2

···F

i+1

i−1

···F

), F

] = gcd(2, F

) = 1.

When we range m over all possible non-negative integers we arrive at the conclu-

sion that all pairs of Fermat numbers are relatively prime.

Notice that each term in the mod is the same as a Fermat number as 4

a+1

= F

a+1

for a ≥ 0. Hence, by Chinese Remainder Theorem the condition

+ 1 ≡ 0 (mod (4

m−1

+ 1)(4

m−2

+ 1)(···)(4 + 1))

is the same as











+ 1 ≡ 0 (mod 4

m−1

+ 1),

+ 1 ≡ 0 (mod 4

m−2

+ 1),

···

+ 1 ≡ 0 (mod 4 + 1).

Now, notice that 4

+ 1 = 4(4

−1

) + 1 = 4



−1



+ 1 for a ≥ 0. Therefore,

the solution to the equation 4m

+1 ≡ 0 (mod 4

+1) is m ≡ 2

−1

(mod 4

+1).

Therefore by Chinese Remainder Theorem there exists an m that satisﬁes all the

above congruences and we have proved k = 2

for m ≥ 0 works.

2.5. Order 60

Assume that k 6= 2

and hence k = p2

for m ≥ 0 and p being an odd integer

that is not 1. Then

− 1

m−1

+ 1)(4

m−2

+ 1) ···(4

+ 1)(4

− 1)

Notice that we must have

+ 1 ≡ 0



mod

∗p

− 1



=⇒ 4m

+ 1 ≡ 0



mod

− 1



Notice that

− 1

− 1) (2

+ 1)

. However, since p is odd we have

3 | 2

+ 1 so

+ 1 ≡ 0



mod

− 1



=⇒ 4m

+ 1 ≡ 0 (mod 2

− 1)

Since p > 1 we clearly have 2

−1 ≡ 3 (mod 4). Assume that all prime divisors

of 2

− 1 are of the form 1 (mod 4). However, this would imply that 2

− 1 ≡ 1

(mod 4) a contradiction therefore there exists at least one prime divisor of 2

−1

that is of the form 3 (mod 4). Label this prime divisor to be z.

(2m)

≡ −1



mod

− 1



≡ −1 (mod z)

but by Theorem 3 this is a contradiction. Henceforth the answer is k = 2

for

m ≥ 0; therefore n = 2

for r ≥ 1.

2.5 Order

Deﬁnition 2.5.1. The order of a mod m (with a and m relatively prime) is the

smallest positive integer x such that a

≡ 1 (mod m). We write this as x = ord

or sometimes shorthanded to o

Example. The order of 2 mod 9 is 6 because 2

≡ 2 (mod 9), 2

≡ 4 (mod 9), 2

≡

8 (mod 9), 2

≡ 7 (mod 9), 2

≡ 5 (mod 9), 2

≡ 1 (mod 9).

Example. Prove that the order of a mod m (with a and m relatively prime) is

less than or equal to φ(m).

Proof. By Euler’s Totient theorem we have

φ(m)

≡ 1 (mod m)

Since order is the smallest x such that a

≡ 1 (mod m) it follows that x ≤

φ(m).

Justin Stevens 61

The following theorem is incredibly important and we will use it a lot through-

out the document.

Theorem 2.5.1. For relatively prime positive integers a and m prove that

≡ 1 (mod m) if and only if

ord

a | n

Proof. If ord

a | n then we have n = ord

aq for some q. Therefore

≡



ord



≡ 1 (mod m)

Now to prove the other direction. By the division algorithm we can write

n = (ord

a) q + r 0 ≤ r < ord

m, q ∈ Z

We now notice that

(ord

a)q+r

= a

≡ 1 (mod m)

=⇒ a

(ord

a)q

≡ 1 (mod m)

=⇒ a

≡ 1 (mod m)

However r < ord

a contradicting the minimality of ord

a if r 6= 0. Therefore

r = 0 and we are done.

Corollary 2.5.1. For relatively prime positive integers a and m

ord

a | φ(m)

Proof. Set n = φ(m) and use Euler’s Totient theorem.

Example 2.5.1. For positive integers a > 1 and n ﬁnd ord

−1

(a)

Solution. We check that the order exists by noting gcd(a

−1, a) = 1. Notice that

ord

−1

(a) = x ⇐⇒ a

− 1 ≡ 0 (mod a

− 1)

For 1 ≤ x < n we have a

− 1 < a

− 1 therefore a

− 1 ≡ 0 (mod a

− 1) is

impossible. For x = n we have a

−1 ≡ 0 (mod a

−1). Therefore ord

−1

(a) =

n .

2.5. Order 62

Example 2.5.2 (AIME 2001). How many positive integer multiples of 1001

can be expressed in the form 10

−10

, where i and j are integers and 0 ≤ i <

j ≤ 99?

Solution. We must have

1001 | 10



j−i

− 1



=⇒ 1001 | 10

j−i

− 1

Notice that ord

1001

(10) = 6 since 10

≡ −1 (mod 1001) and 10

, 10

1 (mod 1001). By theorem 8 we must now have 6 | j − i.

We now relate this problem into a counting problem. In the case that j ≡ i ≡ 0

(mod 6) there are 17 values between 0 and 99 inclusive that satisfy this. We notice

that if we choice two diﬀerent values out of these 17 values, then one must be j

and the other must be i since i < j. Therefore there are





solutions in this

case.

Simiarly, when j ≡ i ≡ 1 (mod 6), j ≡ i ≡ 2 (mod 6), j ≡ i ≡ 3 (mod 6) we

get





solutions. When j ≡ i ≡ 4 (mod 6) and j ≡ i ≡ 5 (mod 6) we get only

16 values between 0 and 99 henceforth we get





solutions.

Our answer is 4





+ 2





= 784 .

Example 2.5.3. Prove that if p is prime, then every prime divisor of 2

−1

is greater than p.

Solution. Let q be a prime divisor of 2

− 1. Therefore we have ord

(2) | p by

Theorem 8. Since p is prime we have

ord

(2) ∈ {1, p}

However, ord

(2) = 1 implies that 2 ≡ 1 (mod q) absurd. Therefore ord

(2) = p.

We also have

ord

(2) | φ(q) =⇒ p | q −1

Therefore q ≥ p + 1 and hence q > p and we are done.

Example 2.5.4. Let p be an odd prime, and let q and r be primes such that

p divides q

+ 1. Prove that either 2r | p − 1 or p | q

− 1.

Justin Stevens 63

Solution. Because p is odd and p | q

+1 we have p - q

−1. Also we have p | q

−1.

Henceforth by Theorem 8

ord

(q) | 2r

However since ord

(q) 6= r we have ord

(q) ∈ {1, 2, 2r}.

When ord

(q) = 2r we have ord

(q) | φ(p) = p − 1 we have 2r | p − 1.

When ord

(q) ∈ {1, 2} in the ﬁrst case we get p | q − 1 and in the second we

get p | q

− 1. In conclusion we get p | q

− 1.

Therefore 2r | p − 1 or p | q

− 1

Example 2.5.5. Let a > 1 and n be given positive integers. If p is an odd

prime divisor of a

+ 1, prove that p − 1 is divisible by 2

n+1

Solution. Since p is odd we have p - a

−1. We also have p |



− 1



+ 1



n+1

− 1. Therefore

ord

(a) | 2

n+1

However ord

(a) - 2

(since if it did then we would have p | a

− 1) hence

ord

(a) = 2

n+1

We know that ord

(a) | p − 1 hence 2

n+1

| p − 1.

Example 2.5.6 (Classical). Let n be an integer with n ≥ 2. Prove that n

doesn’t divide 2

− 1.

Solution. Let p be the smallest prime divisor of n. We have

p | n | 2

− 1

By theorem 8 it follows that ord

(2) | n. However notice that ord

(2) ≤ φ(p) < p

contradicting p being the smallest prime divisor of n.

Example 2.5.7. Prove that for all positive integers a > 1 and n we have

n | φ(a

− 1).

Solution. Since gcd(a

− 1, a) = 1 we consider ord

−1

(a). From above, we have

ord

−1

(a) = n

Now by theorem 8 we have ord

−1

(a) | φ(a

− 1) hence n | φ(a

− 1) as

desired.

2.5. Order 64

Motivation. The motivation to work mod a

−1 stems from the fact that we want

a value to divide φ(a

− 1) so hence we will likely use order mod a

− 1. After a

bit of thought we think to look at ord

− 1).

Example 2.5.8. If a and b are positive integers relatively prime to m with

≡ b

(mod m) and a

≡ b

(mod m) prove that

gcd(x,y)

≡ b

gcd(x,y)

(mod m).

Solution. We have that

≡ b

(mod m)



a · b

−1



− 1



≡ 0 (mod m)



a · b

−1



≡ 1 (mod m)

Set z ≡ a·b

−1

(mod m). From z

≡ 1 (mod m) we have ord

(z) | x. Simiarly

we have ord

(z) | y therefore

ord

(z) | gcd(x, y)

From this we arrive at

gcd(x,y)

≡ 1 (mod m)



a · b

−1



gcd(x,y)

≡ 1 (mod m)

gcd(x,y)

≡ b

gcd(x,y)

(mod m)

Example 2.5.9. Let a and b be relatively prime integers. Prove that any odd

divisor of a

+ b

is of the form 2

n+1

m + 1.

Solution. It suﬃces to prove that all prime divisors of a

+ b

are 1 (mod 2

n+1

If we could do this, by multiplying the prime divisors together we get that all

divisors are of the form 1 (mod 2

n+1

). We let q be an odd divisor of a

+ b

Since gcd(a, b) = 1 it follows that gcd(q, a) = 1 and gcd(q, b) = 1.

Justin Stevens 65

q | a

+ b

q | a

1 +



b · a

−1



q |



b · a

−1



+ 1

q |



b · a

−1



n+1

− 1

Let z ≡ b · a

−1

(mod q). Therefore ord

(z) | 2

n+1

. However since q is odd we

have q - z

− 1 therefore

ord

(z) = 2

n+1

| q − 1

Example 2.5.10 (Bulgaria 1996). Find all pairs of prime p, q such that pq |

− 2

) (5

− 2

Solution. We must either have p | 5

− 2

or p | 5

− 2

. Assume p | 5

− 2

. By

Fermat’s Little Theorem we arrive at

− 2

≡ 3 ≡ 0 (mod p) =⇒ p = 3

We must either have q | (5

− 2

) = 117 or q | (5

− 2

). By the same method,

the second one produces q = 3 while the ﬁrst renders q = 13. Using symettry we

arrive at the solutions (p, q) = (3, 3), (3, 13), (13, 3). Assume that p, q 6= 3 now.

We must have p | 5

− 2

and q | 5

− 2

then.

− 2

≡ 0 (mod p)



5 · 2

−1



− 1



≡ 0 (mod p)



5 · 2

−1



− 1 ≡ 0 (mod p)

Using this same logic we arrive at



5 · 2

−1



− 1 ≡ 0 (mod q)

Let a ≡ 5 · 2

−1

(mod pq). We therefore have

(

ord

(a) | q

ord

(a) | p

=⇒

(

ord

(a) ∈ {1, q} | φ(p)

ord

(a) ∈ {1, p} | φ(q)

2.5. Order 66

If ord

(a) = q and ord

(a) = p then by Theorem 8 we would have

(

q | p − 1

p | q − 1

=⇒

(

p ≥ q + 1

q ≥ p + 1

absurd. Therefore assume WLOG that ord

(a) = 1 therefore a − 1 ≡ 0 (mod p).

Since a ≡ 5 · 2

−1

(mod p) we have

2 (a − 1) ≡ (2) (5)



−1



− 2 ≡ 3 ≡ 0 (mod p)

contradicting p, q 6= 3.

The solutions are hence (p, q) = (3, 3), (3, 13), (13, 3) .

Example 2.5.11 (USA TST 2003). Find all ordered prime triples (p, q, r)

such that p | q

+ 1, q | r

+ 1, and r | p

+ 1.

Solution. We split this up into two cases.

Case 1: Assume that p, q, r 6= 2. We therefore have p - q

− 1 and similarly.

Therefore we have











p | q

− 1

q | r

− 1

r | p

− 1

=⇒











ord

(q) ∈ {1, 2, 2r} | p − 1

ord

(r) ∈ {1, 2, 2p} | q − 1

ord

(p) ∈ {1, 2, 2q} | r − 1

because ord

(q) | 2r and ord

(q) 6= r and similarly.

Assume that ord

(q), ord

(r), ord

(p) ∈ {1, 2}. ord

(q) = 1 implies q ≡ 1

(mod p) and ord

(q) = 2 implies q

≡ 1 (mod p) =⇒ q ≡ −1 (mod p). There-

fore we arrive at











q ≡ ±1 (mod p)

r ≡ ±1 (mod q)

p ≡ ±1 (mod r)

=⇒











q ± 1 ≥ 2p

r ± 1 ≥ 2q

p ± 1 ≥ 2r

since q ±1 6= p from them all being odd. This inequality set is clearly impossible.

Therefore WLOG we set ord

(q) = 2r. We must have 2r | p − 1 (Theorem 8)

but since p and r are odd this reduces down to r | p − 1. However r | p

+ 1 but

+ 1 ≡ 2 6= 0 (mod r) contradiction.

Case 2: We conclude there are no solutions when p, q, r 6= 2. Therefore

WLOG let p = 2. From p | q

+ 1 we arrive at q ≡ 1 (mod 2). Also r is odd since

r | 2

+ 1. Therefore we have r - 2p

− 1 and q - r

− 1.

(

q | r

− 1

r | 2

− 1

=⇒

(

ord

(r) ∈ {1, 4} | q − 1

ord

(2) ∈ {1, 2, 2q} | r − 1

Justin Stevens 67

If ord

(2) = 1 then we have 2 ≡ 1 (mod r) absurd. If ord

(2) = 2 then we have

≡ 1 (mod r) or r = 3. We must have q | 3

− 1 = 80. Since q 6= 2, we check if

q = 5 satisﬁes the equation. (p, q, r) = (2, 5, 3) gives us 2 | 5

+1, 5 | 3

+1, 3 | 2

which are all true. We arrive at the solutions (p, q, r) = (2, 5, 3), (3, 2, 5), (5, 3, 2).

Now we must have ord

(2) = 2q. By theorem 8 we have 2q | r −1. Therefore

since q 6= 2 we have r ≡ 1 (mod q). However q | r

+ 1 but r

+ 1 ≡ 2 6= 0

(mod q).

In conclusion our solutions are (p, q, r) = (2, 5, 3), (3, 2, 5), (5, 3, 2) .

Example 2.5.12. Prove that for n > 1 we have n - 2

n−1

+ 1.

Proof. Let p | n. We arrive at

(

p | 2

p−1

− 1

p | 2

2n−2

− 1

=⇒ p | 2

gcd(p−1,2n−2)

− 1

We must have v

(p − 1) ≥ v

(2n − 2) since n | 2

n−1

+ 1 and p 6= 2.. Let n − 1 =

(n−1)

m. We arrive at

p − 1 ≡ 0 (mod 2

(n−1)+1

) =⇒ n ≡

p ≡ 1 (mod 2

(n−1)+1

)

However this implies v

(n − 1) ≥ v

(n − 1) + 1 clearly absurd.

Example 2.5.13. (China 2009) Find all pairs of primes p, q such that

pq | 5

+ 5

Solution. We divide this solution into two main cases.

Case 1: p = q

In this case we must have

| 2 · 5

=⇒ p = q = 5

Case 2: p 6= q. When q = 5 we arrive at p | 5

+ 5

or therefore

+ 5

≡ 5 + 5

≡ 0 (mod p) =⇒ p = 2, 5, 313

2.5. Order 68

Hence we arrive at (p, q) = (5, 2), (5, 313), (2, 5), (313, 5). Assume p, q 6= 5. We

now have

+ 5

≡ 5 + 5

≡ 0 (mod p) =⇒ 5

q−1

+ 1 ≡ 0 (mod p)

1 + 5

p−1

≡ 0 (mod q)

=⇒ 5

2q−2

≡ 1 (mod p) and 5

2p−2

≡ 1 (mod q)

=⇒ ord

(5) | gcd(2q −2, p − 1) and ord

(5) | gcd(2p − 2, q − 1)

So long as p, q 6= 2 we arrive at

(ord

5) = v

(2q − 2) ≤ v

(p − 1) and v

(ord

5) = v

(2p − 2) ≤ v

(q − 1)

Since 5

q−1

6= 1 (mod p) and 5

p−1

6= 1 (mod q). The two equations above are

clearly a contradiction. Therefore p or q is 2. Let p = 2 for convenience. We then

must have

+ 5

≡ 5

+ 5 ≡ 0 (mod q) =⇒ q = 2, 3, 5

We however know that p 6= q therefore we rule out that solution. The solutions

are hence (p, q) = (2, 3), (2, 5), (3, 2), (5, 2).

In conclusion the solutions are

(p, q) = (2, 3), (2, 5), (3, 2), (5, 2), (5, 5), (5, 313), (313, 5) .

p-adic Valuation

3.1 Deﬁnition and Basic Theorems

Important: Unless otherwise stated p is assumed to be a prime.

Deﬁnition 3.1.1. We deﬁne the p-adic valuation of m to be the highest power

of p that divides m. The notation for this is v

(m).

Example. Since 20 = 2

· 5 we have v

(20) = 2 and v

(20) = 1. Since 360 =

·3

·5

we have v

(120) = 3, v

(360) = 2, v

(360) = 1. m can be a fraction, in

this case we have v





= v

(a) − v

(b).

Theorem 3.1.1. v

(ab) = v

(a) + v

(b).

Proof. Set v

(a) = e

and v

(b) = e

. Therefore a = p

and b = p

where

and b

are relatively prime to p. We then get

ab = p

=⇒ v

(ab) = e

+ e

= v

(a) + v

(b)

Theorem 3.1.2. If v

(a) > v

(b) then v

(a + b) = v

(b).

Proof. Again write v

(a) = e

and v

(b) = e

. We therefore have a = p

and

b = p

. Notice that

a + b = p

+ p

= (p

)



−e

+ b



Since e

≥ e

+ 1 we have p

−e

+ b

≡ b

6= 0 (mod p) therefore v

(a + b) =

= b as desired.

3.1. Deﬁnition and Basic Theorems 70

At this point the reader is likely pondering “these seem interesting but I do

not see use for them”. Hopefully the next example proves otherwise (we’ve split

it into two parts).

Example 3.1.1. Prove that

i=1

is not an integer for n ≥ 2.

Solution. The key idea for the problems is to ﬁnd a prime that divides into the

denominator more than in the numerator.

Notice that

i=1

We consider v

i=1

. From 3.1.2 we get



2i − 1



= v





We then get v



4i − 2



= v





and repeating to sum up the facto-

rial in this way we arrive at

i=1

= v



blog



However for

i=1





to be an integer we need

i=1

≥ v

(n!)



blog



≥ v

(n!)

0 ≥ blog

nc,

which is a contradiction since n ≥ 2.

Justin Stevens 71

Example 3.1.2. Prove that

i=0

2i + 1

is not an integer for n ≥ 1.

Solution.

Deﬁnition 3.1.2. We deﬁne (2i + 1)!! to be the product of all odd numbers less

than or equal to 2i+1. Therefore (2i + 1)!! = (2i + 1) (2i −1) ···3·1. For example

(5)!! = 5 · 3 ·1 = 15.

Similarly to what was done in the previous problem, we can rewrite the sum-

mation as

i=0

2i + 1

i=0

(2n+1)!!

2i+1

(2n + 1)!!

Notice that



(2n + 1)!!

3i − 2

(2n + 1)!!

3i + 2



= v



(2n + 1)!!



Since v



(2n + 1)!!

3i − 2

(2n + 1)!!

3i + 2



> v



(2n + 1)!!



. Repeating to sum all

terms up in groups of three as this, we arrive at

i=0

(2n + 1)!!

2i + 1

≥ v



(2n + 1)!!

blog

(2n+1)c



However we must have



(2n + 1)!!

blog

(2n+1)c



≥ v

[(2n + 1)!!]

0 ≥ blog

(2n + 1)c

which is a contradiction since n ≥ 1.

Example 3.1.3 (ISL 2007 N2). Let b, n > 1 be integers. For all k > 1, there

exists an integer a

so that k | (b − a

). Prove that b = m

for some integer

Solution. Assume to the contrary and that there exists a prime p that divides

into b such that v

(b) 6≡ 0 (mod n). Therefore we set

b = p

n+f

, 1 ≤ f

≤ n − 1

where gcd(b

, p) = 1 and p is a prime. Now let k = p

n(e

+1)

. We must have

(b − a

) ≥ v

(k) = n(e

+ 1).

3.2. p-adic Valuation of Factorials 72

• If v

) ≤ e

then we have

(b) > v

) =⇒ v

(b − a

) = v

) ≤ ne

contradiction!

• If v

) ≥ e

+ 1 then we have

) > v

(b) =⇒ v

(b − a

) = v

(b) < n(e

+ 1)

contradiction!

Both cases lead to a contradiction, therefore f

≡ 0 (mod n) and we have

b = m

3.2 p-adic Valuation of Factorials

Factorials are special cases that really lend themselves to p-adic valuations, as the

following examples show.

Example. Find v

(17!).

Solution. We consider the set {1, 2, ··· , 17}. We count 1 power of 3 for each

element with v

(x) = 1 and we count two powers of 3 for each element with

(x) = 2.

• We begin by counting how many numbers have at least one power of 3 which

is simply b

• We have already accounted for the numbers with two powers of 3, however

they must be counted twice so we add b

c to account for them the second

time.

Our answer is hence b

c + b

c = 6 .

Theorem 3.2.1 (Legendre). For all positive integers n and positive primes

p, we have

(n!) =

∞

i=1





Outline. We consider the power of p that divides into n!.

Justin Stevens 73

• The number of occurences that the factor p

occurs in the set {1, 2, ··· , n}.

We notice that it occurs b

c times.

• The number of occurences that the factor p

occur in the set {1, 2, ··· , n}

is going to be b

c. We have added these once already when we added b

but since we need this to be added 2 times (since it is p

), we add b

c once.

Repeating this process as many times as necessary gives the desired v

(n!) =

∞

i=1





Theorem 3.2.2 (Legendre). For all positive integers n and positive primes

p, we have

(n!) =

n − s

(n)

p − 1

where s

(n) denotes the sum of the digits of n in base p.

Proof. In base n write

n =

i=0



· p



p − 1 ≥ a

≥ 1 and p − 1 ≥ a

≥ 0 for 0 ≤ i ≤ k −1

From 3.2.1 we arrive at

(n!) =

∞

i=1





j=1



j−1

+ p

j−2

+ ··· + 1



j=1



− 1

p − 1



where our steps were motivated by examining

∞

i=1





To make this more rigorous we would use the double summation notation. I avoided this

notation to make the proof more easier to follow.

3.2. p-adic Valuation of Factorials 74

Now we evaluate

n − s

(n)

p − 1

. We notice that s

(n) =

i=0

, which implies that

n − s

(n)

p − 1

i=0



· p



−

i=0

)

p − 1

i=0





− 1



Therefore v

(n!) =

n − s

(n)

p − 1

as desired.

Example 3.2.1 (Canada). Find all positive integers n such that 2

n−1

| n!.

Solution. From 3.2.2 we have

(n!) = n − s

(n) ≥ n − 1 =⇒ 1 ≥ s

(n)

This happens only when n is a power of 2.

Example 3.2.2. Find all positive integers n such that n | (n − 1)!.

Solution. Set n = p

···p

be the prime factorization of n. If k ≥ 2 then write

n = (p

) (p

···p

). From Chinese Remainder Theorem we must prove that

) | (n − 1)! and (p

···p

) | (n − 1)!

However since n − 1 > p

and n − 1 > p

···p

this is true.

Therefore we now consider k = 1 or n = p

. Using Legendre’s formula we

have

− 1)! =

∞

i=1



− 1



≥ e

For e

= 1 this statement is obviously false (which correlates to n being prime).

For e

= 2 we must have



− 1



≥ e

=⇒ p

− 1 ≥ e

Justin Stevens 75

Therefore since e

= 2 we have p

= 2 giving the only counterexample (which

correlates to n = 4). Now for e

≥ 3 we have

∞

i=1



− 1



≥ p

−1

− 1 ≥ 2

−1

− 1 ≥ e

Therefore the anwer is all composite n not equal to 4 .

Example 3.2.3. Prove that for any positive integer n, the quantity

n+1





is an integer. Do not use binomial identities.

Solution. For n + 1 = p prime the problem claim is true by looking at the sets

{n + 1, n + 2, ··· , 2n} and {1, 2, ··· , n} and noticing that factors of p only occur

in the ﬁrst set. Otherwise let p be a prime divisor of n + 1 less than n + 1. We

must prove that





≥ v

(n + 1)

Let v

(n + 1) = k. Therefore write n + 1 = p

where gcd(n

, p) = 1. By

Legendre’s we have





∞

i=1





− 2

∞

i=1





Lemma. When n + 1 = p

and k ≥ m we have





− 2





= 1.

Proof. We notice that 2n = 2n

− 2. Therefore for p 6= 2 we have





= 2n

k−m

− 1 and 2





= 2



k−m

− 1



For p = 2, we arrive at the same formula unless m = 1, which then gives





= 2

− 1 and

= 2

k−1

− 1.

The calculations in both cases are left to the reader to verify (simple exercise).

3.2. p-adic Valuation of Factorials 76

Therefore using our lemma we have





≥ k,

which is what we wanted.

Example 3.2.4 (Putnam 2003). Show that for each positive integer n,

n! =

i=1

lcm

1, 2, . . . ,

(Here lcm denotes the least common multiple, and bxc denotes the greatest

integer ≤ x.)

Solution. If we have v

(a) = v

(b) for all primes p then in conclusion we would have

a = b since the prime factorizations would be the same. Assume that for this case

p ≤ n because otherwise it is clear that v

(n!) = v

i=1

lcm

1, 2, . . . ,

By theorem 7 we have v

(n!) =

∞

i=1





. I claim that this is the same as

i=1

lcm

1, 2, . . . ,

• When i ∈ {1, 2, ··· , b

c} we have at least one power of p in lcm {1, 2, . . . ,





Therefore we add b

• When i ∈ {1, 2, ··· , b

c} we have at least two powers of p in lcm {1, 2, . . . ,





However, since we need to count the power of p

a total of 2 times and it

has already been counted once, we just add it once.

Repeating this process we arrive at v

i=1

lcm

1, 2, . . . ,

∞

i=1





as desired.

Justin Stevens 77

Example 3.2.5. Prove that for all positive integers n, n! divides

n−1

k=0

− 2

Solution. Notice that

n−1

k=0

− 2

) =

n−1

k=0



n−k

− 1



= 2

1+2+···+n−1

n−1

k=1

− 1).

The number of occurences of 2 in the prime factorization of n! is quite obviously

more in

n−1

k=1

− 2

) then in n! using the theorem 7. Therefore we consider all

odd primes p and look at how many times it divides into both expressions.

Lemma.

n−1

k=1

− 1)

≥

∞

i=0



n − 1

(p − 1)p



∞

i=1



n − 1

(p − 1)p

i−1



Outline. We consider the set {2

−1, 2

−1, ··· , 2

n−1

−1} and consider how many

times the exponent p

divides into each term. We consider the worst case scenario

situation when the smallest value of x such that 2

≡ 1 (mod p

) is x = φ(p

) via

Euler’s Totient.

• When p

divides into members of this set, we have

p|(2

− 1) =⇒ k ≡ 0 (mod p − 1).

This results in giving us a total of b

n−1

p−1

c solutions.

• When p

divides into members of this set, we have

|(2

− 1) =⇒ k ≡ 0 (mod p(p − 1)).

We only account for this once using similar logic as to the proof of Legendre’s

theorem therefore we add this a total of b

n−1

p(p−1)

c times.

3.2. p-adic Valuation of Factorials 78

Repeating this process in general gives us



n − 1

φ(p

)





n − 1

(p − 1)p

j−1



and keeping in mind that it is a lower bound, we have proven the lemma.

We desire to have v

n−1

k=1

− 1)

≥ v

(n!) which would in turn give us n!

divides

n−1

k=1

−1). Quite obviously n ≥ p or else v

(n!) = 0 and there is nothing

to consider. Because of this,

n − 1

p − 1

≥

=⇒

n − 1

(p − 1)p

i−1

≥

Therefore, we arrive at

∞

i=1



n − 1

(p − 1)p

i−1



≥

∞

i=1





As a result,

n−1

k=1

− 1)

≥ v

(n!)

and we are done.

Motivation. The motivation behind the solution was looking at small cases. We

take out the factors of 2 because we believe that there are more in the product

we are interested in then in n!. For n = 3 we want 3 | (2

− 1) (2

− 1) (2 − 1).

Obviously 3 | (2

− 1).

Similarly, for n = 5 we want (5 × 3) |(2

− 1) (2

− 1).

Notice that 5|(2

− 1) and 3|(2

− 1).

At this point the motivation to use Fermat’s Little Theorem to ﬁnd which

terms are divisible by p hit me. From here, the idea to use Legendre’s formula

and Euler’s Totient for p

hit me and the rest was groundwork.

Justin Stevens 79

3.2.1 Problems

3.1. (1968 IMO 6) For every natural number n, evaluate the sum

∞

k=0

n + 2

k+1

c = b

n + 1

c + b[

n + 2

c] + ··· + b[

n + 2

k+1

c] + ···

3.2. (1975 USAMO 1) Prove that

(5m)!(5n)!

m!n!(3m + n)!(3n + m)!

is integral for all positive integral m and n.

3.3 Lifting the Exponent

Theorem 3.3.1. For p being an odd prime relatively prime to integers a and

b with p | a − b then

− b

) = v

(a − b) + v

(n) .

Proof. ([?])

We use induction on v

(n).

Base case: We begin with the base case of v

(n) = 0. We have

− b

) = v

(a − b) + v



n−1

+ a

n−2

· b + ··· + b

n−1



Now notice that

n−1

+ a

n−2

· b + ··· + b

n−1

≡ n · a

n−1

(mod p)

from a ≡ b (mod p) therefore since gcd(a, p) = 1 we have

− b

) = v

(a − b)

as desired.

Second base case: It is not necessary to do two base cases, however it will

help us down the road so we do it here. We prove that when v

(n) = 1 we have

− b

) = v

(n) + v

(a − b). Let n = pn

where gcd(n

, p) = 1. We arrive at

− b

) = v

[(a

)

− (b

)

] = v

− b

)

3.3. Lifting the Exponent 80

Now let a = b + kp since we know p | a − b. We arrive at

(b + kp)

− b





(kp) +





(kp)

+ ··· +





(kp)

Using the fact that p |





for all 1 ≤ i ≤ p − 1 we arrive at

[(b + kp)

− b

] = v





+ v

(k) = 2 + v

(a − b) − 1

as desired.

Inductive hypothesis: Assume the statement holds for v

(n) = k and I

prove it holds for v

(n) = k + 1. Set n = p

k+1

. Then we have

h



−





= v



− b



+ 1 = v

(a − b) + k + 1

Via our second base case and inductive hypothesis.

Corollary 3.3.1. For p being an odd prime relatively prime to a and b with

p | a − b and n is a odd positive integer than

+ b

) = v

(a + b) + v

(n)

Theorem 3.3.2. If p = 2 and n is even, and

• 4 | x − y then v

− y

) = v

(x − y) + v

(n)

• 4 | x + y then v

− y

) = v

(x + y) + v

(n)

Proof. This is left to the reader, advising that they follow along the same lines as

the above proof.

Example 3.3.1 (AoPS). Let p > 2013 be a prime. Also, let a and b be

positive integers such that p|(a + b) but p

- (a + b). If p

|(a

2013

+ b

2013

) then

ﬁnd the number of positive integer n ≤ 2013 such that p

|(a

2013

+ b

2013

)

Justin Stevens 81

Solution. The ﬁrst condition is equivalent to v

(a + b) = 1. We also must have

2013

+ b

2013

) ≥ 2. However if p - a, b then we have



2013

+ b

2013



= v

(a + b) + v

(2013) = 1 →←

Therefore p | a, b which in turn gives p

2013

| a

2013

+ b

2013

. Therefore the answer is

all positive integers n less than or equal to 2013 or 2013 .

Example 3.3.2 (AMM). Let a, b, c be positive integers such that c | a

− b

Prove that c |

−b

a−b

Solution. Let

p | c, v

If p - a − b then we obviously have

− b

a − b

Therefore consider p | a −b. Using lifting the exponent so long as p 6= 2, we arrive



− b

a − b



= v

(a − b) + v

(a + b) = x

When p = 2 we arrive at



− b

a − b



= v

(a − b) + v

(a + b) + v

(a − b) ≥ v

(c)

Example 3.3.3 (IMO 1999). Find all pairs of positive integers (x, p) such

that p is prime, x ≤ 2p, and x

p−1

| (p − 1)

+ 1.

Solution. Assume that p 6= 2 for the time being (we will see why later). We

trivially have x = 1 always giving a solution. Now, let q be the minimal prime

divisor of x. We notice that:

q |



(p − 1)



− 1

=⇒ ord



(p − 1)



| gcd(x, q − 1) = 1

=⇒ (p − 1)

− 1 ≡ 0 (mod q)

=⇒ (p − 2) (p) ≡ 0 (mod q)

3.3. Lifting the Exponent 82

We know that (p −1)

+ 1 ≡ 0 (mod q). However, if p −2 ≡ 0 (mod q) then we

have

(p − 1)

+ 1 ≡ 2 6= 0 (mod q)

Since p − 1 is odd. Therefore we must have p ≡ 0 (mod q) or therefore p = q.

Now, by lifting the exponent

we have:

[(p − 1)

+ 1] = 1 + v

(x) ≥ p − 1

x ≥ p

p−2

≥ 2p for p > 3

However we have x ≤ 2p. We now account for p ∈ {2, 3}.

p = 2 gives x | 2 or x = 1, 2. p = 3 gives x

| 2

+ 1 where x ≤ 6. Therefore

we have x = 1, 3. The solutions are hence (x, p) = (1, p), (2, 2), (3, 3).

Example 3.3.4 (Bulgaria). For some positive integers n, the number 3

−2

is a perfect power of a prime. Prove that n is a prime.

Solution. Say n = p

···p

where p

≤ p

≤ ··· ≤ p

and k ≥ 2.

We have 3

− 2

| 3

− 2

. Let p | 3

− 2

for all p

. We have p | z

− 1

where z ≡ 3 · 2

−1

(mod p) since p 6= 2. Therefore

ord

(z) | p

=⇒ ord

(z) | gcd(p

, p

, ··· , p

)

However gcd(p

, p

, ··· , p

) ∈ {1, p

} with it being p

when p

= p

= ··· = p

But if gcd(p

, p

, ··· , p

) = 1 then we have p | z − 1. However

2(z −1) ≡ 1 ≡ 0 (mod p) →←

Therefore p

= p

= ··· = p

. We must therefore consider n = p

Let 3

− 2

= q

. Therefore 3

k−1

− 2

k−1

= q

. Therefore ord

(z) | p

k−1

k ≥ 2. Let ord

(z) = p

. Therefore 3

− 2

≡ 0 (mod q). Now we use lifting

the exponent to give us





k−m

−





k−m

= v



− 2



+ v

(p)

However if q = p then we have ord

(z) | gcd(p

, p − 1) = 1 giving the same p = 1

contradiction. Therefore v

(p) = 0. Hence we must have v



− 2



≥ z.

Therefore

− 2

> 3

− 2

≥ q

since m ≤ k − 1. Therefore k = 1 implying that p is prime.

Comment. When we do Zsigmondy’s theorem you will notice there is a lot easier

solution to this.

lifting the exponent is not the same for p = 2

Justin Stevens 83

Example 3.3.5 (IMO 1990). Find all natural n such that

is an integer.

Solution. Trivially n = 1 is a solution. Now assume n 6= 1 and deﬁne π(n) to be

the smallest prime divisor of n. Let π(n) = p 6= 2. Then we have:

p | 2

+ 1 | 2

− 1 and p | 2

p−1

− 1

=⇒ p | 2

gcd(2n,p−1)

− 1

Now if r 6= 2 | n then we can’t have r | p − 1 because then r ≤ p − 1

contradiction. Therefore r = 2 and since n is odd gcd(2n, p − 1) = 2. Hence

p | 2

− 1 =⇒ p = 3

Let v

(n) = k. By lifting the exponent we must have

+ 1) = 1 + k ≥ v

) = 2k =⇒ k = 1

Let n = 3n

. n

= 1 is a solution (2

+ 1 = 3

= 9). Assume n

6= 1 and let

π(n

) = q 6= 3. By Chinese Remainder Theorem since q 6= 3 we have:

q | 8

+ 1 | 8

− 1 and q | 8

q−1

− 1

=⇒ q | 8

gcd(2n

,q−1)

− 1 = 63 so q = 7

However 2

+ 1 ≡ 8

+ 1 ≡ 2 (mod 7) contradiction.

The solutions are henceforth n = 1, 3.

Example 3.3.6 (China TST 2009). Let a > b > 1 be positive integers and b

be an odd number, let n be a positive integer. If b

| a

−1 prove that a

Solution. We ﬁx b. I claim that the problem reduces down to b prime. Assume

that we have shown the problem statement for b prime (which we will do later).

Now let b be composite and say q | b where q is prime. Then we would have

| b

| a

−1. However, by our assumption q

| a

−1 gives us a

therefore

we have a

> a

. Therefore the problem reduces down to b prime. Let b = p

be prime.

We have p

| a

− 1. Since p | a

− 1 we have ord

a | n. Also by Fermat’s

Little Theorem we have ord

a | p − 1. Let

ord

a = x ≤ p − 1

We now have a

≡ 1 (mod p). Therefore x | n and set n = xn

Now we must have p

| (a

)

− 1. By lifting the exponent we have

[(a

)

− 1] = v

− 1) + v

) ≥ n

3.4. General Problems for the Reader 84

Lemma. log

n ≥ v

(n)

Proof. Let n = p

s. Therefore v

(n) = r. We also have log

n = r+log

s ≥ r.

Therefore we now have

− 1) ≥ n − v

) ≥ n − log

− 1) ≥ log





> a

− 1 ≥ p

−1)

≥

x · p

≥

We use the fact that p is odd in the last step since we have p

≥ 3

3.4 General Problems for the Reader

3.3. [Turkey] Let b

be numbers of factors 2 of the number m! (that is, 2

|m!

and 2

- m!). Find the least m such that m − b

= 1990.

Diophantine equations

4.1 Bounding

Example 4.1.1. (Russia) Find all natural pairs of integers (x, y) such that

− y

= xy + 61.

Solution.

− y

= (x − y)



+ xy + y



= xy + 61

Notice that x > y. Therefore we have to consider x

+ xy + y

≤ xy + 61 or

+ y

≤ 61. Since x > y, we have

61 ≥ x

+ y

≥ 2y

=⇒ y ∈ {1, 2, 3, 4, 5}











y = 1 x

− x − 62 = 0

y = 2 x

− 2x − 69

y = 3 x

− 3x − 89

y = 4 x

− 4x − 125

y = 5 x

− 5x − 186 = 0

Of these equations, we see the only working value for x is when x = 6, y = 5 so

the only natural pair of solutions is (x, y) = (6, 5).

4.2 The Modular Contradiction Method

4.2. The Modular Contradiction Method 86

Example 4.2.1. Find all pairs of integers (x, y) that satisfy the equation

− y! = 2001.

Solution. We consider what happens modulo 7. When y ≥ 7, y! ≡ 0 (mod 7), so

≡ 2001 ≡ −1 (mod 7). Therefore if an x is to satisfy this equation, x

≡ 6

(mod 7). But by analyzing the table shown below, we can see that there are no

solutions to that equation.

x x

(mod 7)

0 0

1 1

2 4

3 2

4 2

5 4

6 1

Therefore y < 7.

Now we must check cases. Note that the smallest perfect square greater than

2001 is 2025 = 45

, and this (surprisingly) gives two valid solutions: (x, y) =

(45, 4) and (x, y) = (−45, 4). This covers all cases with y ≤ 4. If y = 5, then

= 2001 + 5! = 2121, but this equation has no integer solutions since 2121 is

divisible by 3 but not 9. If y = 6, then x

= 2001 + 6! = 2721, which once again

has no solutions for the same reasons as above. Therefore our only solutions are

(x, y) = (45, 4), (−45, 4) .

Tip 4.2.1. When dealing with factorials, it is often advantageous to take advan-

tage of the fact that m! ≡ 0 (mod p) for all positive integers m ≥ p. By ﬁnding

the right mod, we can reduce the number of cases signiﬁcantly.

Example 4.2.2 (USAMTS). Prove that if m and n are natural numbers that

+ 3

+ 1

cannot be a perfect square.

Solution. We look mod 8. Notice that we have

≡ 1 (mod 8) and 3

2k+1

≡ 3 (mod 8)

Justin Stevens 87

Therefore we have 3

≡ {1, 3} (mod 8). Henceforth the possible values of

+ 3

+ 1 mod 8 are 1 + 1 + 1, 3 + 1 + 1, 3 + 3 + 1 which gives 3, 5, 7.

Notice that when x is even we have x

≡ 0, 4 (mod 8). When x = 2k + 1

we get x

= 4k

+ 4k + 1 ≡ 1 (mod 8) since k

+ k ≡ 0 (mod 2). Therefore

the possible values of x

(mod 8) are 0, 1, 4. None of these match the values of

+ 3

+ 1 (mod 8) therefore we have a contradiction.

Motivation. The motivation for looking mod 8 stems from trying mod 4 at ﬁrst.

Trying mod 4 eliminates the case m and n are both even (since then 3

+1 ≡ 3

(mod 4)) and the case when m and n are both odd (since then 3

+1 ≡ 7 ≡ 3

(mod 4)). Since we notice how close this gets us, we try mod 8.

Example 4.2.3. Prove that 19

cannot be written as the sum of a perfect

cube and a perfect fourth power.

Solution. We look (mod 13). Notice that when gcd(x, 13) = 1 we have





≡ 1 (mod 13)

hence substituting y ≡ x

(mod 13) we arrive at y

≡ 1 (mod 13). The solu-

tions to this equation are y ≡ 1, 5, 8, 12 (mod 13). Therefore x

≡ 0, 1, 5, 8, 12

(mod 13).

Next when gcd(x, 13) = 1 we have





≡ 1 (mod 13)

therefore substituting x

≡ y (mod 13) gives us the equation y

≡ 1 (mod 13).

The solutions to this are y ≡ 1, 3, 9 henceforth x

≡ 0, 1, 3, 9 (mod 13).

Lastly, notice that

≡







≡





(6) ≡ (−3)

(6) ≡ 7 (mod 13)

(mod 13) y

(mod 13)

0 0

1 1

5 3

8 9

It is clear that the sum of no two elements above will be 7 (mod 13) therefore

we are done.

4.2. The Modular Contradiction Method 88

Tip 4.2.2. When a problem says to prove a diophantine equation has no solutions

it usually has a modular solution. Finding the right mod is quite an important

trick. Find the modulo which reduces the cases to as small as possible and this

will likely be the right mod to work with. If not, try many diﬀerent mods and see

which ones work.

Example 4.2.4. Find all solutions to the equation x

= y

+ 4 in positive

integers.

Solution. We look (mod 11). The motivation behind this is noting that when

gcd(x, 11) = 1 we have x

≡ 1 (mod 11).

Notice that when gcd(x, 11) = 1 we have





≡ 1 (mod 11).

Therefore substituting y ≡ x

(mod 11) we arrive at y

≡ 1 (mod 11) or y ≡ ±1

(mod 11) therefore x

≡ 0, 1, 10 (mod 11).

The possible squares mod 11 are 0

≡ 0 (mod 11), 1

≡ 1 (mod 11), 2

≡ 4

(mod 11), 3

≡ 9 (mod 11), 4

≡ 5 (mod 11), 5

≡ 3 (mod 11) since x

≡ (11 −

(mod 11). Therefore x

≡ 0, 1, 3, 4, 5, 9 (mod 11).

Henceforth we have:

(mod 11) y

(mod 11)

0 0

1 1

10 3

Therefore x

− y

≡ 4 (mod 11) is impossible and we have concluded that

there are no solutions.

Example 4.2.5 (USAJMO 2013). Are there integers a, b such that a

b + 3

Justin Stevens 89

and ab

+ 3 are perfect cubes?

Solution. The cubic residues mod 9 are −1, 0, 1. Therefore we think to take mod

9. Assume that we can ﬁnd a, b such that a

b + 3 and ab

+ 3 are perfect cubes.

Therefore we must have

(

b + 3 ≡ −1, 0, 1 (mod 9)

+ 3 ≡ −1, 0, 1 (mod 9)

=⇒

(

b ≡ 5, 6, 7 (mod 9)

≡ 5, 6, 7 (mod 9)

If 3 | a we would have a

b ≡ 0 (mod 9) so hence gcd(a, 3) = 1 and similarly

gcd(b, 3) = 1. We notice that via Euler’s Totient Theorem

≡ 0, 1 (mod 9)

Therefore we must have a

b and ab

to multiply to either 0 or 1 when reduced

mod 9. However, 5 ·5 ≡ 7 (mod 9), 5 ·7 ≡ 8 (mod 9), 7 ·7 ≡ 4 (mod 9) therefore

we have arrived at a contradiction.

It is therefore impossibile to ﬁnd a, b such that a

b + 3 and ab

+ 3 are perfect

cubes.

Motivation. The motivation behind this solution was to limit the values on the

possibilities for a

b+ 3 and ab

+3 mod 9. The other key idea was that via Euler’s

Totient φ(9) = 6 therefore (a

b) (ab

) ≡ 0, 1 (mod 9).

Example 4.2.6. Find all solutions to the diophantine equation 7

= 3

+ 4

in positive integers (India)

Solution.

Lemma. ord

(7) = 3

n−1

Sketch. First oﬀ notice that ord

(11) = 3

(prove it!) Via lifting the exponent

we have



− 1



= i + 1 ≥ n

We note that (x, y) = (1, 1) is a solution and there is no solution for y = 2.

Now assume y ≥ 3. Therefore we have

≡ 4 (mod 9) =⇒ x ≡ 2 (mod 3)

4.2. The Modular Contradiction Method 90

I claim that x ≡ 8 (mod 9). From ord

(7) = 9 we have

− 4 ≡ 7

x (mod 9)

− 4 ≡ 0 (mod 27)

After testing x = 2, 5, 8 we arrive at x ≡ 8 (mod 9).

We wish to make 7

constant mod p. Therefore we ﬁnd p such that ord

(7) = 9.

Since 7

−1 = (7

− 1) (7

+ 7

+ 1) and 7

+ 7

+ 1 = 3 ·37 ·1063 we take p = 37.

Since 37 - 7

− 1 we have ord

(7) = 9.

Take the original equation mod 7 and use ord

(3) = 6 to give y ≡ 1 (mod 6).

Therefore y is odd so we write y = 2m + 1 to give us 3

= 3

2m+1

= 3 · 9

. Now

ord

(9) = 9 so hence 9

≡ 9

m (mod 9)

(mod 37).

We have 3

≡ 7

− 4 ≡ 7

− 4 ≡ 12 (mod 37)

m (mod 9) 3

2m+1

(mod 37)

0 3

1 27

2 21

3 4

4 36

5 28

6 30

7 11

8 25

Contradicting 3

= 3

2m+1

≡ 12 (mod 37).

Therefore the only solution is (x, y) = (1, 1).

Example 4.2.7. Solve the diophantine equation in positive integers: 2

+3 =

Solution.

Lemma. ord

11 = 2

n−2

Sketch. We must have ord

11 | 2

n−1

. From lifting the exponent v



− 1



i + 2 Therefore we must have i + 2 ≥ n =⇒ i ≥ n − 2.

(x, y) = (3, 1) is a solution to this equation and x = 4 isn’t. Assume x ≥ 5

now. Take the original equation mod 16 to give us

≡ 3 (mod 16)

≡ 11

(mod 16)

=⇒ y ≡ 3 (mod 4)

Justin Stevens 91

using the lemma.

Therefore

− 3 ≡ 11

y (mod 8)

− 3 ≡ 0 (mod 32)

From which y ≡ 7 (mod 8)

We take p = 2

+ 1 = 17 since ord

(2) = 8.

We also have ord

(11) = 16. Take the equation mod 11 to give x ≡ 3

(mod 10) =⇒ x ≡ 1 (mod 2).

Notice that 11

≡ 11

, 11

≡ 3, 14 (mod 17).

Also

x (mod 8) 2

+ 3 (mod 17)

1 5

3 11

5 1

7 12

Contradicting 2

+ 3 ≡ 11

(mod 17). Therefore the only solution is (x, y) =

(3, 1).

Example 4.2.8 (USAMO 2005). Prove that the system

+ x

y + y = 147

157

+ x

y + y

+ y + z

= 157

147

has no solutions in integers x, y, and z.

Solution. ([16])

We wish to limit the possibilities for z

; therefore we choose to look at the

equation (mod 19). Notice that 147 ≡ 14 (mod 19) and 157 ≡ 5 (mod 19). By

Fermat’s Little Theorem we have

147

157

≡ 14

157

≡ 14

≡ 2 (mod 19)

157

147

≡ 5

147

≡ 5

≡ 11 (mod 19)

Adding the two equations results in





+ y + 1



+ y







+ y + 1



+ x

+ z



≡ [9] + [4] (mod 19)

=⇒



+ y + 1



+ y





+ y + 1



− 1 + z

≡ 13 (mod 19)

=⇒



+ y + 1



+ z

≡ 14 (mod 19)

from ord

(2) = 10

4.3. General Problems for the Reader 92

When gcd(z, 19) = 1 we have (z

)

≡ 1 (mod 19) =⇒ z

≡ ±1 (mod 19).

Therefore z

≡ −1, 0, 1 (mod 19) or henceforth

+ y + 1)

≡ 13, 14, 15 (mod 19)

By work of calculations we ﬁnd that the quadratic residues mod 19 are {0, 1, 4, 5, 6, 7, 9, 11, 16, 17}

therefore we have arrived at a contradiction.

Motivation. There isn’t much motivation behind this solution. The one thing

we have to notice is that z

is a ﬂoater and hence we likely want to limit the

possibilities for it. To do so we take mod 19.

4.3 General Problems for the Reader

4.1. [Hong Kong TST 2002] Prove that if a, b, c, d are integers such that

(3a + 5b)(7b + 11c)(13c + 17d)(19d + 23a) = 2001

2001

then a is even.

Problem Solving Strategies

In this chapter, we explore three famous theorems in Number Theory, and end

with some extremely challenging problems that highlight select problem solving

techniques.

5.1 Chicken Mcnuggets anyone?

Mcdonalds once oﬀered Chicken Mcnuggets in sets of 9 and 20 only. A question

prompted from this is, assuming you only buy sets of 9 and 20 Chicken Mcnuggets

and do not eat/add any during this process, what is the largest amount of Mc-

nuggets that is impossible to make? It turns out the answer is 151, which we will

explore in this section.

Theorem 5.1.1 (Chicken Mcnugget Theorem). Prove that for relatively prime

naturals m, n, the largest impossible sum of m, n (i.e. largest number not ex-

pressable in the form mx + ny for x, y non-negative integers) is mn −m −n.

Proof. (Experimenting)

First oﬀ, let’s try a small case. Let m = 7 and n = 5. We then have to

show that 5 × 7 −5 − 7 = 23 is impossible to make, and every value above 23 is

makable. Assume for sake of contradiction that 23 = 7x + 5y. We then arrive at

x ∈ {0, 1, 2, 3} since when x ≥ 4 this implies that y < 0.











x = 0, 5y = 23

x = 1, 5y = 16

x = 2, 5y = 9

x = 3, 5y = 2

5.1. Chicken Mcnuggets anyone? 94

All of these result in contradictions. Next, notice that











24 = 5 × 2 + 7 × 2

25 = 5 × 5

26 = 5 × 1 + 7 × 3

27 = 5 × 4 + 7 × 1

28 = 7 × 4

29 = 5 × 3 + 7 × 2

30 = 5 × 6

31 = 5 × 2 + 7 × 3

32 = 5 × 5 + 7 × 1

···

We notice that 29 and 24 are exactly the same, except for that the factor of 5 is

increased by 1 in 29. Similarly, the same holds for 25 to 30, and 26 to 31, and

so forth. In fact, once we have 24, 25, 26, 27, 28, the rest of the numbers above 23

are makable by just repeatedly adding 5.

OBSERVATIONS:

• WLOG let n ≥ m. Then, if we can show that mn − m − n is unmakable

and mn −m −n + 1, mn −m −n + 2, ··· , mn −m −n + m, are all makable,

we can just add m repeatedly to make all numbers above mn − m − n.

• There seems to be an inequality related with mn −m − n.

Let’s take a look at our equation above to show that mn−m−n is unmakable.

We arrive at 23 = 7x + 5y. We think to check both mod 5 and mod 7 to see if

this gives us anything. Mod 5 gives us

7x ≡ 23 (mod 5) =⇒ 2x ≡ 3 (mod 5) =⇒ x ≡ −1 (mod 5)

Therefore, we arrive at x ≥ 4, contradicting x ∈ {0, 1, 2, 3}. Taking mod 7 gives

5y ≡ 23 ≡ −5 (mod 7) =⇒ y ≡ −1 (mod 7)

Therefore, we get y ≥ 6 again contradiction. Both of these methods give one of

the variables equal to −1 mod m or mod n. This gives us the inspiration to try

this for the general equation.

Set

mx + ny = mn − m − n.

Justin Stevens 95

Taking mod m of this equation results in ny ≡ −n (mod m). Now, since gcd(n, m) =

1, we must have y ≡ −1 (mod m). Now, we try y = m − 1 to see what happens.

This gives us

mx + n(m − 1) = mn − m − n =⇒ mx = −m

Contradicting x, y non-negative. Obviously, for y more than m − 1 the left hand

side is way bigger than the right hand side, so we have now proven that mn−m−n

is impossible.

Let’s try to construct how would we ﬁnd x, y such that 24 = 7x + 5y. Notice

that taking this equation mod 7, we arrive at

5y ≡ 3 (mod 7) =⇒ y ≡ 2 (mod 7)

Therefore, set y = 2 and we arrive at x = 2 as well. Let’s try to ﬁnd 26 such that

26 = 7x + 5y. Taking this equation mod 7, we arrive at

5y ≡ 5 (mod 7) =⇒ y ≡ 1 (mod 7)

Take y = 1 and we get x = 3. It seems like modulos could do the trick for us. Set

mn − m − n + k = mx + ny (5.1)

Since mn −m −n is a symmetric polynomial (meaning the variables are inter-

changable), we can assume without loss or generality that n ≥ m. If instead

m ≥ n, then replace m by n to get n ≥ m (Sidenote: If m ≥ n, we would have

taken the original equation mod n.) In light of observation 1 above, we only have

to consider

k ∈ {1, 2, 3, ··· , m} (5.2)

Now, what exactly do we have to prove?

• For every k ∈ {1, 2, 3, ··· , m}, there exists a y such that x is an integer.

• For every k ∈ {1, 2, 3, ··· , m}, there exists a y such that x is a non-negative

integer.

Let’s knock oﬀ the ﬁrst item by using the modulo idea. Taking mod m of (1)

gives us

n(y + 1) ≡ k (mod m) =⇒ y + 1 ≡ kn

−1

(mod m)

For any k, we get y ≡ kn

−1

− 1 (mod m)(∗), resulting in x being an integer. We

now must prove that x is a positive integer. Notice that for We know that n−1

(mod m) exists since gcd(m, n) = 1. Now, we must prove that x is a non-negative

5.1. Chicken Mcnuggets anyone? 96

integer. This is a bit harder to do, as we have no idea how to even begin. We know

that we want mn − m − n + k − ny to be positive for every k ∈ {1, 2, 3, ··· , m}.

For y = m − 2, we notice that we get

mn − m − n + k − ny = n − m + k > 0

Similarly, for y = m − y

for m ≥ y

≥ 2, we get

mn − m − n − +k = (y

− 1)n − m + k > 0

However, for y = m − 1, we have no idea where to begin. We do notice that,

however, from (*),

y ≡ −1 (mod m) =⇒ kn

−1

− 1 ≡ −1 (mod m) =⇒ k ≡ 0 (mod m)

Therefore for y = m − 1, we have k = m giving

mn − m − n + k − ny = 0 =⇒ x = 0

Our proof is complete.

This was another awesome problem to do, as it had many key steps involved in

it.

• We ﬁrst oﬀ played around with some small cases (i.e m = 5, n = 7 and

noticed that taking mod m and mod n helped solve the equation). We

also ﬁgured that inequalities would be helpful as they worked when noting

x ∈ {0, 1, 2, 3}.

• We used the ideas of mods to reduce down to y ≡ kn

−1

− 1 (mod m). We

know that there will exist a value of m due to this equation, however, we

must use inequalities to ﬁgure out how.

• We assume without loss or generality that n ≥ m to aid in our use of

inequalities (we do this before the inequalities).

• We show that the equation will always be positive for every k ∈ {1, 2, 3, ··· , m}.

The full rigorous proof below is included again to show what a complete proof

looks like. The above method is included to show the reader what the mathe-

matical method is like as a problem solver. The reader may prefer the following

rigorous proof, but hopefully understood how they would go about ﬁnding this

proof as problem solvers.

using our WLOG

Justin Stevens 97

Proof. (Rigorous) Because the equation is symettric, WLOG assume that n ≥ m.

Assume that mn − m − n = mx + ny. Taking the equation mod m, we arrive at

ny ≡ −n (mod m) =⇒ y ≡ −1 (mod m)

This implies that y ≥ m − 1, however, this gives

mx + ny ≥ mx + mn − m > mn − m − n

Contradiction. Now, I prove that

mn − m − n + k = mx + ny, k ∈ {1, 2, 3, ··· , m}

The reason for this is that for k = k

> m, then we can repeatedly add m to the

reduced value of k

mod m until we reach k

. Our goal is to prove that for every

k, there exists an x such that

• x is an integer.

• x is a non-negative integer.

Taking the equation mod m brings us to

n(y + 1) ≡ k (mod m) =⇒ y ≡ kn

−1

− 1 (mod m)(1)

Using this value of y produces the ﬁrst desired outcome. For the second, we must

have mn −m − n + k − ny ≥ 0. For y = m − y

and m ≥ y

≥ 2, we get

mn − m − n + k − ny = (y

− 1)n − m + k > 0

For y

= 1, we have

y ≡ −1 (mod m) =⇒ kn

−1

− 1 ≡ −1 (mod m) =⇒ k ≡ 0 (mod m)

Therefore, k = m, and we get

mn − m − n + k − ny = mn − m −n + m − n(m − 1) = 0 =⇒ x = 0

Therefore, we have proven our desired statement, and we are done.

Example 5.1.1. (IMO 1983) Let a, b and c be positive integers, no two of

which have a common divisor greater than 1. Show that 2abc − ab − bc − ca

is the largest integer which cannot be expressed in the form xbc + yca + zab,

where x, y, z are non-negative integers.

from gcd(m, n) = 1

5.2. Vieta Jumping 98

5.2 Vieta Jumping

Example 5.2.1 (Putnam 1988). Prove that for every real number N, the

equation

+ x

= x

+ x

has a solution for which x

, x

are all integers larger than N.

Solution. Notice that a trivial solution of this equation is (x

, x

) = (1, 1, 1, 1).

This is our generator of the other solutions, what we are about to do is ﬁnd a

form for another solution in terms of the other variables for x

to ﬁnd a new value

of x

that works. To do this, we have to isolate the variables to make a quadratic

in terms of x

. We arrive at the equation

− x

+ x

) + x

+ x

− x

= 0

Therefore, we notice that if the solutions for x

are x

= r

, r

, we have

+ r

= x

+ x

by Vietas formula. Assume that (x

, x

) = (r

, s

, t

, u

) is a solution of the

original equation with WLOG u

≥ t

≥ s

≥ r

. Then by the above relationship

, x

) = (s

−r

, s

, t

, u

) is also a solution to the equation.

We notice that s

+ s

+ t

− r

> u

≥ t

≥ s

≥ r

. Therefore, the new

solution for x

is the new largest value. Repeating this procedure for the variables

, x

and so on we can always create a new largest value, hence our largest

value tends to inﬁnity and it is larger than N for all real N .

That was a mouthful! Go back and read this a few times through, walk away

from your computer and walk around with it a bit, it’s a confusing method but

once you understand it you are golden!

Example 5.2.2 (IMO 2007). Let a and b be positive integers. Show that if

4ab − 1 divides (4a

− 1)

, then a = b.

Justin Stevens 99

Solution. Start out with noting that because gcd(b, 4ab − 1) = 1, we have:

4ab − 1 | (4a

− 1)

⇐⇒ 4ab − 1 | b

(4a

− 1)

=⇒ 4ab − 1 | 16a

− 8a

+ b

=⇒ 4ab − 1 | (16a

)(a

) − (4ab)(2ab) + b

=⇒ 4ab − 1 | (1)(a

) − (1)(2ab) + b

=⇒ 4ab − 1 | (a −b)

The last step follows from 16a

≡ (4ab)

≡ 1 (mod 4ab − 1) and 4ab ≡ 1

(mod 4ab − 1).

Let (a, b) = (a

, b

) be a solution to 4ab −1|(a −b)

with a

> b

contradicting

a = b where a

and b

are both positive integers. Assume a

+ b

has the smallest

sum among all pairs (a, b) with a > b , and I will prove this is absurd. To do so, I

prove that there exists another solution (a, b) = (a

, b

) with a smaller sum. Set

k =

(a−b

)

4ab

−1

be an equation in a. Expanding this we arrive at

4ab

k − k = a

− 2ab

+ b

=⇒ a

− a(2b

+ 4b

k) + b

+ k = 0

This equation has roots a = a

, a

so we can now use Vietas on the equation to

attempt to prove that a

> a

. First, we must prove a

is a positive integer.

Notice that from a

+ a

= 2b

+ 4b

k via Vietas hence a

is an integer. Assume

that a

is negative or zero. If a

is zero or negative, then we would have

− a

(2b

+ 4b

k) + b

+ k = 0 ≥ b

+ k

absurd. Therefore, a

is a positive integer and (a

, b

) is another pair that con-

tradicts a = b. Now, a

= b

+ k from Vieta’s. Therefore, a

. We desire

to show that a

< a

⇐⇒

+ k

< a

⇐⇒ b

− b

)

− 1

< a

⇐⇒

− b

)

− 1

< (a

− b

)(a

+ b

)

⇐⇒

− b

)

− 1

< a

+ b

5.2. Vieta Jumping 100

Notice that we can cancel a

−b

from both sides because we assumed that a

> b

The last inequality is true because 4a

− 1 > 1 henceforth we have arrived at

the contradiction that a

+ b

> a

+ b

. Henceforth, it is impossible to have

a > b (our original assumption) and by similar logic it is impossible to have b > a

forcing a = b .

Example 5.2.3 (Classical). Let x and y be positive integers such that xy

divides x

+ y

+ 1. Prove that

+ y

+ 1

= 3.

Solution. Let (x, y) = (x

, y

) be a solution such that x + y is minimal and

= k 6= 3. WLOG let x

≥ y

(because the equation is symmetric).

However, if x

= y

, then we must have

= 2 +

= k and since k is a

positive integer, x

= y

= 1 which gives k = 3 but we are assuming k 6= 3 so

hence x

6= y

and x

≥ y

+ 1 (we will use this later). I will prove that we are

able to ﬁnd another solution (x

, y

) with x

+ y

< x

+ y

forcing k = 3 since it

contradicts the assumption that x + y is minimal.

+ y

+ 1

= k

=⇒ x

− x(ky

) + y

+ 1 = 0

This equation is solved when x = x

, x

. We will now prove that x

is a positive

integer. Notice that x

+ x

= ky

therefore x

is an integer. Also from Vietas,

= y

+ 1 > 0 =⇒ x

> 0 from x

> 0. Therefore, x

is a positive integer

and (x

, y

) is another pair that contradicts the

= 3 statement. Using

= y

+ 1, we arrive at x

. We desire x

< x

⇐⇒

+ 1

< x

⇐⇒ y

+ 1 < x

butx

≥ (y

+ 1)

= y

+ 2y + 1 > y

+ 1

Therefore, x

< x

and we have y

+ x

< y

+ x

contradicting our initial

assumption, and hence k = 3 .

Justin Stevens 101

Example 5.2.4. Let a, b be positive integers with ab 6= 1. Suppose that ab −1

divides a

+ b

. Show that

+ b

ab − 1

= 5

Solution. Let (a, b) = (a

, b

) with WLOG a

≥ b

be the pair of integers such

that

+ b

ab − 1

= k 6= 5

and a + b is the smallest. If a

= b

, then we would have

−1

= k = 2 +

which

is only an integer when a

= 1 however a

= b

= 1 gives a

= 1 contradicting

ab 6= 1 and giving zero in the denominator. Therefore a

6= b

and a

≥ b

+ 1 (we

will use this later). I will show that there exist a pair (a, b) = (a

, b

) such that

> a

contradicting a

+ b

being minimal.

+ b

− 1

= k

=⇒ a

+ b

= kab

− k

=⇒ a

− a(kb

) + b

+ k = 0

We now have a quadratic in terms of a with roots a = a

, a

. I will now prove

is a positive integer. Notice that a

+ a

= kb

hence a

is an integer and

= b

+ k gives us that a

is positive since b

+ k is positive and a

is positive.

We desire to prove that a

< a

. From Vietas we have a

= b

+ k hence

< a

⇐⇒

+ k

< a

⇐⇒ b

+ k < a

⇐⇒

+ b

− 1

< a

− b

⇐⇒

+ b

− 1

< a

+ b

from diﬀerence of squares anda

− b

≥ 1

⇐⇒ a

+ b

< a

+ a

− a

− b

⇐⇒ a

+ b

< a

− 1) + b

− b

)

If a

, b

≥ 2 then this inequality is obviously true and a

< a

contradicting

the minimal assumption and k = 5. If a

or b

are equal to 1 then we are not

5.3. Wolstenholme’s Theorem 102

done however and we have to prove that k =

−1

= 5 in this situation. Since

≥ b

+ 1, let b

= 1. We therefore have k =

−1

= a

+ 1 +

−1

. Therefore, we

must have a

−1|2 or a

= 2, 3. In both of these cases, we get k =

2−1

3−1

= 5.

In both cases we have proved k = 5 hence we are done .

5.2.1 Exercises

5.1. [Crux] If a, b, c are positive integers such that 0 < a

+ b

− abc ≤ c show

that a

+ b

− abc is a perfect square.

5.2. [IMO 1988] Let a and b be positive integers such that ab + 1 divides a

+ b

Prove that

ab+1

is a perfect square.

5.3 Wolstenholme’s Theorem

We begin the number theory section with a problem that highlights a key problem

solving technique throughout all of mathematics: experimenting.

Theorem 5.3.1 (Wolstenholme’s). For prime p¿3, express 1 +

+ ···+

p−1

in the form

for m, n relatively prime (meaning they share no common

divisors). Prove that p

divides m.

Proof. (Experimenting)

When solving this problem, a mathematician would ﬁrst oﬀ try to simplify the

problem. Instead of showing p

divides m, we ﬁrst oﬀ try to show that p divides

m. To do this, we start out with some small cases, say p = 5. Notice that

1 +

= 1 +

We see quite clearly that 5

| 25. We begin writing down some observations that

could help us later in the problem.

• The product of the denominators (2, 3, 4) is relatively prime to 5. In fact,

the whole set {1, 2, 3, ··· , p − 1} is relatively prime to p so it makes sense

that there product is relatively prime to p as well.

• In the set of denominators (1, 2, 3, 4) we have 1 + 4 = 5, 2 + 3 = 5.

Justin Stevens 103

We test out the second observation to see if it is of any use:



1 +







= 5





We now invoke our ﬁrst observation, and notice that since gcd(4 × 6, 5) = 1,

the numerator must be divisible by 5 because there are no factors of 5 in the

denominator of

We try extending this grouping idea to the general case:

1 +

+ ··· +

p − 1



1 +

p − 1





p − 2



+ ···

Notice that

1 +

p − 1

p − 2

2(p − 2)

, ···

p − j

j(p − j)

Therefore we can factor out a power of p and the resulting numerator will be

divisible by p since there are no powers of p in the denominator.

Now that we’ve gotten that taken care of, let’s move on to the p

problem. The

ﬁrst thought that we have at this point is to see what the remaining denominators

are after we factor out this ﬁrst power of p. Let’s analyze what we had when p = 5:





= 5





= 5





Now, obviously 5

| m in this case. The question that puzzles us now is why

is the numerator of

likewise divisible by p? Let’s try another example when

p = 7:



1 +











= 7





= 7



120 + 72 + 60

6 × 10 × 12



= 7



252

6 × 10 × 12



= 7 × 7 ×



6 × 10 × 12



Whatever the resulting expression is, it will not contribute any powers of 7

therefore the resulting numerator is divisible by 7

. But why is 120 + 72 + 60

divisible by 7? Going through two base cases has not yielded anything yet. We

could go through and try p = 11, but I’ll spear the reader this. When we hit a

5.3. Wolstenholme’s Theorem 104

dead end in a math problem, we try a diﬀerent technique. We go back to the

general case and remember the equation

p − j

j(p − j)

After factoring out a p, we think ”what if we consider the resulting expression

mod p”. Our study of inverses in the prerequisites tells us that we can indeed

consider this expression mod p. Notice that

j(p − j) ≡ j(−j) ≡ −j

(mod p)

Whoah! This expression seems extremely useful. Since

p−j

j(p−j)

uses up

two terms, and we want for j to take on all the residues mod p, we must multiply

the above expression by 2. For example,

1(p−1)

≡ −1

, but we want both the −1

and the −(p − 1)

terms. Therefore, we now have



p − 1





p − 2



+ ···



≡ −



+ ··· +

(p − 1)



(mod p)

Since gcd(2, p) = 1, it is suﬁcient to show that

−



+ ··· +

(p − 1)



≡ 0 (mod p)

Again, we don’t know exactly how to proceed, but we think we have hit the right

idea. Let’s substitute p = 5 into the new expression and see what results. What

we desire to show is

−





≡ 0 (mod 5)

We think back to what frations mean modulo 5. Fractions are the same thing

as inverses, so let’s think about the set of inverses modulo 5. The set we are

looking at is {1

−1

, 2

−1

, 3

−1

, 4

−1

} (mod 5). Notice that 1

−1

≡ 1 (mod 5), 2

−1

≡ 3

(mod 5), 3

−1

≡ 2 (mod 5), 4

−1

≡ 4 (mod 5) therefore we have

−1

, 2

−1

, 3

−1

, 4

−1

} ≡ {1, 3, 2, 4} (mod 5)

Notice that this is the same reordered set as {1, 2, 3, 4}. Therefore, we arrive at

−





≡ −



+ 2

+ 3

+ 4



(mod 5)

Justin Stevens 105

The resulting expression is divisible by 5 (check it yourself!) Now, we move onto

the general case. We desire to show that

−1

, 2

−1

, 3

−1

, ··· , (p − 1)

−1

} ≡ {1, 2, ··· , (p − 1)} (mod p)

Now, how would we do this? If we could show that no two numbers in the ﬁrst set

are the same, then the two sets will be congruent. This inspires us to use proof

by contradiction, where we assume something is true, then show that this is

actually a contradiction. Assume that

−1

≡ b

−1

(mod p), a 6≡ b (mod p)

However, multiply both sides of the equation by ab to result in

−1

b ≡ abb

−1

(mod p)

a ≡ b (mod p)

Contradiction! Therefore, the two sets must be the same and in general we have

−



+ ··· +

(p − 1)



≡ −



+ 2

+ 3

+ ··· + (p − 1)



(mod p)

Now, we use the identity

+ 2

+ ··· + n

n(n + 1)(2n + 1)

To ﬁnally arrive at

−



+ 2

+ 3

+ ··· + (p − 1)



= −



(p − 1)(p)(2p − 1)



Since gcd(p, 6) = 1 (since p ≥ 5), the numerator of the expression is divisible by

p implying that p

| m.

That was a mouthful! Throughout this problem, we explored many useful

problem solving strategies.

• Weaken the problem: When you have no idea how to attack a problem

initially, try weakening the condition. In this case, we wanted to show that

| m, so we tried tos how p | m, which provided motivation for grouping

the sum.

• Experimenting: We analyzed simple cases such as p = 5 and p = 7 to see

how would we would go about the weakened version of the problem. We

wrote down some observations, and ﬁgured out how to solved the weakened

problem.

5.3. Wolstenholme’s Theorem 106

• Writing out the general form: When our experimentation failed to solve

the general case, we went back to the general form of the equation we found

before. Doing so helped us relate the problem to the sum of the squares of

inverses.

• Back to the drawing board: While the new expression looked more help-

ful, we had no idea how to deal with inverses. Therefore, we experimented

with inverses a bit to make the key observation that the set of inverses mod

p and the set of integers mod p (excluding 0) are the same.

• Prove your lemmas: While our observation looked extremely helpful, we

had to rigorously proof our lemma. In mathematical proof writing, you

cannot take statements for granted, you have to prove them. Thankfully

the lemma was relatively simple to prove.

Here is a formal writeup of the above proof. The reason that I did not show

this formal argument immediately, is many people are left scratching their heads

thinking ”I understand this, but how did the author come up with this?” Also,

to be fully rigorous we must use sigma notation, which is likely confusing to some

readers. You can read the following proof lightheartedly, it is included to show

the reader how to write up a formal proof of their own once they solve an exciting

math problem.

Proof. (Rigorous)

We group the terms as such:

p−1

i=1

p−1

i=1



p − i



p−1

i=1



i(p − i)



Since gcd(2, p) = 1, we now desire to show that

p−1

i=1

i(p − i)

≡ 0 (mod p)

Notice that i(p − i) ≡ −i

, therefore

p−1

i=1

i(p − i)

≡ −

p−1

i=1

(mod p).

Justin Stevens 107

Lemma. All inverses mod a prime are distinct, i.e. a

−1

≡ b

−1

(mod p) ⇐⇒ a ≡

b (mod p)

Proof.

−1

≡ b

−1

(mod p)

(ab) a

−1

≡ (ab) b

−1

(mod p)

a ≡ b (mod p)

Therefore

−1

, 2

−1

, 3

−1

, ··· , (p − 1)

−1

} ≡ {1, 2, 3, ··· , (p − 1)} (mod p)

Therefore

−

p−1

i=1

(mod p) ≡ −

p−1

i=1

(p − 1)p(2p − 1)

≡ 0 (mod p)

Since gcd(p, 6) = 1. We are now done.

Notice how while the above proof is extremely concise, we have no motivation

for why we broke the sum up as such, or how we would have thought of the above

solution alltogether!

Here is a similar problem, which is much harder than this above theorem. We

again include full motivation and a fully rigorous solution.

Example 5.3.1. (IberoAmerican Olympiad) Let p > 3 be a prime. Prove

that if

p−1

i=1

with (n, m) = 1 then p

divides n.

Proof. (Experminenting) Incomplete.

Proof. (Rigorous) This is equivalent to wishing to prove that

p−1

i=1

≡ 0 (mod p

)

5.3. Wolstenholme’s Theorem 108

treating each of the numbers as inverses and using gcd(p, 2) = 1.

We now notice

(p−j)

. Therefore

p−1

i=1

p−1

i=1

(p − i)

+ i

(p − i)

By lifting the exponent v

((p − i)

+ i

) = v

(p − i + i)+v

(p) = 2. Therefore

we can factor a p

out of the numerator to give us

p−1

i=1

(p − i)

+ i

(p − i)

= p

p−1

i=1

(p−i)

(p − i)

≡ 0 (mod p

)

⇐⇒

p−1

i=1

(p−i)

(p − i)

≡ 0 (mod p)

Notice that i ≡ −(p − i) (mod p) so hence we now need

p−1

i=1

(p−i)

≡ 0 (mod p)

since we can take the negative out of the denominator.

We consider

p−1

i=1

(

p+1

)

p−1

)

p−1

i=1

+(p−i)

−(

(p+1)

)

−(

(p−1)

)

We desire to show each part is divisible by p. For the ﬁrst sum notice that

we want

p−1

i=1

≡

p−1

i=1

(mod p) since each element from 1 to p − 1 has a

distinct inverse including 1

−1

≡ 1 (mod p) and (p − 1)

−1

≡ (p − 1) (mod p).

By Fermat’s Little Theorem we have

p−1

i=1

≡

p−1

i=1

(mod p) ≡

(p − 1)(p)(2p − 1)

≡ 0 (mod p)

since p 6= 2, 3.

Now we desire to prove that

+(p−i)

−

(

(p+1)

)

−

(

p−1

)

≡ 0 (mod p). Since

gcd(p, 2) = 1 we want

+ 2

(p − i)

− (p + 1)

− (p − 1)

≡ 0 (mod p

)







p(−i)

p−1

+ (−i)



−







+ 1 + p





(−1)

p−1

+ (−1)



≡ 0 (mod p

)





− 2p

≡ 0 (mod p

)

Justin Stevens 109

The second step follows from the fact that p





≡ 0 (mod p

) and every i ≥ 3

we have p





≡ 0 (mod p

), and the third step follows from p being odd.

Now, p

− 2) ≡ 0 (mod p

) is true by Fermat’s Little Theorem therefore

we are done.

5.4 Bonus Problems

Example 5.4.1 (IMO 1989). Prove that for all n we can ﬁnd a set of n

consecutive integers such that none of them is a power of a prime number.

Solution. I claim that the set {(2n + 2)! + 2, (2n + 2)! + 3, ··· , (2n + 2)! + n + 1}

satisﬁes the problem statement. Notice that

(2n + 2)! + 2 = 2



1 +

(2n + 2)!



Since

(2n+2)!

≡ 0 (mod 2) it follows that 1 +

(2n+2)!

≡ 1 (mod 2); henceforth it is

impossible for (2n + 2)! + 2 to be a power of a prime number because it has an

even and an odd factor.

Next, notice that

(2n + 2)! + k = k



1 +

(2n + 2)!



Because 2 ≤ k ≤ n + 1 we must have (2n + 2)! ≡ 0 (mod k

) or hence

(2n+2)!

≡ 0

(mod k). Therefore 1 +

(2n+2)!

≡ 1 (mod k). However, since (2n + 2)! + k is

divisible by k it must be a perfect power of k, but since 1 +

(2n+2)!

is not a perfect

power of k it follows that (2n + 2)! + k is not a perfect power of a prime.

Motivation. The way that we arrived at this set may be a bit confusing to the

reader so I explain my motivation. When I see a problem like this I instantly

think of factorials. The reason behind this is that if I asked to ﬁnd a set of n

consecutive integers none of which are prime, I would use the set

{(n + 1)! + 2, (n + 1)! + 3, ··· , (n + 1)! + n + 1}

for n ≥ 1. The reason behind this is we are looking for numbers that have two

divisors.

5.4. Bonus Problems 110

In this case we are looking for numbers that have a divisor divisible by k and

another that is not divisible by k. I noticed that looking in the prime factorization

of (2n)! that we can ﬁnd two factors of any number k with 2 ≤ k ≤ n. Therefore

looking at (2n!) + k we can ﬁnd that this number is divisible by k but when we

factorize it we are left with a term that is 1 (mod k).

(Note: The following example includes some intense notation. For this reason

we have included a table for f

(x) and g

(x) in the ”motivation” section in hopes

for the reader to better understand the notation.)

Example 5.4.2 (USA TSTST 2013). Deﬁne a function f : N → N by

f(1) = 1, f(n + 1) = f(n) + 2

f(n)

for every positive integer n. Prove that

f(1), f(2), . . . , f(3

2013

) leave distinct remainders when divided by 3

2013

Solution. Deﬁne f(x) to be the same as in the problem. Deﬁne a function f

(x)

such that 0 ≤ f

(x) ≤ 3

− 1 and f

(x) ≡ f (x) (mod 3

). Next, deﬁne g

(x)

such that 0 ≤ g

(x) ≤ φ(3

) − 1 and g

(x) ≡ f(x) (mod φ(3

)). We re-write the

problem statement as if x, y ∈ {1, 2, ··· , 3

} we have f

(x) = f

(y) ⇐⇒ x = y

(i.e. f

(x) is distinct). A few nice properties of these:

1. By Chinese remainder theorem we have f

n−1

(x) ≡ f

(x) ≡ g

(x) (mod 3

n−1

2. By Euler’s totient we have f

(x) ≡ 2

(x−1)

+ f

(x − 1) (mod 3

3. From (1) and (2) along with Chinese Remainder Theorem we have g

(x) ≡

(x−1)

+ g

(x − 1) (mod φ(3

))

I claim that f

(x) = f

(y) ⇐⇒ x ≡ y (mod 3

). This is to say that the

values of f

(x) are distinct when x ∈ {1, 2, ··· , 3

} and we have f

(x) has a

period of 3

(i.e f

(x) = f

(x + 3

m) where m is a positive integer.

Base case: We have f

(1) = 1, f

(2) = 0, f

(3) = 2 therefore the problem

statement holds for k = 1. Notice that g

(x) = 1 therefore f

(x) ≡ 2 + f

(x − 1)

(mod 3) from proposition (2). Therefore it is clear that f

(x) = f

(x + 3m).

Inductive hypothesis: f

(x) = f

(y) ⇐⇒ x ≡ y (mod 3

) holds for

n = k. I claim it holds for n = k + 1.

From (1) we have g

k+1

(x) ≡ f

(x) (mod 3

). Therefore we have

k+1

(x) ≡ g

k+1

(y) (mod 3

) ⇐⇒ x ≡ y (mod 3

)

Since φ(3

k+1

) = 2 · 3

and g

k+1

(x) is odd we have g

k+1

(x) = g

k+1

(x + 3

m) for

positive integers m. This means that we can separate g

k+1

(x) into three ”groups”

that have length 3

and are ordered g

k+1

(1), g

k+1

(2), ··· , g

k+1

Justin Stevens 111

Because f

(x) ≡ g

k+1

(x) ≡ f

k+1

(x) (mod 3

) we can separate f

k+1

(x) into

three groups all of whose elements correspond to f

(x) mod 3

. We now have

k+1

(x) ≡ f

k+1

(y) (mod 3

) ⇐⇒ x ≡ y (mod 3

)

We must now prove that

• f

k+1

(x) = f

k+1

(x + 3

k+1

m) where m is a positive integer.

• f

k+1

(x) 6≡ f

k+1

(x + 3

) (mod 3

k+1

) 6≡ f

k+1

(x + 2 · 3

) (mod 3

k+1

Both of these two statements boil down to (2). We notice that we have

k+1

(x + 3

) ≡ 2

k+1

(

x+3

−1

)

+ f

k+1



x + 3

− 1



(mod 3

k+1

)

=⇒ f

k+1

(x + 3

) ≡ 2

k+1

(

x+3

−1

)

+ 2

k+1

(

x+3

−2

)

+ ··· + 2

k+1

(x)

+ f

k+1

(x) (mod 3

k+1

)

We now notice that g

k+1

(y) takes on all of the odd integers from 1 to φ



k+1



−

1. This is exactly the number of elements we have above henceforth it happens

that

k+1

(x + 3

) ≡ 2

+ 2

+ ··· + 2

(

k+1

)

−1

+ f

k+1

(x) (mod 3

k+1

)

k+1

(x + 3

) ≡ 2

φ(3

k+1

)

− 1

+ f

k+1

(x) (mod 3

k+1

)

Via lifting the exponent we have



φ(3

k+1

)

− 1



= k + 1

Therefore v

φ(3

k+1

)

− 1

= k henceforth f

k+1

(x + 3

) ≡ f

k+1

(x) (mod 3

)

but f

k+1

(x + 3

) 6= f

k+1

(x) (mod 3

k+1

). We write f

k+1

(x + 3

) − f

k+1

(x) = z3

where gcd(z, 3) = 1. Notice that substituting x = n3

+ x

we arrive at

k+1

+ (n + 1) · 3

) − f

k+1

+ n3

) ≡ z3

(mod 3

k+1

)

from which we can derive

k+1



x + a · 3



− f

k+1



x + b · 3



≡ (a − b)3

(mod 3

k+1

)

Now, notice that f

k+1

(x+3

)−f

k+1

(x) = z3

, f

k+1

(x+2·3

)−f

k+1

(x+3

) = z3

and f

k+1

(x+2·3

)−f

k+1

(x) = 2z3

therefore the ﬁrst part of our list of necessary

conditions is taken care of. Now, notice that substituting a = 3m, b = 0 into the

second equation we arrive at the second condition.

Our induction is henceforth complete. Because the problem statement holds

for all n it also holds for 2013 and we are done.

5.4. Bonus Problems 112

Motivation. The main motivation I had when solving this problem was to look at

the table of f

(x) and g

(x). This table was derived using properties (2) and (3).

Notice how the other properties hold for this table.

x f

(x) g

(x)

1 1 1

2 3 3

3 5 2

4 1 7

5 3 9

6 5 8

7 1 4

8 3 6

9 5 5

Example 5.4.3 (IMO 2005). Determine all positive integers relatively prime

to all the terms of the inﬁnite sequence 2

+ 3

+ 6

− 1, n ≥ 1

Solution. [[2]]

I prove that for all primes p there exists a term in the sequence that is divisible

by p. I claim that when n = p − 2 we have 2

p−2

+ 3

p−2

+ 6

p−2

− 1 ≡ 0 (mod p).



p−2

+ 3

p−2

+ 6

p−2

− 1



≡ 3(2

p−1

) + 2(3

p−1

) + 6

p−1

− 6

≡ 3(1) + 2(1) + 6(1) − 6 ≡ 0 (mod p)

Therefore when p 6= 2, 3 it follows that

p−2

+ 3

p−2

+ 6

p−2

− 1 ≡ 0 (mod p)

When p = 2 we notice that n = 1 gives 2

+ 3

+ 6

− 1 = 10 ≡ 0 (mod 2) and

when p = 3 that n = 2 gives 2

+ 3

+ 6

− 1 = 48 ≡ 0 (mod 3).

In conclusion notice that all primes divide a term in the sequence hence the

only positive integer relatively prime to every term in the sequence is 1.

Motivation. The motivation behind this problem is noticing that most likely every

prime divides into at least one term and then trying to ﬁnd which value of n

generates this. The motivation fo rhte choice of n stems from noticing that 2

p−2

+ 6

p−2

− 1 ≡

− 1 ≡ 0 (mod p). This is unfortunately not a fully

Justin Stevens 113

rigorous proof as most olympiads do not accept working in fractions when we

think about modulos (even though it is a fully legitimate method and is in fact

necessary to prove some theorems).

Example 5.4.4 (IMO 1971). Prove that we can ﬁnd an inﬁnite set of positive

integers of the form 2

− 3 (such that n is a positive integer) every pair of

which are relatively prime.

Solution. [[15],[3]]

We use induction. Our base case is when a set has 2 elements and that is

done by {5, 13}. Let a set have N elements and I prove it is always possible to

construct a N + 1 element set with the new element larger than all the previous

elements. Let all the distinct primes that divide the least common multiple of the

N elements be p

, p

, ··· , p

. Denote the new element that we add to the set to be

−3. We desire to have 2

−3 6≡ 0 (mod p

) for 1 ≤ j ≤ k. Since gcd(p

, 2) = 1

we have 2

−1

≡ 1 (mod p

). Therefore letting

x =

i=1

− 1)

to give us 2

− 3 ≡ −2 (mod p

) and since gcd(p

, 2) = 1 we have 2

− 3 6≡ 0

(mod p

) as desired.

Notice that this process is always increasing the newest member of the set

therefore we may do this process an inﬁnite amount of times to give us an inﬁnite

set.

Motivation. The motivation behind using induction is to think of how you can

construct an inﬁnite set. It would be quite tough to build an inﬁnite set without

ﬁnding a way to construct a new term in the sequence which is essentially what

we do here.

Example 5.4.5. (IMO Shortlist 1988) A positive integer is called a double

number if its decimal representation consists of a block of digits, not com-

mencing with 0, followed immediately by an identical block. So, for instance,

360360 is a double number, but 36036 is not. Show that there are inﬁnitely

many double numbers which are perfect squares.

5.4. Bonus Problems 114

Solution. Let C(n) be this function and notice that when n =

k−1

i=0

(10

) where

0 ≤ a

≤ 9 when m 6= k −1 and 1 ≤ a

k−1

≤ 9, we have

C(n) = (10

+ 1)

k−1

i=0

(10

)

We set

• 10

+ 1 = 49p

···p

•

k−1

i=0

(10

) = 36p

···p

Obviously C(n) is a perfect square in this case. Also since

k−1

i=0

(10

) =

(10

+ 1) < 10

it follows that 1 ≤ a

k−1

≤ 9. It is left to prove that there are inﬁnite k such that

49|(10

+ 1). Noticing that ord

(10) = 42, we see that k = 42x + 21 satisﬁes the

condition 10

+1 ≡ 0 (mod 49) hence we have constructed inﬁnitely many double

numbers which are perfect squares.

Notation

This text was written primarily for any audience who enjoys number theory and

wants to learn new problem solving skills. In this text, we will attack many hard

problems using many diﬀerent methods and tips in number theory. In this text,

we attack many hard math problems using simple methods and formulae. Each

section begins with a theorem or general idea, along with a fully rigorous proof.

By the end of this text, I hope the reader has mastered the method of induction.

Each section is then ﬁlled with problems oﬀ of the main idea of the section.

Instead of including many computational problems, we begin with a few “easier”

problems and then dig right into olympiad problems. While this may be hard or

challenging to those just getting acquainted with mathematics, through personal

experience, this is the best way to learn number theory. I highly recommend the

reader spends time on each and every problem before reading the given solution.

If you do not solve the problem immediately, do not fret, it took me a very long

time to solve most of the problem myself.

Spend your time and struggle through the problems, and enjoy this text!

A.0.1 Sets

• The real numbers R are any positive or negative number including 0, such

as 1, 1 +

√

2, −π, e, etc

• The integers Z are deﬁned as the integers:

{··· , −3, −2, −1, 0, 1, 2, 3, ···}

denotes the positive integers {1, 2, 3, ···} while Z

−

denotes the negative

integers {··· , −3, −2, −1}.

• The natural numbers N are deﬁned as the positive integers or Z

. The

natural numbers including 0 are deﬁned as N

115

116

• The rational numbers Q are deﬁned as the ratio of two integers, such as

• The complex numbers C are deﬁned as a + bi where a, b ∈ R.

• The set of polynomials with integer coeﬃcients is deﬁned as Z[x]. For ex-

ample, x

− 19x

+ 1 ∈ Z[x], however, x

− πx 6∈ Z[x].

• The set of polynomials with rational coeﬃcients is deﬁned as Q[x]. For

example, x

−

x ∈ Q[x].

We say that a divides b if

is an integer. For example, 4 divides 12 since

= 3, however, 4 does not divide 13 since

= 3.25. We write a divides b as

a | b. In this, b is also a multiple of a. In this text, when we say ”divisors”

we assume positive divisors. When considering divisors of natural n, we only

have to work up to

√

n. The reason for this is if n = ab then we obviously cannot

have a, b >

√

Induction is a proof technique used often in math. As it can be tricky to those

who are understanding it for the ﬁrst time, we begin with an example problem

and explain the method of induction as we solve this problem.

Example A.0.1. Show that for all natural n, 1 + 2 + 3 + ··· + n =

n(n+1)

Solution. In induction, we ﬁrst oﬀ have to show a statement holds for a base case,

typically n = 1. In this case,

1 =

1 × 2

so the base case holds. We now show that if the problem statement holds for

n = k, then it holds for n = k + 1. This essentially sets oﬀ a chain, where we have

n = 1 =⇒ n = 2 =⇒ n = 3 =⇒ ···

The reason we have to show the base case is because it is the oﬀseter of the chain.

Because of this reason, we can think of induction as a chain of dominoes. Once

we knock down the ﬁrst domino, and show that hitting a domino will knock down

the proceeding domino, we know all the dominoes will be knocked down. Our

inductive hypothesis is that the problem statement holds for n = k, or henceforth

1 + 2 + 3 + ··· + k =

k(k + 1)

Justin Stevens 117

We now need to show that it holds for n = k + 1 or we need to show that

1 + 2 + 3 + ··· + (k + 1) =

(k+1)(k+2)

. Now, notice that

1 + 2 + 3 + ··· + (k + 1) = (1 + 2 + 3 + ··· + k) + k + 1

k(k + 1)

+ k + 1 =

(k + 1)(k + 2)

As desired. Therefore, we have completed our induction.

Theorem A.0.1 (Induction). Let’s say we have a statement P (n) that we

wish to show holds for all natural n. It is suﬃcient to show the statement holds

for n = 1 and that P (k) =⇒ P (k + 1) for natural k, then the statement is

true for all natural n.

NOTE: The statement P (k) =⇒ P (k + 1) means that if P (k) is true

(meaning the statement holds for n = k), then P (k + 1) is true. This is used

for ease of communication.

Proof. We use the well ordering principle. The well ordering principle states

that every set has a smallest element. In this case, assume that for sake of

contradiction, P (n) is not true for some n = x ∈ S. Let y be the smallest

element of S and since y > 1 (from us showing the base case), we have y −1 ≥ 1.

Therefore P (y − 1) is true. We also know that P (k) =⇒ P (k + 1). Therefore,

P (y − 1) =⇒ P (y), contradiction.

Theorem A.0.2 (Strong induction). For a statement P (n) that we wish to

show holds for all natural n, it is suﬃcient to show a base case (n = 1) and

that if P (n) is true for n ∈ {1, 2, 3, ··· , k} it implies P (k + 1) is true.

Proof. The proof is identical to the above proof verbatum.

It is assumed the reader has prior knowledge of induction, so this should be

review. If induction is still confusing at this point, we recommend the reader reads

up on induction as it is vital for this text.

This section includes formulas it is assumed the reader knows.

Theorem A.0.3 (Binomial Theorem). For n natural,

(x + y)

i=0





n−i

118

Deﬁnition A.0.1. The greatest common divisor of two integers a, b is denoted

gcd(a, b). For example, gcd(4, 12) = 4.

Deﬁnition A.0.2. The least common multiple of two integers a, b is denoted

lcm[a, b]. For example lcm[4, 15] = 60

Deﬁnition A.0.3. We deﬁne

a ≡ b (mod c) ⇐⇒ c | a −b

For example 13 ≡ 1 (mod 4) since 4 | 12.

Deﬁnition A.0.4. A number is said to be prime if the only divisors of the number

are 1 and itself. For example, 5 is prime since 1 | 5, 2 - 5, 3 - 5, 4 - 5, 5 | 5. On the

other hand, 6 is not prime as 1, 2, 3, 6 | 6. A number is said to be composite if n

can be expressed in the form ab for a, b being positive integers greater than 1. 1

is said to be neither prime nor composite.

Deﬁnition A.0.5. −→←− means ”contradiction”

Deﬁnition A.0.6. The degree of a polynomial is deﬁned as the highest exponent

in its expansion. For example, deg(x

−2x

+ 1) = 3 and deg(−x

+ x

−1) = 4.

Solutions

Solutions of Chapter 1

1.1 Note that

603 = 301 × 2 + 1

Therefore, by the Euclidean Algorithm, we have gcd(603, 301) = gcd(1, 301) = 1 .

1.2

289 = 153 × 1 + 136

153 = 136 × 1 + 17

136 = 17 × 8 + 0.

Therefore gcd(153, 289) = 17 .

1.3

189 = 133 × 1 + 56

133 = 56 × 2 + 19

56 = 19 × 2 + 18

19 = 18 × 1 + 1.

Therefore gcd(189, 133) = 1 .

1.4 Let the two numbers be a, b with a > b. Recall that gcd(a, b)lcm[a, b] = ab,

therefore ab = 384. Furthermore, a = b + 8, therefore we have

b(b + 8) = 384 =⇒ b

+ 8b − 384 = 0 =⇒ b = 16.

This gives a = b + 8 = 24, therefore a + b = 24 + 16 = 40 .

119

120

1.5 The ﬁrst step is to divide the leading term of a(x), x

, by the leading term

of b(x), x

= x

. Therefore

+ 4x

+ 2x =



+ 2x





−2x

+ 4x

+ 2x



The next step is to divide the leading term of r

(x), −2x

, by the leading term

of b(x), x

−2x

= −2x. We add this to the quotient and subtract from the

remainder:

+ 4x

+ 2x =



+ 2x



− 2x





+ 4x

+ 2x



Finally, we once again divide the leading of r

(x), 4x

by the leading term of x

= 4. We add this to quotient and subtract from the remainder:

+ 4x

+ 2x =



+ 2x



− 2x + 4





−4x

+ 2x



Therefore, q(x) = x

− 2x + 4 and r(x) = −4x

+ 2x. Note that deg(r(x)) = 2 <

deg(b(x)) = 3.

1.6 In order for the improper fraction to not be in lowest terms, we must have

gcd(N

+ 7, N + 4) 6= 1. We ﬁnd that

+ 7 = (N + 4) (N − 4) + 23.

Therefore gcd(N

+7) = gcd(N +4, 23) Since 23 is prime, we must have 23 | N +4.

The smallest value of N which works in the speciﬁed range is 23 × 0 + 19 = 19,

and the largest is 23 ×85 + 19 = 1974. Therefore, there is a total of 85 + 1 = 86

values of N which work.

1.7

gcd(21n + 4, 14n + 3) = gcd(7n + 1, 14n + 3)

= gcd(7n + 1, 14n + 3 − 2(7n + 1))

= gcd(7n + 1, 1)

= 1.

1.8

− x



− x



(x − 1) +



− x



− x =



− x



(x + 1) .

Therefore, gcd(x

− x

, x

− x) = x

− x .

Justin Stevens 121

1.9 We use the division algorithm to divide ax

+ bx

+ 1 by x

−x −1. First oﬀ,

divide the leading terms to get

= ax:

+ bx

+ 1 =



− x − 1



(ax) +



(a + b)x

+ ax + 1



Next, divide the leading term of the remainder by the leading term of the dividend

to get

(a+b)x

= a + b. Add this to the quotient:

+ bx

+ 1 =



− x − 1



(ax + a + b) + [(2a + b)x + a + b + 1] .

In order for x

−x −1 to divide ax

+ bx

+ 1, the remainder must be 0. Therefore

we must have

(

2a + b = 0

a + b + 1 = 0

From the ﬁrst equation, we hae b = −2a. Substituting this into the second

equation gives a + (−2a) + 1 = 0 =⇒ a = 1

and b = −2 .

1.10 We use induction. For a base case, note that gcd(F

, F

) = gcd(1, 1) = 1

and gcd(F

, F

) = gcd(1, 2) = 1.

For the inductive hypothesis part, assume that gcd(F

, F

m+1

) = 1. We now

show that this implies that gcd(F

m+1

, F

m+2

) = 1, completing the induction. By

the Euclidean Algorithm, note that

gcd(F

m+1

, F

m+2

) = gcd(F

m+1

, F

m+2

− F

m+1

By deﬁnition of Fibonacci numbers, we have F

m+2

= F

m+1

+ F

=⇒ F

m+2

−

m+1

= F

. Therefore,

gcd(F

m+1

, F

m+2

) = gcd(F

m+1

, F

) = 1

by the inductive hypothesis. Therefore, we have shown that m =⇒ m + 1 and

by induction, we are done.

1.11 Let the two relatively prime numbers be a and b. Assume for the sake of

contradiction that gcd(ab, a + b) 6= 1, meaning that there exists a prime p such

that p | ab and p | a + b. Recall that by Euclid’s Lemma,

p | ab =⇒ p | a or p | b.

However, in the case that p | a, since we also know that p | a + b, we must have

p | b, contradicting the fact that a and b are relatively prime. The same argument

holds in the case that p | b. Therefore, we have arrived at a contradiction, and we

must have gcd(ab, a + b) = 1.

122

1.12

97 = 5 × 19 + 2

5 = 2 × 2 + 1.

Running these steps in reverse, we ﬁnd that

1 = 5 − 2 ×2 = 5 − 2 × (97 −5 × 19) = 5 × 39 + 97 × (−2).

Therefore x = 39 and y = −2.

1.13

1110 = 1011 × 1 + 99

1011 = 99 × 10 + 21

99 = 21 × 4 + 15

21 = 15 × 1 + 6

15 = 6 × 2 + 3.

Running these steps in reverse gives

3 = 15 − 2 × 6

= 15 − 2(21 − 15 × 1) = 3 × 15 − 2 × 21

= 3 × (99 − 21 × 4) − 2 × 21 = 3 × 99 − 14 ×21

= 3 × 99 − 14 × (1011 − 99 × 10) = 143 × 99 − 14 ×1011

= 143 × (1110 − 1011) − 14 × 1011 = 143 × 1110 − 157 × 1011.

Therefore x = 143 and y = −157.

1.14 By the Euclidean Algorithm, note that

1691 = 1349 × 1 + 342

1349 = 342 × 3 + 323

342 = 323 × 1 + 19

323 = 19 × 17 + 0.

Therefore, gcd(1691, 1349) = 19, and it is impossible for a linear combination of

1691 and 1349 to be equal to 1.

1.15 Note that the pair (x, y) = (−5, 2) satisﬁes the equation. The problem asks

to ﬁnd all integers x, y, therefore, we need to parameterize it. If (x

, y

) is a

solution, then so is (x

+ 13, y

− 5) since

5(x

+ 13) + 13(y

− 5) = 5x

+ 13y

+ (65 − 65) = 1.

Therefore, for integer t, all solutions (x, y) are characterized by (−5 + 13t, 2 −5t) .

Justin Stevens 123

1.16 Note that

− 1 = (n − 1)



k−1

+ n

k−2

+ ··· + n + 1



Therefore,

(n − 1)

| n

− 1 ⇐⇒ (n − 1) |



k−1

+ n

k−2

+ ··· + n + 1



Furthermore, since n ≡ 1 (mod n − 1), we have

k−1

+ n

k−2

+ ··· + n + 1 ≡ 1

k−1

+ 1

k−2

+ ··· + 1 + 1 ≡ k (mod n − 1).

Therefore, (n − 1) | k.

1.17 Assume for the sake of contradiction that

√

2 is rational. Therefore, for

relatively prime integers m, n, we have

√

2 =

. Multiply by n on both sides and

square in order to get

= 2n

Since the right hand side is a multiple of 2, the left hand side must be also,

therefore 2 | m. For some integer m

, set m = 2m

(2m

)

= 2n

=⇒ 2m

= n

By similar logic, the left hand side is a multiple of 2, therefore the right hand

side must be, therefore 2 | n. However, this contradicts the initial assumption

that

was in lowest terms, since 2 divides both the numerator and denominator.

Therefore, we have arrived at a contradiction and are done.

1.18 Assume for the sake of contradiction that log

(2) is rational. Therefore,

for relatively prime integers m, n, we must have log

(2) =

. Rewriting this

equation, we see that it is equivalent to

= 10.

Taking everything to the power of n gives 2

= 10

. Note that 10

= 2

therefore, the equation becomes 2

= 2

. However, this is a contradiction of

the Fundamental Theorem of Arithmetic, because the right side has a prime factor

of 5 and the left side does not.

1.19 We begin by prime factorizing 2004: 2004 = 2

·3·167. Therefore, 2004

2004

4008

· 3

2004

· 167

2004

. Hence, any divisor of 2004

2004

will take on the form m =

167

. If the divisor m has exactly 2004 positive integers, then this is equivalent

τ(m) = (a + 1) (b + 1) (c + 1) = 2004 = 2

· 3 · 167.

124

We consider the set {a + 1, b + 1, c + 1}. We begin by ﬁguring out how to place

the factors of 167 into the set. We can either give the factor of 167 to a + 1, b + 1,

or c + 1, for a total of 3 choices.

Similarly, for the factor of 3, we have a total of 3 choices. On the other hand,

for the factor of 2, this is equivalent to placing 2 indistinguishable objects (factors

of 2) into 3 bins. Using the method of stars of bars, this can be done in



2+3−1

2−1



= 6

ways. Another way to verify this would be simple casework on the powers of 2 in

{a + 1, b + 1, c + 1}: (2, 0, 0), (0, 2, 0), (0, 0, 2), (1, 1, 0), (1, 0, 1), (0, 1, 1).

In conclusion, there are 3 ·3 ·6 = 54 positive integer divisors of 2004

2004

that

are divisible by 2004 positive integers.

1.20 We proceed with the Euclidean Algorithm over the rationals:

− 1 = (5x

− 1)





− 1

(5x

− 1) =



− 1



(25x + 125) + 124

1 =

− 1

124

−



− 1





124

x +

125

124



1 =

− 1

124

−



− 1 −



− 1





124

x +

125

124



1 =



− 1





124



124

x +

125

124



−



− 1





124

x +

125

124



1 =



− 1





124

x +

124



−



− 1





124

x +

125

124



Therefore,

u(x) =

124

x +

124

and v(x) =

−25x

124

−

125

124

1.21 We begin by applying the division algorithm repeatedly.

− 1 = (x

− 1)x

+ x

− 1

− 1 = (x

− 1)x

+ x

− 1

− 1 = (x

− 1)x + x − 1

− 1 = (x − 1)x + 1.

Justin Stevens 125

We then reverse the order of the division algorithm as follows:

x − 1 = x

− 1 − (x

− 1)x

= x

− 1 −



− 1 − (x

− 1)x





− 1



1 + x



−



− 1





− 1 − (x

− 1)x



1 + x



−



− 1





− 1



1 + x





− 1



−x

− x



Hence, polynomials that satisfy the above condition are u(x) = 1 + x

and

v(x) = −x

− x

− x .

1.22 I claim the answer to be yes. Note that by the 1.1.5, we have

gcd(x

− 1, x

− 1) = x

gcd(m,n)

− 1 = x − 1,

since it is given in the problem statement that m and n are relatively prime.

Therefore, using Bezout’s Theorem for polynomials, there does indeed exist u, v ∈

Q[x] such that (x

− 1)u(x) + (x

− 1)v(x) = gcd(x

− 1, x

− 1) = x − 1. In

order to ﬁnd such polynomials, one should follow the method used in the above

problem.

1.23 Assume for the sake of contradiction that there exists positive integers a, b

for which the above equation was true. Let gcd(a, b) = d. Now, set a = da

and

b = db

and substitute these into the equation above to get

− b

) | d

+ b

) =⇒ a

− b

| a

+ b

Now, we know that gcd(a

, b

) = 1. However, if the above equation is true, then

we must also have

− b

| (a

+ b

) + (a

− b

) = 2a

− b

| (a

+ b

) − (a

− b

) = 2b

If a

− b

divides both 2a

and 2b

, it must then divide their greatest common

divisor:

− b

| gcd(2a

, 2b

) = 2.

Since n > 1, we know that a

− b

6= 1, 2, leading to a contradiction.

1.24 Note that the greatest common divisor of the ﬁrst two terms must divide

the entire result. Therefore, we calculate it as follows:

gcd(2002 + 2, 2002

+ 2) = gcd



2002 + 2, 2002

+ 2 − (2002 + 2) (2002 −2)



= gcd



2002 + 2, 2002

+ 2 −



2002

− 4



= gcd (2002 + 2, 6)

= 6.

126

Therefore, the greatest common divisor of the sequence must divide 6. We now

prove that 6 divides every term in the sequence. Clearly, every term in the se-

quence is even, and furthermore, since 2002 ≡ 1 (mod 3), we have

2002

+ 2 ≡ 1

+ 2 ≡ 0 (mod 3).

Therefore, the answer is 6 .

1.25

gcd(n! + 1, (n + 1)!) = gcd(n! + 1, (n + 1)! − (n + 1)(n! + 1))

= gcd(n! + 1, −(n + 1))

= gcd(n! + 1, n + 1).

Let p be a prime divisor of n + 1. Unless n + 1 is prime, we have

p ≤ n =⇒ n! + 1 ≡ 1 (mod p).

When n + 1 is prime, we have n! + 1 ≡ 0 (mod n + 1) (this fact will later be

proved in the Wilson’s theorem section). Therefore, the answer is

gcd(n! + 1, (n + 1)!) =

(

1 if n + 1 is composite

n + 1 if n + 1 is prime

1.26

gcd(2

− 2, 2

− 2) = 2

gcd(30

−1,30

−1)

− 1

= 2

gcd(10,45)−1

− 1

= 2



−1

− 1



= 2

− 2.

Therefore, x = 30

1.27 We begin by using the formula for the sum of squares to rewrite the sum:

+ 3

+ ··· + n



+ 2

+ 3

+ ··· + n



− 1

n(n + 1)(2n + 1)

− 1

+ 3n

+ n − 6

(n − 1)(2n

+ 5n + 6)

Justin Stevens 127

We want to determine when this expression equals p

for some prime p. We begin

by computing the greatest common divisor of n − 1 and 2n

+ 5n + 6. Note that

+ 5n + 6 = (n − 1)(2n + 7) + 13.

Therefore, gcd(2n

+5n+ 6, n −1) = gcd(13, n −1). Hence, n−1 and 2n

+5n+ 6

can share no common divisors other than 13.

Hence, besides for a few special cases, there will be more than one prime that

divides into the expression

(n − 1)(2n

+ 5n + 6)

. The exception cases are when

n − 1 divides into the denominator, 6. We therefore check n = 2, 3, 4, 7.

• When n = 2, then

(n−1)(2n

+5n+6)

= 4 = 2

• When n = 3, then

(n−1)(2n

+5n+6)

= 13.

• When n = 4, then

(n−1)(2n

+5n+6)

= 29.

• When n = 7, then

(n−1)(2n

+5n+6)

= 139.

All of the numbers above are of the form p

, hence, the answer is n = 2, 3, 4, 7 .

1.28 First oﬀ, WLOG let m > n. Then we have

+ 1 | a

n+1

− 1 | a

− 1.

The last step follows from the fact that 2

n+1

| 2

Let a

− 1 = q(a

+ 1). Therefore,



− 1



= q(a

+ 1) − 2.

By the Euclidean Algorithm,

gcd(a

− 1, a

+ 1) = gcd(a

+ 1, −2) =

(

1 if a is even

2 if a is odd

1.29 Assume for the sake of contradiction that 2

− 1 | 2

+ 1. We obviously

have a > b, so write a = bq + r using the division algorithm. We must have

gcd(2

− 1, 2

+ 1) = 2

− 1. We then have

gcd(2

− 1, 2

+ 1) = gcd(2

− 1, 2

+ 1 + 2

− 1)

= gcd(2

− 1, 2



a−b

+ 1



= gcd(2

− 1, 2

a−b

+ 1).

Repeating this process, we arrive at

gcd(2

− 1, 2

+ 1) = gcd(2

− 1, 2

a−qb

+ 1) = gcd(2

− 1, 2

+ 1).

Since r < b, we have 2

+ 1 ≤ 2

b−1

+ 1 < 2

− 1 for a, b > 2.

1.30 [Outline] Use induction and the factorization x

−x

−x+ 1 =

(x + 1)

− 7x(x

+ x + 1)

Bibliography

[1] Burton, David M. Elementary Number Theory. Boston: Allyn and Bacon,

1976. Print.

[2] ”104 Number Theory Problems: From the Training of the USA IMO Team

[Paperback].” Amazon.com: 104 Number Theory Problems: From the Train-

ing of the USA IMO Team (9780817645274): Titu Andreescu, Dorin Andrica,

Zuming Feng: Books. N.p., n.d. Web. 01 Aug. 2013.

[3] Andreescu, Titu, and D. Andrica. Number Theory: Structures, Examples, and

Problems. Boston, MA: Birkhuser, 2009. Print.

[4] Problems of Number Theory in Mathematial Competitions by Yu Hong-Bing

[5] http://yufeizhao.com/olympiad/mod2.pdf

[6] http://aopswootblog.wordpress.com/2013/03/09/

number-theory-4-using-appropriate-moduli-to-solve-exponential-diophantine-equations/

[7] http://projectpen.files.wordpress.com/2008/10/pen-vol-i-no-1.

pdf

[8] http://blogs.sch.gr/sotskot/files/2011/01/Vieta_Jumping.pdf

[9] http://www.uwyo.edu/moorhouse/courses/3200/division_algorithm.

pdf

[10] http://math.stanford.edu/

paquin/Notes.pdf

[11] Art of Problem Solving 2012-2013 WOOT Diophantine Equations Handout

[12] http://www.artofproblemsolving.com/Wiki/index.php/Fermat_number

[13] http://www.math-olympiad.com/35th-canadian-mathematical-olympiad-2003.

htm#2

128

Justin Stevens 129

[14] http://www.artofproblemsolving.com/Forum/viewtopic.php?f=721&t=

542072

[15] http://www.artofproblemsolving.com/Forum/viewtopic.php?t=42703

[16] http://www.artofproblemsolving.com/Wiki/index.php/2005_USAMO_

Problems/Problem_2