1.

NUMBER OF FACTORS

Properties:
Let the prime factorization of a number n is n  p1a1 p a22 ...p ka k where pi, i = 1, 2... k are distinct primes,
then
 The number of factors of n is T(n)  1  a1 1  a 2  ... 1  a k 
T(n )
 The product of all factors of n is n 2

k k pia1 1  1

i 1
 
The sum of all factors of n is Sd   1  pi  pi2  ...piai  
i 1 pi  1
Sd
 The sum of reciprocals of all factors of n is
n
Corollary 1
T is multiplicative function. That is for any integers a, b such that HCF (a, b) = 1,
we have T(ab) = T(a)T(b)

Corollary 2
For any positive integer n
T(n)  2 n
Proof : Let d1 < d2 < … < dk be the divisors of n not exceeding n . The remaining divisors are
n n n
, ,... . It follows that
d1 d 2 d k
T(n)  2k  2 n

Applications 1
1. Find the number of factors of 3600.

2. Find the number of factors of 72000 that are divisible (a) by 25 (b) by 100

3. Find the number of the factors of 31500 that are

(a) divisible by 35
(b) not divisible by 9
(c) not divisible by 45
(d) divisible by 45 but not by100

4. Find the number of factors of 4800 that are of form 4k + 2.

5. Find the smallest number with (a) 5 factors (b) 12 factors.

6. Find the sum of even positive divisors of 10000.

7. Find the sum of reciprocal of factors of 420.

8. Find the sum of all positive two-digit integers that are divisible by each of their digits. .

9. [AMC12A 2002] Some sets of prime numbers, such as {7, 83, 421, 659}, use each of the nine
nonzero digits exactly once. What is the smallest possible sum such a set of primes can have?
2 DIVISIBILITY
For an integer m and a nonzero integer n, we say that m is divisible by n or n divides m if there is an
m
integer k such that m = kn; that is, is an integer. We denote this by n|m. If m is divisible by n,
n
then m is called a multiple of n; and n is called a divisor (or factor) of m.
Because 0 = 0 · n, it follows that n|0 for all integers n. For a fixed integer n, the multiples of m are 0,
±n, ±2n, .... Hence it is not difficult to see that there is a multiple of n among every n consecutive
integers. If m is not divisible by n, then we write n | m. (Note that 0 | m for all nonzero integers m,
since m = 0 = k · 0 for all integers k.)
For a prime p we say that pk fully divides n and write pk||n if k is the greatest positive integer such
that pk|n.

Properties
Let x, y, and z be integers. We have the following basic properties:
(a) x|x (reflexivity property);
(b) If x|y and y|z, then x|z (transitivity property);
(c) If x|y and y  0, then |x|  |y|;
(d) If x|y and x|z, then x|y + z for any integers  and ; ie if x|y, then, x|y for any integers  .
(e) If x|y and x|y ± z, then x|z;
(f) If x|y and y|x, then |x| = |y|; ie, x = ±y
y
(g) If x|y and y  0, then | y ;
x
(h) For z  0, x|y if and only if xz|yz.
y y
(i) All the divisors of y appear in pairs, namely, x and (observe that x  if y is not a perfect
x x
square). Hence the number of divisors of n are odd iff n is a perfect square.

Applications 2
1. Prove that (n+1)! + 1 has no prime factor less than n. Does this mean that (n + 1)! + 1 is prime
n  N?

2. Find least positive value of a + b where a, b are positive integers such that11|a + 13b and 13|a + 11b

3. Find the number of pairs of natural numbers (m, n) such that

m
(a) 0   1 (b) gcd (m, n) = 1 (c) mn = 25! (RMO 1994)
n

4. Find all 6 digit natural numbers a 1 , a 2 , a 3 , a 4 , a 5 , a 6 using digits 1, 2, 3, 4, 5, 6 such that for each k =
1, …, 6 we have k | a 1 , a 2 ...a k (RMO)

5. (i) Consider two positive integers a and b such that 2000 | a a b b . What is the least value of product ab.
(ii) Consider two positive integers a and b such that 2000 a b b a . What is the least value of product ab.

3. PARITY
The set of integers, denoted by Z, can be partitioned into two subsets, the set of odd integers and the
set of even integers: {±1, ±3, ±5, ...} and {0, ±2, ±4, ...}, respectively. Although the concepts of odd
and even integers appear straight-forward, they come handy in tackling various number-theoretic
problems.
 Properties
 An odd number is of the form 2k + 1,or 2k − 1 for some integer k;
 An even number is of the form 2m, for some integer m;
 The sum of two odd numbers is an even number;
 The sum of two even numbers is an even number;
 The sum of an odd and an even number is an odd number;
 The product of two odd numbers is an odd number;
 The product of integers is even if and only if at least one of its factors is even.
 For any integers a, b the parity of a + b and a − b is the same.
 The product of two consecutive integers is always even.
 One of the two consecutive even numbers is divisible by 4. The product of two consecutive even
integers is always divisible by 8.

Applications 3
1. Let n be an integer greater than 1. Prove that
(a) 2n is the sum of two odd consecutive integers;
(b) 3n is the sum of three consecutive integers.

2. Let k be an even number. Is it possible to write 1 as the sum of the reciprocals of k odd integers?

3. [HMMT 2004] Zach has chosen five numbers from the set 1, 2, 3, 4, 5, 6, 7. If he told Claudia what
the product of the chosen numbers was, that would not be enough information for Claudia to figure
out whether the sum of the chosen numbers was even or odd. What is the product of the chosen
number.

4. MODULAR ARITHMETIC
Let a, b, and m be integers, with m  0. We say that a and b are congruent modulo m if m divides
a − b. We denote this by a  b (mod m). The relation “  ” on the set Z of integers is called the
congruence relation. If m does not divide a − b, then we say that integers a and b are not congruent
modulo m and we write a  b (mod m).

Properties
 a  a (mod m) (reflexivity).
 If a  b (mod m) and b  c (mod m), then a  c (mod m) (transitivity).
 If a  b (mod m), then b  a (mod m).
 If a  b (mod m) and c  d (mod m), then a + c  b + d (mod m) and a − c  b − d (mod m)
 If a  b (mod m), then for any integer k, ka  kb(mod m).
 If a  b (mod m) and c  d (mod m), then ac  bd (mod m).
 In general, if ai  bi (mod m), i = 1, ... , k, then a1 … ak  b1 … bk (mod m).
 In particular, if a  b (mod m), then for any positive integer k, ak  bk (mod m).
 We have a  b (mod mi), i = 1, ...,k, if and only if a  b (mod lcm(m1, ...,mk)).
 In particular, if m1, ...,mk are pair wise relatively prime, then a  b (mod mi), i = 1, ..., k, if
and only if a  b (mod m1… mk ).
a b
 If a  b (mod m) and d|a, d|b and gcd(d, m) = 1, then  (mod m)
d d
a b m
 If a  b (mod m) and d|a, d|b and gcd(d, m) = k, then  (mod )
d d k
 Some useful facts
 x2  0, 1(mod 3)  0, 1(mod 4)  0,±1(mod 5)  0, 1, 3, 4 (mod 6)  0, 1, 2, 4(mod 7)  0, 1,
4, (mod 8)  0, 1, 4, 7(mod 9)
 x3  0, ±1(mod 3)  0, ±1(mod 4)  0, ±1, ±2(mod 5)  0, ±1, ±2, 3(mod 6)  0, ±1(mod7) 
0, ±1,±3(mod 8)  0, ±1(mod 9)
 x4  0, 1(mod 3)  0, 1(mod 4)  0, 1, (mod 5)  0, 1, 4(mod 6)  0, 1, 2, 4, (mod7)  0,
1(mod 8)  0, 1, 4, 7(mod 9)
 x3  x (mod 6)
 x5  x (mod 5)
 x4  1, 0(mod16)

Applications 4
1. Find the remainder when 1989 · 1990 · 1991+19923 is divided by 7.

2. Find the reminder when 9123456789 is divided by 8.

3. Find the reminder when 7123456789 is divided by 8.

4. Prove that 255 + 1 is divisible by 11

5. Find the reminder when 7101 is divided by 25.

6. Find the reminder when 4976 is divided by 13.

7. Determine the last 2 digits of the number 7999

7
8. Determine the last two digits of the number 7 7

5. DECIMAL REPRESENTATION AND DIVISIBILITY TESTS

Let a n a n 1...a 0  a n .10 n  a n 1.10n 1  ....  a 0 be the decimal representation of the number
a n a n 1 ....a 0
 a n a n 1 ...a 0  a n  a n 1  ....  a 0  mod 3 
 a n a n 1 ...a 0  a n  a n 1  ....a 0  mod 9 
 a n a n 1 ...a 0  a 1a 0  10a 1  a 0  2a 1  a 0  mod 4 
 a n a n 1 ...a 0  a 2 a 1a 0  100a 2  10a 1  a 0  4a 2  2a 1  a 0  mod 8 
 a n a n 1...a 0  a k 1...a1a 0  mod 2k 
n
 a n a n 1...a 0  a 0  a1  a 2  a 3 ...   1 a n  mod11 (alternating sum)
 a n a n 1....a 0  ....  a 5a 4 a 3  a 5 a 4 a 3  a 2 a1a 0 (mod 7 or 11 or 13)
 a n a n 1 ...a 0  ...  a 5 a 4 a 3  a 5 a 4 a 3  a 2 a1a 0 (mod 27 or 37)

Applications 5
1. State and prove the divisibility tests for 2 n and 5n

2. The integer n is the smallest positive multiple of 15 such that every digit of n is either 0 or 8. Find n.

3. Let N  a n a n 1...a 0 , M  a 0  4a1  4a 2 .  ...  4a n then, prove that 6 | N iff 6 | M

4. Determine the number of five-digit positive integers abcde (a, b, c, d, and e not necessarily distinct)
such that the sum of the three-digit number abc and the two-digit number de is divisible by 11.

5. Find the smallest natural number n such that it’s decimal representation has 6 as the last digit and if
it’s last digit is shifted to front of the remaining digits and the resulting number is four times the
original number.

6. DIVISION ALGORITHM
Theorem : For any positive integers a and b there exists a unique pair  q, r  of nonnegative integers
such that b  aq  r and 0  r  a. We say that q is the quotient and r the remainder when b is divided
by a.

Applications 6
1. If 36 | n, then find the possible remainders when 48 divides 2 n  12

2. Prove that
(a) x m  a m | x n  a n iff m|n
(b) a m  b m |a n  b n if m| n

7. PRIMES
 The integer p 1 is called a prime (or a prime number) if there is no integer d with d 1 and d  p
such that d|p .
 Any integer n 1 has at least one prime divisor. If n is a prime, then, that prime divisor is n itself.
If n is not a prime, then let a 1 be its least divisor. Then n  ab, where 1  a  b. If a were not a
prime, then a  a1a 2 with 1  a1  a 2  a and a1 |n contradicting the minimality of a.
 An integer n 1 that is not a prime is called composite. If n is a composite integer, then it has a
prime divisor p not exceeding n . Indeed, as above, n  ab, where 1 a  b and a is the least
 divisor of n. Then n  a 2 ; hence a  n . This idea belongs to the ancient Greek mathematician
Eratosthenes. (250BCE).
 Note that all positive even numbers greater than 2 are composite. In other words, 2 is the only
even (and the smallest) prime. All other primes are odd; that is, they are not divisible by 2.
 If p | ab, then p|a or p|b
 If p is prime then, p is irrational.
 Any prime p  3 is of form p  6k  1

The following result by Euclid has been known for more than 2000 years :
Theorem
There are infinitely many primes
Proof : Assume by way of contradiction that there are only a finite number of primes :
p1  p 2  .....  p m . Consider the number P  p1p2 ......pm  1. If P is a prime, then P  p m , contradicting
the maximality of pm . Hence P is composite, and consequently, it has a prime divisor p 1, which is
one of the primes p1 , p 2 ,...., p m , say p k . It follows that p k divides p1...pk ...pm  1. This, together with
the fact that p k divides p1 , p k ,...., p m , implies p k divides 1, a contradiction.
 The Fundamental Theorem of Arithmetic
Any integer n greater than 1 has a unique representation (up to a permutation) as a product of primes.

Corollary (Euclids Lemma)

Let a and b be integers. If a prime p divides ab, then p divides either a or b.

Definition
Let v p  n  be the maximum power of p dividing n. If v p  n   k, then, it is customery to write
pk ||n if p k |n but pk 1 | n .

Applications 7
1. If pi be a prime greater than 3 such that 6| p12  p 22  ....  p n2 then, prove that 6|n

2. Find all primes p, q such that p 2  q 2  1

3. [ARML 2003] Find the largest divisor of 1001001001 that does not exceed 10000.

4. Find the largest n such that 2n ||31024  1

5. Find all positive integers n for which 3n  4, 4n  5, and 5n  3 are all prime numbers.

6. [AHSME 1976] If p and q are primes and x 2  px  q  0 has distinct positive integral roots, find p
and q.

7. Find 20 consecutive composite numbers.

8. Prove that only prime of form n 3  1 is 7

9. Prove that the only prime p for which 3p  1 is a perfect square is p  5

10. Prove that only prime of form n 2  4 is 5

11. If p is a prime, p  5, prove that p 2  2 is a composite number.

8. G.C.D.
For a positive integer k we denote by D k the set of all its positive divisors. It is clear that D k is a
finite set. For positive integers m and n the maximal element in the set Dm  Dn is called the greatest
common divisor (or G.C.D.) of m and n and is denoted by gcd(m, n). In the case Dm  Dn  1, we
have gcd  m, n   1 and we say that m and n are relatively prime (or co-prime).

Definition
The mathematically useful definition of G.C.D is as follows
The G.C.D of the integers a, b is said to be g if, it satisfies following two conditions
 g|a and g|b
If there exists another integer k such that k|a and k|b, then k|g The following are some basic
properties of G.C.D.
 Properties
1. If p is a prime then gcd  p, m   p  if p| m  or gcd  p, m   1  if p | m 
2. If d  gcd  a, b  , then a  da 0 and b  db0 and gcd  a 0 , b 0   1
3. If d  gcd  a, b  and m be any integer such that m | a and m | b then m | d
min x, y 
4. If p x || m and p y || n, then p || gcd  m, n  . Furthermore, if m  p11 .....p kk and
1 k
n  p .....p ,  i ,  i  0, i  1,...., k,
1 k

then gcd  m, n   p1m1 .....p kmk , where mi  min   i , i  i  1,...., k

5. If m  nq  r, then gcd  m, n   gcd  n, r  . Hence
gcd  a, b   gcd  a,  b   gcd  a, b  ax   gcd  a  bx, b  x  Z .
6. For any m  N, gcd  ma, mb   m gcd  a, b 
a b 1
7. If d | a and d | b then gcd  ,   gcd  a,b 
d d d
8. If gcd  a, m   1 and gcd  b, m   1 , then, gcd  ab, m   1
9. If c | ab and gcd  a, c   1, then, c|b
10. If a|c and b|c and gcd  a, b   1, then ab | c
11. If gcd  m, b   1, then, gcd  a, b   gcd  ma, b 

Application 8
1. Show that the gcd  n ! 1, (n  1)! 1  1

2. 
Find the gcd n 2  1,  n  1  1
2

21n  4
3. Prove that is irreducible for any n  N
14n  3

4. 
Find the gcd 2002  2, 20022  2, 20023  2,...... 
5. 
Find the g.c.d of the numbers 213  2,313  3, 413  4,...,1313  13 
9. EUCLIDEAN ALGORITHM
Canonical factorizations help us to determine the greatest common divisors of integers. But it is not
easy to factor numbers, especially large numbers. (This is why we need to study divisibility of
numbers.) A useful algorithm for finding the greatest common divisor of two positive integers m and
n is the Euclidean algorithm. It consists of repeated application of the division algorithm :
m  nq1  r1 ,1  r1  n,
n  r1q 2  r2 ,1 r2  r1 ,....
rk  2  rk 1q k  rk ,1 rk  rk 1 ,.
rk 1  rk q k 1  rk 1 , rk 1  0
This chain of equalities is finite because n  r1  r2  .....  rk . The last nonzero remainder, rk , is the
greatest common divisor of m and n. Indeed, by applying successively property (5) above we obtain
gcd  m, n   gcd  n, r1   gcd  r1 , r2   ....  gcd  rk 1 , rk   rk
 B’ezout’s theorem
Theorem [B’ezout]
For positive integers m and n, there exist integers x and y such that
mx  ny  gcd  m, n  .
Applications 9

1. Find the integers x, y such that

a) gcd  62, 72   62x  72y
b) gcd 119, 272   119x  272 y

2. In a special football game, a team scores 7 points for a touchdown and 3 points for a field goal.
Determine the largest mathematically unreachable number of points scored by a team in an
(infinitely long) game.

3. There is an ample supply of milk in a milk tank. Mr. Fat is given a 5-litre (unmarked) container and a
9-litre (unmarked) container. How can he measure out 2 litres of milk?

10. LCM
For a positive integer k we denote by M k the set of all multiples of k . Then, M k is an infinite set.
For positive integer s and t the minimal element of the set M s  M t is called the least common
multiple of s and t and is denoted by lcm  s , t  or  s, t  .
The mathematically useful definition of L.C.M is as follows

Definition
The L.C.M of the integers a, b is said to be l iff it satisfies following two conditions
 a | l and b | l
 if there exists another integer k such that a | k and b | k , then l / k
Properties
max x , y 
1. If p x || m and p y || n, then p || gcd  m, n . Furthermore, if m  p1 ….. pkk and
1

n  p11 ... pkk ,  i , i  0, i  1,...., k , then lcm  m, n   p1M1 .... pkM k .where
M i  max  ai , i  i  1,...., k
2. If gcd  a, b   g , where a  ga0 and b  gb0 gcd  a0 , b0   1 . , then lcm  a, b   ga0 b0  a.
b0  a0 .b
3. n . lcm  a, b   lcm  na, nb 
The following property establishes an important connection between G.C.D. and L.C.M..
4. For any positive integers m and n the following relation holds: mn  gcd  m, n  . lcm  m, n 
Proof: Let m  p11 .... pkk and n  p11 .... pkk ,  i ,  i  0, i  1,...., k .
From above property 3 we have
gcd  m, n  lcm  m, n   lcm  m, n   p1M1  m1 .... pkM k mk  p11 1 .... pkk k  mn . (Note that this
cannot be easily generalized. For example, it is not true that gcd  a, b, c  lcm  a, b, c   abc .)
Applications 10

1. The GCD of two numbers is same as their difference. Their sum is the square of their GCD and their
LCM is 42 times the GCD, then find the numbers.

2. Prove the following properties for a, b, c positive naturals

(a) If a   pi ai and b   pi bi and mi  min  ai , bi  , M i  max  ai , bi  then prove that
 a, b    pi m  a, b    pi M
i i

(b)  a, b, c   a, b, c   abc, then  a, b    b, c    c, a   1

3. If  a , b   1 then prove that

(a)  a , b   1 for any natural number k .
k k

(b)  a  b, a  b  is 1 or 2
(c)  a  2b, 2a  b  is 1 or 3.
(d)  a  b, a 2
 b2  is 1 or 2
(e)  a  b, a 2
 ab  b2  is 1 or 3
(d)  a  b, ab  is 1

4. Find the least lcm of 20 natural numbers, not necessarily distinct, whose sum is 801.

5. Find all pairs of natural numbers whose sum is 5432 and least common multiple is 223020.

6. Determine the number of ordered pairs of positive integers  a, b  such that lcm  a, b   23571113

7. Prove that the number of ordered pairs of positive integers  a, b  such that
lcm  a, b   n  p1a1 p2a2 .... pkak is  2a1  1 2a2  1 ....  2ak  1

11. FERMAT’S LITTLE THEOREM (1640)

Let a be a positive integer and p be a prime. Then a p  a  mod p  . The cancellation rule tells us that
we can divide by a if gcd  a, p   1, getting gcd  a, p   1  a p 1  1 mod p 
Proof: First proof by induction. The theorem is valid for a  1 , since p |1p  1. Suppose it is valid for
p
some value of a, that is, p | a p  a . We will also show that p |  a  1   a  1 . Indeed,
p  p  p
  a  1  a p     ai  1   a  1  a p  a , since p being prime p |   i  p.
 a  1
i  i 
Second proof with congruence. Now, suppose that gcd  a, p   1 . We form the sequence
S  {a, 2a,3a,...,  p  1 a,}
No two of its terms are congruent (mod) p, since i.a  k .a  mod p   i  k  mod p   i  k
Hence, each of the numbers in S is congruent to exactly one of the numbers 1, 2,3,.... p  1. We get
a  2a  3a   p  1 a  1  2  3   p  1 mod p 
 a p 1 1  2   p  1  1  2   p  1 mod p 
 We may cancel with  p  1 !since  p  1 ! and p are co-prime. Thus,
a p 1  1 mod p 
Third proof by combinatorics.

We have pearls with a colors. From these we make necklaces with exactly p pearls. First, we make a
string of pearls. There are ap different strings. If we throw away the a one-colored strings ap − a
strings will remain. We connect the ends of each string to get necklaces.
We find that two strings that differ only by a cyclic permutation of its pearls result in
indistinguishable necklaces. For p prime, there are p cyclic permutations of p pearls on a string.
Hence the number of distinct necklaces is (ap − a)/p. Because of its interpretation this is an integer.
So p|ap − a.
The converse theorem is not valid. The smallest counterexample is 341|2341− 2, where 341 = 31 · 11
341 340

is not a prime. Indeed, we have 2  2  2 2  1  2 2
10
  
34

134  2  210 1 ...  2.3.341. ... .
Applications 11

1. Find remainders when

(a) 2101 is divided by 101
(b) 3102 is divided by 101
(c) 8900 is divided by 29
(d) 7120 is divided by 143
(e) 33000  1 is divided by 1001
(f) 512345678910111213141516171819 is divided by 11
(g) 1373  143 is divided by 11

2. Prove that
(a) a 21  a  mod15 
(b) a 7  a  mod 42 
(c) a13  a  mod 273
(d) a9  a  mod 5 
(e) 17 |11104  1

3. Can we take square-roots under congruences ? That is does a 2  b 2  mod n   a  b  mod n 

4. If gcd  6, n   1, then prove that 6 | n 2  1

5. If gcd  a, 30   1, then prove that 60 | a 4  59

6. If gcd  a,133  gcd  b,133  1, then, prove that 133 | a18  b18

7. If n is a positive integer not divisible by 5, then, prove that either n 2  1 or n 2  1 is divisible by 5.

12. EULER’S FUNCTION

Euler’s  function is defined as follows: For m  1,   m  number of elements from 1,2,….,m which
are relatively prime to m.
 Properties
1. If p is a prime, then   p   p  1
2.  
If p is a prime, then  p k  p k  p k 1
3. Let a and b be two relatively prime positive integers. Then   ab     a    b 
 1  1   1 
4. If n  p11 . p 2 2 .... p k k , then,   n   n  1    1   ...  1  
 p1   p2   pk 
5.   n  is even integer for n  2

Theorem [Gausss]
For any positive integer n,   d   n
d |n

Proof:
1 2 n
We consider the rational numbers , ,..., . Clearly, there are m are n numbers in the list. We
n n n
obtain a new list by reducing each number in the above list to the lowest terms; that is, express each
fraction as a quotient of relatively prime integers. The denominators of the numbers in the new list
will all be divisors of n. If d | n, exactly   n  of the numbers in the list will have d as their
denominator. (This is the meaning of lowest terms!) Hence, there are
d |   n  in the new list. Because the two lists have the same number of terms, we obtain the
desired result.

Application 12
1. Calculate  1001 ,   5040  ,   36000 

2. If A  {n  N /10 | (n)}, then, prove that A is infinite

3. Find the number of pairs  a, b  of co-prime natural numbers that add up to7200.

4. Find the sum of all natural numbers co-prime to 1000 (less than 1000)

5. Factorize N  3900049, given N is the product of exactly 2 distinct primes and that
  N   3896100

13. EULER’S THEOREM

The Fermat-Euler Theorem is the generalization of Fermat’s theorem where divisor need not be a
 m
prime number. It states that if gcd  a, m   1 , then, a  1 mod m

Applications 13
1. Show that 51|1032 n9  7

2. Find the remainder when 7 200  11800 is divided by 101

3. Find last two digits of 7200  3200

4. Find the reminder when 1992 is divided by 92

5. Find last two digits of 31234

6. Prove last that 1001 | p13600  p23600  .....  p1001

3600
where p i are distinct primes greater than 13.

2  n 1
7. Show that if gcd  a, n   gcd  a  1, n   1, then, 1  a  a  ...  a  0  mod n 

14. WILLSON’S THEOREM

For any integer p,  p  1 !  1 mod p  , iff p is a prime
Hence  p  2  !  1 mod p 
Proof: (a) Necessity: In this part it is given to us that p |  p  1 ! 1
If possible p is not a prime. Let p  ab then a  p 1 and b  p  1 Hence p  ab |  p  1 ! implying
a contradiction.
(b) conversely Sufficiency: If p is a prime for every a  p there exists b  p such that
ab  1 mod p  . Also  p  1   1 mod p 

Application 14

1. Find the remainder when

(a) 20! is divided by 23
(b) 14! is divided by 17
(c) 26! is divided by 31

2. Prove that (31!)  (9!)  1(mod 41)

3. What is the remainder when 1! + 2! + 3! + ….. + 100! is divided by 12?

 2009! 
4. Find   where x is a fractional part of number x.
 2011 

r 1
5. If p is a prime and 0  r  p, then, prove that  p  r ! r  1!  1  0  mod p  . Hence or otherwise
show that 18!  (–1) (mod 437)

6. Show that p is the smallest prime that divides

 p  1! 1 Can we state that n is a prime iff n| (n–1)! + 1?

7. Show that 10 |  n  1 ! 1 for any n  N

15. PYTHAGOREAN TRIPLES

A Pythagorean triple consists of three positive integers a, b, and c, such that a 2  b 2  c 2 . Such a
triple is commonly written (a, b, c), and a well-known example is (3, 4, 5)
 If (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer k.
 A primitive Pythagorean triple is one in which a, b and c are co-prime.
  A right triangle whose sides form a Pythagorean triple is called a Pythagorean triangle.
 There are 16 primitive Pythagorean triples with c  100 :
 3, 4, 5 5,12,138,15,17  7, 24, 25 
 20, 21, 29 12,35, 37  9, 40, 41 28, 45,53
11, 60, 6116, 63,65  33, 56, 65 48,55, 73
13,84,85  36, 77,85  39,80,89  65, 72,97 
 Additionally these are all the primitive Pythagorean triples with 100 < c  300.
 20, 99,101 60,91,109 15,112,113
 44,117,125 88,105,137 17,144,145
 24,143,145 51,140,149 85,132,157 
119,120,169  52,165,17319,180,181
 57,176,185104,153,185 95,168,193
 28,195,197 84,187, 205133,156, 205
 21, 220, 221 140,171, 221 60, 221, 229 
105, 208, 233120, 209, 241 32, 255, 257 
 23, 264, 265 96, 247, 265 69, 260, 269 
115, 252, 277 160, 231, 281161, 240, 289  68, 285, 293
Application 15

Instruction for Question Q. 1 to Q. 6 : a  m 2  n 2 , b  2mn, c  m 2  n 2 , m  n  0

1. Prove the Euclid’s formula :
This is a fundamental formula for generating Pythagorean triples given an arbitrary pair of integers
m and n with m > n> 0. The formula states that the integers a  m2  n 2 , b  2mn, c  m2  n 2 form a
Pythagorean triple. The triple generated by Euclid’s formula is primitive if and only if m and n are
co-prime and not both odd.

2. Prove that exactly one of a, b is odd; c is odd.

3. Prove that exactly one of a, b is divisible by 3.

4. Prove that exactly one of a, b is divisible by 4.

5. Prove that exactly one of a, b, c is divisible by 5.

6. Prove that the largest number that always divides abc is 60.

7. All prime factors of c are primes of the form 4n + 1. Therefore c is of the form 4n+1.
16. BINOMIAL THEOREM
For natural number n, binomial theorem gives expansion for any index of a binomial
 a  b  , a, b  R
n n n n n
 a  b    a n    a n 1.b    a n 2 b2  ....    bn
0  1  2 n
n
 For any positive integers n, r, the binomial coefficient   is a positive integer for any 0  r  n .
r 

Applications 16

1. Determine the last 3 digits of the number 7999

n
2. Prove that for positive integer n we have n 2 |  n  1  1

3. Show that 1993  1399 is a positive integer divisible by 162. (RMO 1993)

7
4. Let a, b, c be the positive integers such that a | b 2 , b | c2 and c | a 2 then prove that abc |  a  b  c 

 n   n   n  1
5. Prove that      
 r   r  1  r 

n
n n n n n n
6. Prove that   r    0   1    2   ....   n   2
r 0          

n n n n n n

7. Prove that          ....           ...  2n 1
0  2 4 1   3   5 

n
r n n n n n n
8. Prove that   1  r    0   1    2   .....   1  0
r 0         n

n
n n n n n n 1
9. Prove that  r  r   1   2  2   3 3   ...  n  n   n2
r 0          

n
2 n n 2 n 2 n n
2  n 2
10. Prove that r       2    3    ...  n    n  n  1 2
r 0 r
   1 2
  3
  n
 

n
3 n n 3 n 3 n n
3  2 n 3
11. Prove that r       2    3    ....  n    n  n  3 2
r 0  r  1  2 3  n
17. REPUNIT
The number with all its digits are 1 is called repunit and it is denoted by R n  11....1 (n times)
1 1

R n   99....9   10n  1
9 9

Applications 17

1. Find all n such that R n is a perfect square.

2. Find whether R 91 is a prime.

3. Prove that R n | R m iff n | m. Does that means R p is prime for p prime?

4. Prove that if  n, m   1, then,  R n , R m   1

5. Prove that R mn  R m .100....0100....01.....100....01 where in second factor 1 appears n times and

 
between any two one’s m–1 zeros appear. R m 10mk  10    ....  10m  1  R m k 1 (for eg R12)
m k 1

6. Let N be a 50 digit number with all its digits but 26th digit from left is 1.If 13|N, then, find the 26th
digit.

7. Find the smallest positive integer n such that 999999n  111....1

8. Show that each term in the following sequence is a perfect square.

(a) 16, 1156, 111556, 11115556, ….
(b) 49, 4489, 444889, 44448889,…

9. Which is the least positive integer n such that 3 R100 | R n

18. SUM OF THE DIGITS

 S  n  denotes the sum of digits of the number n. Clearly S  n   n  mod 9 
 S  n   9 times number of digits of n
 s  m  s  n   s m  n 

Applications 18

1. Find the smallest natural number n with S  n   100

2. Find the largest natural number with all nonzero digits such that S  n   125

3.  
Find all solutions to the equation s  n   s  s  n    s s  s  n    1489

4. [MOSP 1998] Let S(x) be the sum of the digits of the positive integer x in its decimal representation.
 S x 
(a) Prove that for every positive integer x,  5 . Can this bound be improved?
S  2x 
Sx
(b) Prove that is not bounded.
S  3x 

19. ABSOLUTE VALUE

Classical definition : The absolute value of a real number is its distance from origin.
 x if x  0
Mathematical definition : The absolute value of the number x is denoted by | x | 
 x if x  0
Interval
a b
1. Open interval :  a, b   x  R / a  x  b

a b
2. Closed interval :  a, b   x  R / a  x  b

a b
3. Open closed interval :  a, b   x  R / a  x  b

a b
4. Closed open interval :  a, b   x  R / a  x  b

Properties
1. The solution for the equation | x | a is a  x  a  x    a, a  for a  0 and is a null set
otherwise.
2. The solution for the equation | x | a is x  a or x  a  x   ,  a    a,   for a  0 that
is x 2  a 2
3. Triangle inequality | x  y |  | x |  | y |
| x |  | y | if xy  0
Actually | x  y |  | x |  | y | if xy  0

4. | x ||  x |
 x  a  x  a for any a  R 
5. | x  a | 
 a  x  x  a
Application 19
1. Solve the following equations/in-equations
a) | 4x  5 | 3
b) | 2x  8 || x  2 |
c) | 2x  1|| x  3 |
d) | 5x  3 | 103
e) | 7x  11|  3

2. Solve the following equations/in-equations

a) | x 2  2x  5 |  4
b) | 3x 2  2 | 1  4x
x 1
c) 1
x 1
 d) | x 2  x |  2
e) x 2  2x  5 | x  1| 7  0

3. Solve the equation | x  3 |  | x  1| 4

4. Find the minimum value of the expression | x  7 |  | x  11|

5. Find the minimum value of the expression | x  2 |  | x  11|  | x  7 |  | x  5 |

6. Show that the equation | 2x  3 |  | x  1|  | 5  x | 0.99 has no solutions.

7. Solve the equation | x  1|  | x |  | x  1| x  2

2
8. Find the values of a for which the equation  x  1 | x  a |

20. GREATEST INTEGER FUNCTION

Definition
For a real number x there is a unique integer n such that n  x  n  1 . We say that n is the greatest
integer less than or equal to x, or the floor of x. We write n   x  . The difference x   x  is called the
fractional part of x and is denoted by x . The least integer greater than or equal to x is called the
ceiling of x and is denoted by  x  . If x is an integer, then [x] =  x  = x and {x} = 0; if x is not an
integer, then  x    x   1 . We start with four (algebraic) examples to get familiar with these
functions.

Properties
1.  x   x iff x  Z
2. x  0 iff x  Z
3. 0  x   1
4. x  x x 1
5. x  1   x   x and 0  x   x   1
6.  x  m    x   m if m is an integer.
7.  x    y   x  y   x    y  1
0 if x  Z
8.  x    x   1 otherwise

x   x 
9.      if m  Z
 m  m
n 
10. For n, a  Z , the number of integers divisible by a, less than n will be equal to  
a 
 1
11.  x  2  rounds x to it’s nearest integer.
12.  x  y   xy  for nonnegative real numbers x and y
 Legendre’s Function
Let m be a prime. For any positive integer n, let e p  n  be the exponent of p in the prime factorization
of n!. The arithmetic function e p is called the Legendre function associated with the prime p. The
following result gives a formula for the computation of e p  n  .
For any prime p and any positive integer n, the highest power e p  n  of prime p that divides n is

n  n   n  n
given by ep  n       2    3   .....    i 
 p p  p  i 1  p 
i k
If n   a i p  a 0  a1p  ......  a k p , then,
   
ep  n   a1  a 2 p  .....  a k 1p k 1  a 2  a 3p  ......  a k p k 1  ......
  
 a1  a 2 1  p   a 3 1  p  p 2  .....  a k 1  p  p 2  .....  p k 1 
Property
n  Sp  n 
where Sp  n   sum of digits of n when represented in base p.
p 1
Proof : Let n   a i pi  a 0  a1p  ....  a k p k
Now   
ep  n   a1  a 2 p  .....  a k 1p k 1  a 2  a 3p  ....  a k P k 1  ..... 
  
 a1  a 2 1  p   a 3 1  p  p 2  .....  a k 1  p  p 2  .....  p k 1 
 Sp  n    a i
n  Sp  n   p  1 
i


p 1
  ai
p 1
 a 1  p  p
i
2

 .....  pi 1  e p  n 

Applications 20

1. Solve the equation 4  x   3x

2. Solve the equation  9x   9

3. Solve the equation x 2  6  x   6  0

 1  1
4. Solve the equation  x     x     2x 
 2  2
 x   x   x  31x
5. Find the number of integers 0  x  1000 such that         
 2   3   5  30

6. Find all solutions to 4x 2  40  x   51  0

7. Find the number of zeros at the end of 100!

8. Consider a new symbol a n || b, this means n is the largest power of a that divides b. Find n such that
12 n || 533!
9. Let s and t be positive integers such that 7s || 400! and 3t ||   3! ! !. Compute s + t.

10. [HMMT 2003] Find the smallest n such that n! ends in 290 zeros.

11. Australia 1999] Solve the following system of equations:

x   y   z  200.0
x  y   z  190.1
 x    y  z  178.70

x  x 
12. Find the number of positive integers x which satisfy the condition     . (Here [z] denotes,
 99  101
for any real z, the largest integer not exceeding z; e.g. 7 / 4  1 )

13. How many of the first 1000 positive integers can be expressed in the form
 2x   [4x]   6x   8x 
14. (Hermit Identity) Let x be a real number and let n be a positive integer.
 1  2  n  1
Then  x    x     x    ....   x    nx 
 n  n  n 
 19   20   91 
15. (AIME 1991) Suppose that r  R for which  r   r 
 100   100 
  ....  r  100   546 . Find 100r 
 EXERCISE -1

1. Prove that if n  p k , then, T  n   k  1

2. Prove that if n is a perfect square iff T  n  is odd.

3. Find the number of integers between 1and 1000, both inclusive which are not divisible by any of the
integers 2, 5 or 7.

4. Find the smallest positive integer which leaves remainder 2 when divided by 3 , remainder 3 when
divided by 4,remainder 4 when divided by 5 Show all such numbers form an A.P.

5. The number n is such than n has 60 divisors and 7n has 80 divisors. Find the largest power of 7 that
divides n.

6. Prove that if m, n are odd integers, then

(a) 8 | n 2  m 2 ,
(b) 16 | n 4  m4  2,
 
(c) 24 | n n 2  1 ,

7. If a is an odd integer then, prove that

2 2
12 | a 2   a  2    a  4   1

8. Let m1 , m2 ,...., mn be a rearrangement of the numbers 1, 2, 3,…., n. Suppose n is odd then prove that
the product  m1  1 m 2  2  ..  m n  n  is an even integer

9. The numbers 1 through 10 are written in a row. Can the signs “+” and “-” be placed between them,
so that the value of the resulting expression is 0?

10. A grasshopper jumps along the straight line. His first jump takes him 1 cm, his second 2 cm, and so
on. Each jump can take him to the right or to the left. Show that after 1985 jumps the grasshopper
can not return to his original position.

11. Find the reminder when 22225555 + 55552222 is divided by 7.

12. Find all integers solutions to the equation a2 + 1 = 4b2

13. Find all integers solutions to the equation a2 + 7 = 999b

14. Prove that a 3  b3  2012 has no solution over integers

15. Prove that a  b | a n  b n n  N

16. Prove that a  b | a n  b n n  N, n is odd

17. Prove that a  b | a n  b n n, n  N , n is even

18. Prove that there is no integer a such that a 2  3a  19 is divisible by 289

19. Prove that n 5  4n is divisible by 5 for any n  N

20. Prove that 24 | p2  1 for a prime p  3

21. If x, y, z be integers which are sides of a right triangle with hypotenuse z. then prove that one of x, y
is divisible by 3 and one of the sides is divisible by 5

22. Given natural numbers a, b are such that 21| a 2  b2 , then Prove that 441| a 2  b 2

23. Let a = 44444444 and b be the sum of digits of a and c be the sum of digits of b then find the sum of
digits of c

EXERCISE -2

1. In a book with page numbers from 1 to 100, some pages are torn off. The sum of the remaining pages
is 4949. How many pages are torn off?

2.  
For any a, b, c  N, show that 7 | abc a 3  b3 b3  c3 c3  a 3  
3. Find all non-negative integers k, n which satisfy 22k 1  9.2k  5  n 2 (2014 BMO)

4. Find the smallest natural number n such that it’s decimal representation has 8 as the last digit and if
it’s last digit is shifted to front of the remaining digits and the resulting number is two times the
original number.

5. We denote a 2  gcd  b1 ; c1  ; b 2  gcd  c1 ; a1  ; c2  gcd  a1; b1  ; and

a 3  lcm  b 2 ;c 2  ; b 3  lcm  c 2 ; a 2  ; c3  lcm  a 2 ; b 2  : show that gcd  b3 ; c3   a 2 .

6. How many pairs (x, y) of positive integers with x  y satisfy gcd(x, y) = 5! and lcm(x, y) = 50!?
(1997 Canadian Mathematical Olympiad)

12
7. If gcd  a,35   1, then, prove that a  1 (mod 35)

8. If gcd  a, 42   1, then, prove that 168 | a 6  1

9. If n is a positive integer not divisible by 17, then, prove that either n 8  1 or n 8  1 is divisible by 17.

10. For all n  N, prove that 13 |1112n 6  1 .

11. If n is a any positive integer and p is a prime, then n 2  k 2  mod p   n  k  mod p 

12. Prove that n5 and n both have the same last digit.

13. Prove that if 5 | (n − 1), 5 | (n + 1) and 5 | n, ,then, prove that 5 | n 2  1

14. If a is co-prime integer to a prime p, then prove that there exists an integer b such that ab  1(modp).

15. If p and q are distinct primes then prove that

(a) pq  q p  p  q  mod pq 
 pq  q p 
(b)   is even if p  2, q  2 , where [.] denotes the greatest integer function
 pq 

16. Find the remainder when 21990 is divided by 1990 (RMO 1990)

17. Find the remainder when

a) 2250 is divided by 41
b) 51002 is divided by 11
c) 44444444 is divided by 9

18. Find last two digits of 7100 – 3100

19. Show that 41|220 – 1

 72 
20. Find remainder when   is divided by 73.
 36 

21. Prove that n  N, n  1 a  n 4  4 is composite  b  n 4  4n is composite .

22. Prove that the sequence a n  24n  1 contains all primes greater than 3.

23. If 2 n  1 is a prime then show that n is a prime.

24. If p and 8p − 1 are primes, then 8p + 1 is a composite

25. Find all positive integers n such that the numbers n  1, n  3, n  7, n  9, n  13 and n  15 is a prime.

EXERCISE- 3

1. Find the smallest n that satisfy the equation s  n   s  s  n    s(s  s  n  )  1035

2. If a  44444444 , b  s  a  , c  s  b  , d  s  c  . Then find d

3. Let a, b  0 . Find the values of m for which the equation

| x  a |  | x  b |  | x  a |  | x  b | m  a  b  has at least one real solution.

|ab| |a| |b|

4. Prove that for all real numbers a, b, we have|  
1 | a  b | 1 | a | 1 | b |

5. Find the right triangle with integral sides such that its perimeter is numerically equal to its area.
6. Find the right triangle with integral sides such that its semi-perimeter is numerically equal to its area.

1 1 1 1 1 2a
7. If      , find the value of a and b.
1!9! 3!7! 5!5! 7!3! 9!1! b!

8. Prove that the product of r consecutive integers is divisible by r!

 p
9. If p is a prime, then the binomial coefficient   is divisible by p for 1  r  p  1
r 

10. If p is any prime other than 2 or 5, prove that p divides infinitely many terms in the sequence
9, 99, 999, ...

11. Prove that a number with 3n equal digits is divisible by 3n.

12. Let s(n) denote the sum of the digits of n . If f  x   90x 2  20x  1 , then, find s (f (11111)).

13. Show that for natural number n relatively prime to 10, there is another natural number m all of whose
digits are 1’s such that n divides m. Hence or otherwise show that every positive rational number can
a
be expressed in the form b for some natural numbers a, b, c.
10 10c  1

14. Show that there is a natural number n such that decimal representation of n! ends with 1993 zeros.

2 2 2 2 n
n
n n n n  n   2n 
15. Prove that              ....      
r 0  r   0  1   2  n n 

 x   2x 
16. (SSSMO/2002) Determine the number of real solutions of       x
2  3 

17. (CHINA)/1988) Let S   1     2    3   ....  1988  Find  S 

502
 305k 
18. (CHINA/1986) Evaluate the sum S    
k 1  503 

 10 20000 
19. (PUTNAM/1986) What is the units digit of  100 ?
 10  3 

20. Given some positive integers less than 1951, where each two have a lowest common multiple greater
than 1951. Prove that the sum of the reciprocals of these numbers is less than 2.

21. (CHINA/1992) Given that real number a  1 , the natural number n  2 , and the equation [ax] = x
has exactly n distinct real solution. Find the range of a.
 10 n
22. (ASUMO/1989) Find the minimum natural number n, such that the equation  1989 has integer
x
solution x. Find x

23. (ASUMO/1980) How many different non-negative integers are there in the Sequence
 12   2 2   32  1980 2 
, ,
 1980   1980   1980  ,...,  1980 
       

24. (SSSMOJ/2000/Q30) Find the total number of integers n between 1 and 10000 (both inclusive) such
that n is divisible by  n  . Here  n  denotes the largest integer less than or equal to n

25. (CMO/1987) For every positive integer n, show that

 n  n  1   4n  1   4n  2    4n  3 
       

WINDOW TO RMO

2
1. A natural number k is such that k 2  2014   k  1 . What is the largest prime factor of k?
(preRMO 2014)

2. The first term of a sequence is 2014. Each succeeding term is the sum of the cubes of the digits of the
previous term. What is the 2014th term of the sequence? (preRMO 2014)

3. One morning, each member of Manjul’s family drank an 8-ounce mixture of coffee and milk. The
1
amounts of coffee and milk varied from cup to cup, but were never zero. Manjul drank th of the
7
th
2
total amount of milk and of the total amount of coffee. How many people are there in Manjul’s
17
Family? (preRMO 2014)

n 99
1 1
4. Let Sn   . What is the value of S ? (preRMO 2013)
k 0 k 1  k n 1 n  Sn 1

5.  
What is the smallest positive integer k such that k 33  43  53  a n for some positive integers a and
n, with n > 1? (preRMO 2013)

6. Let S(M) denote the sum of the digits of a positive integer M written in base 10. Let N be the
smallest positive integer such that S(N) = 2013. What is the value of S(5N+2013)? (preRMO 2013)

7. Let m be the smallest odd positive integer for which 1 + 2 + …… + m is a square of an integer and
let n be the smallest even positive integer for which 1 + 2 + ….. + n is a square of an integer. What is
the value of m + n ? (preRMO 2013)
8. What is the maximum possible value of k for which 2013 can be written as a sum of k consecutive
positive integers? (preRMO 2013)

9. What is the sum (in base 10) of all the natural numbers less than 64 which have exactly three ones in
their base 2 representation? (preRMO 2013)

10. Rama was asked by her teacher to subtract 3 from a certain number and then divide the result by 9.
Instead, she subtracted 9 and then divided the result by 3. She got 43 as answer. What would have
been her answer if she had solved the problem correctly? (preRMO 2012)

11. For how many pairs of positive integers (x, y) is x  3y  100 ?

12. The letters R, M, O represent whole numbers. If R  M  O = 240, R  M + O = 46 and R + M  O = 64,

what is the value of R + M + O? (preRMO 2012)

2000
13. Determine the largest 3-digit prime factor of the integer C1000 .

14. N is a 50 digit number (in the decimal scale). All digits except the 26th digit (from the left) are 1. If N
is divisible by 13, find the 26th digit. (RMO 1990)

15. A four-digit number has the following properties : (a) It is a perfect square, (b) Its first two digits are
equal, (c) Its last two digits are equal. Find all such four-digit numbers. (RMO 1991)

16. Prove that n 4  4n is composite for all integer values of n greater than 1. (RMO 1991)

1 1 1
17. If   , where a, b, c are positive integers with no common factor, prove that (a + b) is the
a b c
square of an integer. (RMO 1992)

18. Prove that the ten’s digit of any power of 3 is even. [e.g. the ten’s digit of 36  729 is 2].
(RMO 1993)

19. Show that 1993 1399 is a positive integer divisible by 162. (RMO 1993)

20. A leaf is torn from a paperback novel. The sum of the numbers on the remaining pages is 15000.
What is the page number on the torn leaf? (RMO 1994)

21. Find all 6-digit natural numbers a1a 2a 3a 4a 5a 6 formed by using the digits 1, 2, 3, 4, 5, 6, once each
such that the number a1a 2 ....a k is divisible by k, for 1  k  6 .(RMO 1994)

22. Let A be a set of 16 positive integers with the property that the product of any two distinct numbers
of A will not exceed 1994. Show that there are two numbers a and b in A which are not relatively
prime. (RMO 1994)

23. Find the number of all rational numbers m /n such that (a) 0 < m / n < 1 (b) m and n are relatively
prime (c) mn = 25! (RMO 1994)

24. Suppose N is an n-digit positive integer such that (a) all the n-digits are distinct; and (b) the sum of
any three consecutive digits is divisible by 5. Prove that n is at most 6.Further, show that starting
with any digit one can find a six-digit number with these properties. (RMO 1994)
25. Given any positive integer n show that there are two positive rational numbers a and b, a  b, which
are not integers and which are such that a  b,a 2  b2 ,a 3  b3 ,......,a n  bn are all integers.
(RMO 1996)

26. If A is a fifty-element subset of the set {1, 2, 3, …, 100} such that no two numbers from A add up to
100, show that A contains a square. (RMO 1996)

27. For each positive integer n, define a n  20  n 2 , and d n  gcd  a n ,a n 1  . Find the set of all values that
are taken by dn and show by examples that each of these values are attained. (RMO 1997)

1 1 1
28. Solve for real x :    x   , where [x] is the greatest integer less than or equal to x and
 x   2x  3
(x) = x – [x], [e.g. [3.4] = 3 and (3.4) = 0.4] (RMO 1997)

29. Let n be a positive integer and p1 ,p2 ,p3 ,.....pn be n prime numbers all larger than 5 such that 6 divides
p12  p 22  p 32  ......p n2 . Prove that 6 divides n. (RMO 1998)

30. Find the minimum possible least common multiple of twenty natural numbers whose sum is 801.
(RMO 1998)

31. (i) Consider two positive integers a and b which are such that a a bb is divisible by 2000. What is the
least possible value of the product ab?
(ii) Consider two positive integers a and b which are such that a b ba is divisible by 2000. What is the
least possible value of the product ab? (RMO 2000)

x  x 
32. Find the number of positive integers x which satisfy the condition      (Here [z] denotes,
 99  101 
for any real z, the largest integer not exceeding z; e.g. [7/4] = 1.) (RMO 2001)

33. Find all primes p and q such that p2  7pq  q 2 is the square of an integer. (RMO 2001)

34. Let a, b, c be positive integers such that a divides b 2 , b divides c 2 and c divides a 2 . Prove that abc
7
divides  a  b  c  .(RMO 2002)

35. Suppose the integers 1, 2, 3, ……, 10 are split into two disjoint collections a1 ,a 2 ,a 3 ,a 4 ,a 5 and
b1 , b2 ,b3 , b4 , b5 such that a1  a 2  a 3  a 4  a 5 , b1  b2  b3  b4  b5
 
(i) Show that the larger number in any pair a j , b j ,1 j  5, is at least 6.
(ii) Show that a1  b1  a 2  b2  a 3  b3  a 4  b4  a 5  b5  25 for every such partition.
(RMO 2002)

n n 
36. If n is an integer greater than 7, prove that      is divisible by 7. (RMO 2003)
7 7
37. Let  and  be the roots of the equation x 2  mx 1  0, where m is an odd integer. Let
 n   n   n , n  0. Prove that (A) n is an integer (B) gcd  n , n 1   1. (RMO 2004)

38. Let p1 , p2 ,..... be a sequence of primes such that p1  2 and for n  1, pn 1 is the largest prime factor of
p1p2 ....pn  1. Prove that p n  5 for any n. (RMO 2004)

39. If a, b, c are three real numbers such that a  b  c , b  c  a , c  a  b , then prove that one of a,
b, c is the sum of the other two. (RMO 2005)

40. Find the least value of a + b such that 11 divides a + 13b and 13 divides a + 11b. (RMO 2006)

41. Let a, b, c be three natural numbers such that a < b < c and gcd (c – a, c – b) = 1. Suppose there exists
an integer d such that a +d, b + d, c + d form sides of a right triangle. Prove that there exists integers
l, m such that c  d  l 2  m 2 (RMO 2007)

42. Prove that there exist two infinite sequence a n n 1 and bn n 1 of positive integers such that the
following conditions hold simultaneously: (i) 0  a1  a 2  a 3  ....; (ii) a n  b n  a n2 , for all n  1;
(iii) a n 1 divides b 2n  1, for all n  1 (iv) a 2n  1 divides b 2n  1 , for all n  1 (RMO 2008)

43. In a book with page numbers from 1 to 100 some pages are torn off. The sum of the numbers on the
remaining pages is 4949. How many pages are torn off? (RMO 2009)

44. Show that 32008  4 2009 can be written as product of two positive integers each of which is larger than
2009182 .(RMO 2009)
 
n 
45. For each largest n  1 define a n   (where  x  denoted the largest integer not exceeding x,
 n
 
for any real number x). Find the number of all n in the set 1,2,3,..., 2010 for which a n  a n 1 .
(RMO 2010)

46. Show that there is no integer a, such that a 2  3a  19 is divisible by 289.(RMO 2009)

47. Let n be a positive integer such that 2n  1 and 3n  1 are both perfect squares. Show that 5n  3 is a
composite number. (RMO 2010)

48. Let  a1 , a 2 ,a 3 ,...,a 2011  be a permutation (that is a rearrangement) of the numbers 1, 2, 3,...., 2011 .
Show that there exist two numbers j, k such that 1  j  k  2011 and a j  j  a k  k .(RMO 2011)

49. A natural number n is chosen strictly between two consecutive perfect squares. The smaller of these
two squares is obtained by subtracting k from n and the larger one is obtained by adding l to n. Prove
that n - kl is a perfect square. (RMO 2011)

50. Let a, b, c be positive integers such that a divides b3 , b divides c 3 and c divides a 3 . Prove that abc
13
divides  a  b  c  .(CRM 2013, pl)
51. Let a, b, c be positive integers such that a divides b4 , b divides c 4 and c divides a 4 . Prove that abc
21
divides  a  b  c  .(CRMO 2012, p2)

52. Let a, b, c be positive integers such that a divides b5 , b divides c 5 and c divides a 5 . Prove that abc
31
divides  a  b  c  .(CRMO 2012, p3)

53. Find all primes p and q such that p divides q 2  4 and q divides p2 1 (CRMO 2013,p1)

x7 1
54. Prove that there do not exist natural numbers x and y, with x  1, such that  y5  1 .
x 1
(CRMO 2013,p2)

55. Consider the expression 20132  2014 2  20152  ...  n 2 . Prove that there exists a natural number
n  2013 for which one can change a suitable number of plus signs to minus signs in the above
expression to make the resulting expression equal 9999. (CRMO 2013, p2)

56. Find all 4-tuples  a, b,c,d  of natural numbers with a  b  c and a ! b! c!  3 d .(CRMO 2013, p3)

57. Determine the smallest prime that does not divides any five-digit number whose digits are in a
strictly increasing order. (CRMO 2011, p4)

1 1
58. Let x be a non-zero real number such that x 4  4
and x5  5 are both rational numbers. Prove that
x x
1
x is a rational number. (CRMO 2013, p4)
x

59.  
Find all triples  p,q, r  of primes such that pq  r  1 and 2 p 2  q 2  r 2  1 .
(CRMO 2013, Mumbai Region)

60. Let a, b be real numbers and, let P  x   x3  ax 2  b and Q  x   x 3  bx  a . Suppose that the roots
of the equation P  x   0 are the reciprocals of the roots of the equation Q  x   0 . Find the greatest
common divisor of P  2013! 1 and Q  2013! 1 . (CRMO 2013, Mumbai Region)

61. Let a1 ,b1 ,c1 be natural numbers. We define a 2  gcd  b1 ,c1  , b2  gcd  c1 ,a1  ,c2  gcd  a1 , b1  , and
a 3  lcm  b2 ,c2  , b3  lcm  c2 ,a 2  ,c3  lcm  a 2 , b2  Show that gcd  b3 ,c3   a 2 .
(CRMO 2013, Mumbai Region)

62. Let a1 , a 2 ,..., a 2n be an arithmetic progression of positive real numbers with com-mon difference d.
Let (i) a12  a 32  ...  a 22n 1  x, (ii) a 22  a 24  ...  a 2n  y, and (iii) a n  a n 1  z . Express d in terms of
x, y,z,n . (CRMO 2014,p1)

63. Suppose for some positive integers r and s, the digits of 2 r is obtained by permuting the digits of 2s
in decimal expansion. Prove that r = s. (CRMO2014, p1)
64. Find all pairs of (x, y) of positive integers such that 2x + 7y divides 7x + 2y. (CRMO2014, p2)

65. For any positive integer n > 1, let P(n) denote the largest prime not exceeding n. Let N(n) denote the
next prime larger than P(n). (For example P(10) = 7 and N(10) = 11, while P(11) = 11 and
N 11  13) . If n  1 is a prime number, prove that the value of the sum
1 1 1 n 1
  ...   (CRMO2014, p2)
P  2  N  2  P 3 N 3 P  n  N  n  2n  2

66. Suppose n is odd and each square of an n  n grid is arbitrarily filled with either 1 or −1. Let rj and ck
denote the product of all numbers in j-th row and k-th column respectively, 1  j, k  n . Prove that
n n

r c
j1
j
k 1
k  0 (CRMO2014, p2)

67. Prove that there does not exist any positive integer n < 2310 such that n(2310 − n) is a multiple of
2310. (CRMO2014, p3)

68. For any natural number n, let S(n) denote the sum of the digits of n. Find the number of all 3-digit
numbers n such that S(S(n)) = 2. (CRMO2014, p3)

69. Determine all pairs m  n of positive integers such that 1  gcd  n  1, m  1  gcd  n  2,m  2
 ....  gcd  m, 2m  n  .(CRMO2014, p4)

70. Find all real numbers a such that 3  a  4 and a  a  3a is an integer. Here a denotes the
fractional part of a. For example 1.5  0.5;3.4  0.6 )(CRMO2015, p1)

7k  5 6m  1
71. Find all fractions which can be written simultaneously in the forms and ,
5k  3 4m  3
for k, m  N (CRMO2015, p1)

72. Find all real numbers a such that 4 < a < 5 and a(a − 3 {a}) is an integer. (Here {a} denotes the
fractional part of a. For example {1.5} = 0.5; {−3.4} = 0.6.) (CRMO2015, p2)

73. Show that there are infinitely many triples (x, y, z) of integers such that x 3  y4  z31
(CRMO2015, p3)

74. Show that there are infinitely many positive real numbers a which are not integers such that a(a − 3
{a}) is an integer. (Here {a} denotes the fractional part of a. For example {1.5} = 0.5; {−3.4} = 0.6.)
(CRMO2015, p3)

75. How many integers m satisfy both the following properties:

(i) 1  m  5000
(ii)  m    m  125  ?
   
(Here [x] denotes the largest integer not exceeding x, for any real number x.) (CRMO2015, p4)

76. Consider a sequence  a k k 1 of natural numbers defined as follows: a1 = a and a2 = b with a, b > 1
and gcd(a, b) = 1 and for all k > 0, ak+2 = ak+1+ak. Prove that for all natural numbers n and k,
a
gcd  a n ,a n k   k (RMO Delhi region)
2
 ANSWER KEY

Applications 1
1. 45
2. Let number of factors of n that are not divisible by k be denoted by
T k (n) then T 25  7200   42 T100  7200   30

3. (a) Hence factors divisible by 35 are 3 · 3 · 3 · 1 = 27

(b) Factors not divisible by 9 are 3 · 2 · 4 · 2 = 48
(c) Factors not divisible by 45 are T(31500) – T45(7200) = 72 – 18 = 54
(d) T45,but 100  31500   7 1  2  14

4. 6
5. a) 16 b) 60
56  1
6.  2  2  2  2  2 1  5  5  5  5  5   62. 5 1  242172 .
2 3 4 5 2 3 4 5

16
7.
5
8. 630
9. 207
Solution: The answer is 207. Note that digits 4, 6, and 8 cannot appear in the units digit. Hence the
sum is at least 40+60+80+1+2+3+5+7 + 9 = 207. On the other hand, this value can be obtained with
the set{2, 5, 7, 43, 61, 89}.

Applications 2
2. a = 23, b = 5 3. 28 4. 123654, 321654
5. i) a = 1, b = 10 gives ab = 10, ii) a = 4, b = 5 gives ab = 20.

Applications 3
2. It is not possible. 3. 420

Applications 4
1. 2 2. 1 3. 6 5. 7 6. 9 7. 43 8. 43

Applications 5
2. 880 4. 8181 5. 153846

Applications 6
1. 0 or 24
Applications 7
2. no solution 3. 9901 4. 12 5. 2 6. q= 2 and p = 3
7. Numbers 20! 2, 20! 3,..., 20! 21 will do the trick.

Application 8
5 if n  2  mod 5  
2. gcd   4. 6 5. 2  3  5  7 13  2730
1 otherwise 

Applications 9
1. a) x  7, y  6 b) x  7, y  3 2. 11 3. 2  4  5  2  9

Applications 10
1. 13  6 and 13  7 4. 42 5.  59 × 28,135 × 28  6. 2835

Applications 11
1. Ans. (a) 2 (b) 9 (c) 7 (d) 1 (e) 1 (f) 9 (g) 2

Application 12
1.  1001  720,   5040  1152,   36000  28800

3. 1920 4. 400000 5. N  3900049  1999.1951

Applications 13
2. 2 3. 0 4. 49 5. 69

Application 14
1
1. (a) 11 (b) 8 (c) 9 3. 9 4.
2011
Application 16
1. 143

Applications 17
1. 1 6. 3 7. n = 54 9. 300

Applications 18
1. 199....9 where 9 appears 11 times. 2. R125 3. No solution

Application 19
 1  2   106   8
1. a)  2,  , b) {2, 10}, c)  ,4 , d)  , 20  , e)  ,    2,  
 2  3   5   7

 2  13 2  7 
 
2.a) 3  2 2,3  2 2  {3} b)  ,  c)  ,0 d)  , 1   2,  e)  2, 1 3,4
 3 3 

3 5
3.  1,3 4. 4 5. 11 7.  0,1 8.  ,1, 
4 4
Applications 20
4 8  10  1
1. 0, , 2. 1,  3. 6, 12, 18 4. x  5. 33
3 3  9 2
1 1 1
6. 29, 189, 229 7. 24 8. 263 9. 422
2 2 2
10. 1170 11. x  94.65, y  105.45 and z  84.35
12. 2499 13. 600 15.743

Exercise -1
3. 343 4. 59 5. 2 9. Not possible. 11. 0
12. No such a exists. 13. No such a exists. 23. 7

Exercise- 2
1. 3 3. k  0 and n  4 4. 421052631578947368 6. 214
7. n  {37, 38, 39, 40} 16. 1024
17. (a) 40, (b) 4, (c) 5 18. 0 20. 1 25. 4

Exercise -3
1. 9R111 2. 5 3.  2, 5. (5, 12, 13) and (6, 8, 10)

6.  3,4,5 7. a = 9 b = 10 12. 11 16. x 0,2,3,4,5,7

1 1
17. 242 18. 304.251  76304 19. 3 21. 1   a  1
n n 1
22. Hence minimum value of n = 7 and x = 5027 or 5026
23. 1486

Window to RMO
1. 11 2. 407 3. 8 4. 9 5. k = 1 6. 18 7. 9
8. 61 9. 630 10. 15 11. 33 12. 20 13. 661 14. 3
15. 7744
20. Let n be total number of pages and k be the torn page number, then only two possible answers are
(a) n = 173, k = 25 (b) n = 174, k = 112
29 17 97
21. 123456, 321456 23. 256 27. 1, 3, 9, 27, 81 28. , ,
12 6 24
30. 42 31. (i) 10 (ii) 20 32. 2499
33.  p, p  / p is a prime   3,11 , 11,3 40. 28
43. 3 45. All n such that  n  1 is a perfect square.

53.  5,3 56. 1,1,1,1 , 1, 2,3, 2  , 1, 2, 4,3 57. 11

yx
59. (2, 3, 5), (3, 2, 5) 60. 3 62. d 
nz
64.  d, d  ,  4d, d  , 19d, d  , 12d,3d  ,  5d,5d  for all d  N 68. 85

3  17 1 3  33 3  41
69.  n, n  1 , where n  N 70. a  3  ,3 4 ,3  ,3 
4 4 4
43 31 55 5 61 19 13
71. , ,1, , , , ,
31 27 39 3 43 13 9
6 8 10 12 14
72. a  3  ,3  ,3  ,3 ,3  75. 72
2 2 2 2 2