Number Theory IMOTC 2013 Divisibility and congruences

These are some notes (written by Tejaswi Navilarekallu) used at the International Mathematical
Olympiad Training Camp (IMOTC) 2013 held in Mumbai during April-May, 2013.
1 Divisibility and congruences
Denition 1.1. Given integers a and b, we say that a divides b if there exists an integer m such that
b = am. We also say that a is a divisor (or a factor) of b. We write a | b.
Denition 1.2. A positive integer p is called a prime number if it has exactly two positive divisors
(namely 1 and itself ). A composite number is an integer n > 1 that is not a prime.
Here are some properties.
If a | b then a | bc.
If a | b and b | c then a | c.
If a | b and a | c then a | (b c).
If a | b and a | c then a
2
| bc.
If a | b then a
k
| b
k
.
By the denition of prime number it is easy to prove the following:
Proposition 1.3. If n > 1 is an integer then n has a prime divisor.
Proof. By induction. If n is a prime then we are done. Otherwise, let m be a divisor of n, with m = 1, n.
Then 1 < m < n. So, by induction m has a prime divisor p. It is easy to see that p divides n.
Corollary 1.4. There innitely many prime numbers.
Proof. If p
1
, . . . , p
k
are all the primes, then let n = p
1
p
2
p
k
+ 1. Then, by the above proposition we
get a prime factor p of n, which will have to equal one of the p
i
s. This gives a contradiction.
The following are two very important results in number theory.
Theorem 1.5. If p is a prime number, a and b are integers such that p divides ab then p divides a or
p divides b.
Theorem 1.6 (Fundamental theorem of arithmetic). Every integer n > 1 can be uniquely written as
n = p

1
1
p

2
2
p

k
k
where p
1
< p
2
< < p
k
are primes and
i
s are positive integers.
Denition 1.7. The greatest common divisor of two positive integers m and n is dened as the highest
integer that divides both m and n. We denote this by gcd(m, n) or by just (m, n). We say that two
integers m and n are coprime to each other if their gcd is 1.
Denition 1.8. The least common multiple of two positive integers m and n is dened as the smallest
integer that is divisible by both m and n. We denote this by lcm(m, n).
1
Number Theory IMOTC 2013 Divisibility and congruences
Example. Common factors (or the lack thereof) between variables is something to look for in number
theory problems. For example, consider the equation
x
2
+ y
2
= z
2
, (1.9)
with x, y, z being positive integers. If d = (x, y, z) then (x/d)
2
+(y/d)
2
= (z/d)
2
and (x/d, y/d, z/d) = 1.
In other words, all the solutions to (1.9) can be obtained by primitive solutions, i.e., solutions in which
(x, y, z) = 1. For a primitive solution, we note that one of x and y has to be odd, and the other even.
Without loss of generality we suppose that y is even. We can then rewrite (1.9) as
x
2
= (z
2
y
2
) = (z y)(z + y) .
Note that one in fact has (y, z) = 1 for primitive solutions, and since z is odd it follows that (z+y, zy) =
1. It follows then that both z + y and z y have to be squares (of odd coprime integers). Thus any
primitive solution to (1.9) is given by

rs,
r
2
s
2
2
,
r
2
+s
2
2

for some odd coprime integers r > s.

Here are some properties of greatest common divisors which are often useful:
(m, n) = (m, rm + n) for any integer r.
If d = (m, n) then there are integers x and y such that mx + ny = d.
If m | ab and (m, a) = 1 then m | b.
If m | a, n | a and (m, n) = 1 then mn | a.
Before going further, we introduce the notion of congruences. The theory of congruences is essentially
a notational simplication of the divisibility properties.
Denition 1.10. For integers a, b and m, we say that a is congruent to b modulo n if n divides (a b).
We write
a b (mod n).
The idea is to get a good handle on the remainder obtained when a is divided by n. The basic
properties of divisibility mentioned in the earlier section can be translated in congruence notation as
follows. Let a b (mod n) and c d (mod n). Then
b a (mod n).
If b e (mod n) then a e (mod n).
a c b d (mod n).
ac bd (mod n).
a
k
b
k
(mod n).
Proposition 1.11. Let a and n be integers with (a, n) = 1. Then
(a) there is an integer b such that ab 1 (mod n); and,
(b) there is a positive integer k such that a
k
1 (mod n).
Proof. (a) Since (a, n) = 1 we have from the properties of gcds that there exists integers b and c such
that ab + nc = 1 and hence ab 1 (mod n).
(b) Consider {1, a, a
2
, . . . , a
n+1
}. Since there are only n possible remainders modulo n it follows that at
least two elements in this set are congruent modulo n, and hence we get a
k
1 (mod n) for some k.
2
Number Theory IMOTC 2013 Divisibility and congruences
Theorem 1.12 (Chinese remainder theorem). Let m, n be positive integers with (m, n) = 1 and let a, b
be integers. Then there is a unique integer x
0
such that 0 x
0
mn 1, x
0
a (mod m) and x
0
b
(mod n). Morevoer, any x which satises x a (mod m) and x b (mod n) equals x
0
+kmn for some
integer k.
Proof. Let 0 a
0
m be such that a a
0
(mod m). Consider the set {a
0
, a
0
+ m, a
0
+ 2m, . . . , a
0
+
mn m}. Since (m, n) = 1 it follows that no two elements from this set leave same remainder when
divided by n. Therefore there is a unique q with 0 q n 1 such that x
0
= a
0
+ qm b (mod n).
The second part of the theorem follows from the uniqueness of x
0
.
Denition 1.13 (Eulers totient function). For a natural number n we denote by (n) the number of
integers between 1 and n (both inclusive) that are coprime to n.
Let S
n
denote the set {1, 2, . . . , n} and T
n
= {a|1 a n, (a, n) = 1} S
n
. Then by denition we
have (n) = |T
n
|. We shall think of elements of these sets as remainders when integers are divided
by n. Therefore we distinguish between elements in T
m
and T
n
for m = n.
Proposition 1.14. The function from the set of natural numbers to itself is multiplicative, i.e., if m
and n are coprime positive integers then (mn) = (m)(n).
Proof. Consider the map f : T
mn
T
m
T
n
dened by a ( a, a), where the image of a in T
m
(and T
n
,
respectively) is the remainder when a is divided by m (resp. n). Given remainders c and d modulo m and
n, respectively, by Chinese remainder theorem it follows that the equations x c (mod m) and x d
(mod n) have a unique solution modulo mn. This shows that f is a bijection and hence the result.
Theorem 1.15. If n = p

1
1
p

2
2
p

k
k
with p
1
, p
2
, . . . , p
k
distinct primes and
1
,
2
, . . . ,
k
positive
integers then
(n) = n

1
1
p
1

1
1
p
2

1
1
p
k

.
Proof. Both the sides in the statement of the theorem are multiplicative, and therefore it is enough to
prove the result when n is a power of prime. If n = p

then (n) = p

p
1
= n

1
1
p

, and hence
the theorem follows.
There are many identities involving the totient function that are not dicult to prove. We give here
one example which is motivated by the study of cyclotomic polynomials.
Proposition 1.16. For a positive integer n one has

d|n
(d) = n.
We rst prove a useful lemma.
Lemma 1.17. Let f be a multiplicative function from the set of positive integers to itself. Dene
F(n) =

d|n
f(d). Then F is also multiplicative.
Proof. Suppose that m, n are positive integers such that (m, n) = 1. Then
F(mn) =

d|mn
f(d) =

d
1
|m,d
2
|n
f(d
1
d
2
)
=

d
1
|m

d
2
|n
f(d
1
)f(d
2
) =

d
1
|m
f(d
1
)F(n) = F(m)F(n) .
3
Number Theory IMOTC 2013 Divisibility and congruences
Proof of Proposition 1.16. From the previous lemma it follows that both the sides of the required identity
are multiplicative functions. Therefore it is enough to prove the result for prime powers. If n = p

then
the left-hand side equals

d|p

(d) = 1 +

k=1
(p
k
p
k1
) = p

.
Remark. One of the motivations for studying Eulers totient function comes from the theory of cyclo-
tomic elds. Let n be a positive integer. While solving certain diophantine equations, it is handy to have
a factorisation of the polynomial x
n
1 into polynomials with integer coecients. For example, when
we looked the solutions to Pythagoras equation, the we used the factorisation of the polynomial x
2
1.
The polynomial F
n
(x) = x
n
1 has exactly n distinct complex roots. In fact, if
n
= e
2i/n
then
{
r
n
}
0rn1
is the set of all roots. Similar to the notion of order modulo an integer, we can dene the
order of a root
r
n
of unity as the least positive integer k such that (
r
n
)
k
= 1. In particular, the order of

n
is n.
It then follows that for any d dividing n, there are exactly (d) roots of order d. This gives the identity

d|n
(d) = n. Dene
d
(x) =

(x ), where the product runs over all the roots of x

n
1 = 0 of
order d. Then
d
(x) is a polynomial of degree (d), and in fact, it is irreducible and all its coecients
are integers (why?). Moreover,
d
(x) is independent of n. This polynomial is called the d-th cyclotomic
polynomial.
Here are some identities left as an exercise for the reader.
Exercise 1.18. Prove that

1kn,(k,n)=1
k =
n(n)
2
.
Exercise 1.19. Find a closed expression in terms of n and its prime factorisation for the number of
integers k between 1 and n such that (k, n) = (k 1, n) = 1.
Exercise 1.20. Find a closed expression in terms of n and its prime factorisation for sum of integers
k between 1 and n such that (k, n) = (k 1, n) = 1.
There are also many conjectures related to the totient function. Here are two examples.
Conjecture 1.21. For a positive integer n, if (n) divides n 1 then n is a prime.
Conjecture 1.22. For a positive integer n, if n divides (n)d(n) + 2, where d(n) is the number of
positive divisors of n.
We now state some of the very powerful results.
Theorem 1.23 (Wilsons Theorem). If p is a prime then (p 1)! 1 (mod p).
Theorem 1.24 (Fermats little theorem). Let p be a prime number and a be an integer. Then a
p
a
(mod p). Equivalently, if p a then a
p1
1 (mod p).
Theorem 1.25. Let n be a positive integer and a an integer such that (a, n) = 1. Then a
(n)
1
(mod n).
Squares play an important role in analysing the properties of integer solutions to diophantine equa-
tions. (We have already seen this while looking at the solutions to Pythagoras equation.) Therefore
it is good to know and keep track of properties of squares. In particular, it is very useful to know the
following simple results.
4
Number Theory IMOTC 2013 Problems
If n
2
= ab and (a, b) = 1 then a and b are squares.
If n is not divisible by 3 then n
2
1 (mod 3).
If n is odd then n
2
1 (mod 4) and in fact, n
2
1 (mod 8).
If p is a prime, then the equation x
2
a (mod p) has a solution for precisly (p + 1)/2 values of a
with 0 a p 1.
Slightly more non-trivial results are below.
Theorem 1.26. Let n be an integer and let p be a prime dividing n
2
+ 1. Then either p = 2 or p 1
(mod 4). Conversely, if p = 2 or p 1 (mod 4) then there exists an integer n such that p divides n
2
+1.
Theorem 1.27. If p = 2 or p 1 (mod 4) then there exists integers a and b such that p = a
2
+ b
2
.
Denition 1.28. If (a, n) = 1, then the smallest positive integer k such that a
k
1 (mod n) is called
the order of a modulo n, and is denoted by o
n
(a).
The importance of orders is somewhat apparent from the following result.
Theorem 1.29. Let n be a positive integer and a an integer such that (a, n) = 1. If a
d
1 (mod n)
then o
n
(a) divides k. In particular, o
n
(a) divides (n).
Example. Suppose that p is a prime dividing a
2
+ 1, or in other words a
2
1 (mod p). Squaring
both the sides we get a
4
1 (mod p). Therefore o
p
(a) divides 4, but does not divide 2. This proves
that o
p
(a) = 4 and hence 4 divides p 1.
Example. Let a, b be relatively prime positive integers. Let p be a prime dividing a
6
n
+ b
6
n
. Then
a
6
n
+b
6
n
0 (mod p). Note that (a, b) = 1 implies that (a, p) = (b, p) = 1. Therefore b has an inverse
modulo p, i.e., there exists c such that bc 1 (mod p). We therefore get (ac)
6
n
(bc)
6
n
1
(mod p). Squaring we get (ac)
26
n
1 (mod p). Therefore o
p
(ac) divides 2 6
n
and does not divide 6
n
.
This shows that o
p
(ac) = 2
n+1
d for some odd integer d. Since o
p
(ac) divides p 1 it follows that p 1
(mod 2
n+1
).
There are a few reasons why orders are important: (a) if something is congruent to one modulo n then
its k-th power is also congruent to one modulo n; (b) if a
k
1 (mod n) then a
k1
is the multiplicative
inverse of a modulo n; (c) if a
k
1 (mod n) then v
2
((n)) v
2
(k) + 1 where v
q
(m) denotes the
exponent of q dividing m.
2 Problems
When dealing with a diophantine equation, there are few systematic steps that one can go through to
get a better idea of the problem.
To start with, if possible, nd any small solution by plugging in small values. If there exists a
solution, and you expect only nitely many solutions, then you cannot get a contradition unless
you assume something more about the variables.
Identify the possible parities of all the variables.
5
Number Theory IMOTC 2013 Problems
Try to rearrange the terms so that both the sides are nice. The following are nice to have in an
equation:
factorisable polynomials;
squares or higher powers;
sum of two squares (and in particular n
2
+ 1 for some integer n).
Consider the equations modulo small primes.
Look for the properties of the prime divisors of each side of the (rearranged) equation.
Example. Consider the equation y
2
= x
3
+7. We would like to nd all integer solutions to this equation.
To start with, we plug is small values of x and y to see if there are any simple solutions, and nd
that there are are no small solutions.
We next consider the parity of x and y. Clearly, they have to be of opposite parity. Also, if x is
even then x
2
+ 7 3 (mod 4) while y
2
1 (mod 4). Hence x is odd and y is even.
Now we try to manipulate the equation to get nice terms on both the sides. Even though y
2
is nice
x
3
+ 7 is not-so-nice, so there is need of manipulation. Note that adding 1 to both the sides make
them nice since we will have sum of two squares on the left-hand side and a factorisable polynomial
on the right-hand side. So we rewrite the equation as
y
2
+ 1 = (x + 2)(x
2
2x + 4) .
The prime divisors of left-hand side have special property, and therefore all the prime divisors of
the right-hand side should also have the same property. That is, if a prime p divides the right-hand
side then p 1 (mod 4). In particular, this implies that x
2
2x + 4 1 (mod 4). But since x is
odd, x
2
2x + 4 = (x 1)
2
+ 3 3 (mod 4). Hence we have a contradition.
We have thus shown that there are no solutions to the given equation.
1. Find all pairs (x, y) of positive integers such that y
2
= x
3
+ 7.
2. Find all pairs (m, n) of positive integers such that 2
m
+ 3
n
is a square.
3. Find all pairs (m, n) of positive integers such that 2
m
+ 3 = 11
n
.
4. Find all primes p such that (2
p1
1)/p is a square.
5. Find all positive integers m and n such that 2
n
1 divides m
2
+ 9.
6. Find all positive integers m and n such that m
2
+ n
2
is a prime and it divides m
3
+ n
3
4.
7. Find all pairs (x, y) of positive integers such that
x
7
1
x1
= y
5
1.
8. For a positive integer n let f(n) denote the smallest positive integer k such that n divides 1 + 2 +
+ k. Find all positive integers n such that f(n) = 2n 1.
9. Given an integer k 2, prove that there innitely many positive integers n such that 2
2
n
+ k is
composite.
6