Number Theory

Numbers can be classified as Real and Complex. Further real numbers can be classified as integers, natural numbers, whole numbers, rational numbers, irrational numbers, prime numbers, composite numbers, co–prime numbers etc. Here is a brief summary of real numbers:

There are certain points to be noted about prime and composite numbers.

1. The number of prime numbers are infinite
2. Every prime number is odd except 2.
3. Every prime number which is more than 3, can be represented as \(6k + 1\) or \(6k – 1\)
4. Every prime number which is more than 2, can be written as \(4k + 1\) or  \(4k – 1\).
5. Every prime number which is more than 3, can be represented as \(8k \pm 1\) or \(8k \pm 3\)

6. There in no known algebraic formula which can represent prime numbers, many attempt have been made to make a formula to generate a formula for prime numbers for example the number \({n^2} + n + 41\) is always prime for all values of \(n\) from 1 to 39 but it fails when \(n = 40\) or any multiple of 41. 

   Similarly another number of this type is  

   \({n^2} + n + 17\) is prime for all values from 1 to 15.

7. If \(p\) is a prime number more than 3 then \({p^2} - 1\) is always multiple of 24.
8. If \(p\) denotes prime numbers and \(c\) denotes composite numbers then \({p^c},\,\,{c^p},\,\,{p^p},\,\,p \times c,\,\,c \times c\) and \(p \times p\) are always composite. \(p + c, p + p\) may not be a prime.

Example 1: If \(p, p + 4, p + 14\) all three numbers are prime. How many different values can \(p\) take?

Solution: By simple observation we see that  \(p\) is 3, now suppose \(p > 3\), since \(p\) is a prime number it can be only \(6k + 1\) or \(6k – 1\). 

(a) \(p = 6k + 1\), 

\(p + 4 = 6k + 5\) and

\(p +14\) will be \(6k + 15\), now \(6k + 15\) can never be a prime number as it is multiple of 3.

(b) \(p = 6k – 1\), 

\(p + 4 = 6k + 3\)

\(p +14\) will be \(6k + 13\)

Since \(p + 4 = 6k + 3\) which can never be a prime number as it is multiple of 3.

So \(p, p + 4\) and \(p + 14\) can never be prime simultaneously for a value of \(p\) other than 3.

A perfect number is defined as a positive integer which is the sum of its proper positive factors, that is, the sum of the positive divisors excluding the number itself. Equivalently, a perfect number is a number that is half the sum of all of its positive divisors (including itself).

The first perfect number is 6, because 1, 2, and 3 are its proper positive divisors and \(1 + 2 + 3 = 6\). Equivalently, the number 6 is equal to half the sum of all its positive divisors: \(\left[ {\frac{{1 + 2 + 3 + 6}}{2}} \right] = 6\).

The next perfect number is 28. As 28 can be written as \(= 1 + 2 + 4 + 7 + 14\). This is followed by the perfect numbers 496 and 8128.

How to find a Perfect Number:

If \({2^n} - 1\) is a prime number then the formula \({2^{n - 1}}({2^n} - 1)\) always give an even perfect number.  For example the first four perfect numbers can be obtained by putting 

\(n = 2\):   \({2^1}({2^2} - 1) = 6\)

\(n = 3\):   \({2^2}({2^3} - 1) = 28\) 

\(n = 5\):   \({2^4}({2^5} - 1) = 496\)

\(n = 7\):   \({2^6}({2^7} - 1) = 8128\)

But the fifth perfect number not be obtained by putting \(n=11\), the value \({2^{11}} - 1 = 2047 = 23 \times 89\) is not prime and therefore n = 11 does not yield a perfect number. 

The fifth perfect number 33550336 

\( = \left[ {{2^{12}}({2^{13}} - 1)} \right]\) has 8 digits.

It is important to note that:

Sum of proper factors of a perfect number is always equal to the number itself.
Sum of reciprocal of factors of a perfect number is always 2.

Rational numbers:

A rational number is a number which can be expressed as a ratio of two integers. Non–integer rational numbers (commonly called fractions) are usually written as the fraction \(\frac{a}{b}\), where \(b\) is not zero, \(a\) is called the numerator, and \(b\) the denominator.

Any repeating number with a constant cycle or numbers with terminating digits are also known as rational numbers.

Some of the examples of rational numbers are:
\(\frac{2}{3}\), \(0.3333......\), \(2.25\) etc.

The decimal representation of a real number is called a repeating decimal (or recurring decimal) if at some point it becomes periodic. For example, the decimal representation of \(\frac{1}{3} = 0.3333333..\) becomes periodic just after the decimal point, repeating the single–digit sequence "3" indefinitely. Similarly the fraction \(\frac{1}{7} = 0.142857142857.......\) is repeating with a period of 6 digits. All the repeating numbers are rational numbers. Repeating decimal can be represented using bar lines on the digits. \(\frac{1}{7} = 0.142857142857.... = 0.\overline {142857} \)

Some interesting examples of repeating decimal:

\(\cfrac{1}{7} = 0.\overline {142857} \), \(\cfrac{2}{7} = 0.\overline {285714} \)

\(\cfrac{3}{7} = 0.\overline {428571} \), \(\cfrac{4}{7} = 0.\overline {571428} \)

\(\cfrac{5}{7} = 0.\overline {714285} \), \(\cfrac{6}{7} = 0.\overline {857142} \)

We see that all the six repeating digits are same in all the fractions given above.

Conversion from Repeating Numbers to Fraction:

Note that every repeating decimal can be converted to fraction (\(p/q\) form). Suppose the number is \(0.12\overline {345} \), this number is equal to 0.12345345345345……up to infinite. In this number 12 is non repeating number, 345 is repeating number, number of repeating digits is 3 and number of non repeating digits is 2.  The \(p/q\) form is given by: \[\left[ {\frac{{{\rm{Entire}}\,\,\,\,{\rm{Number}}\; - \;{\rm{Non}}\,\,\,{\rm{repeating}}\,\,\,{\rm{number}}}}{{\mathop {99999..}\limits_{{\rm{(up}}\,{\rm{to}}\,\,{\rm{number}}\,\,{\rm{of}}\,\,{\rm{rep}}{\rm{.}}\,\,{\rm{digits)}}} \mathop {000000000}\limits_{\,\,\,\,\,\,\,\,\,\,{\rm{(upto}}\,\,{\rm{number}}\,\,{\rm{of}}\,\,{\rm{non}}\,\,{\rm{rep}}\,\,{\rm{digits)}}} }}} \right]\]

For example the number \(0.2\overline {34} \), 34 is repeating and 2 is non repeating. The equivalent fraction of this number is \(\frac{{234 - 2}}{{990}} = \frac{{232}}{{990}} = \frac{{116}}{{495}}\)

Answer Solution

Answer Solution

Answer Solution

Irrational numbers:

An irrational number is any real number that is not a rational number — that is, it is a number which cannot be expressed as a fraction \(m/n\), where \(m\) and \(n\) are integers, with \(n\) non–zero. The most well known irrational numbers are \(\pi \) and\(\sqrt 2 \).  

• Sum or difference of two irrational numbers may not be irrational.
• Product or division of two irrational numbers may not be irrational.
• Product of one rational and one irrational number may or may not be irrational. For example \(3 \times \sqrt 2 \)is irrational but \(0 \times \sqrt 3 \) is rational. Note that 0 is rational.

The constant \(\pi \) is irrational. 

Example 4: If \(A{\rm{ }} = {\rm{ }}0.{a_1}{a_2}{a_1}{a_2} \ldots  \ldots  \ldots  ..\infty \) and \(B{\rm{ }} = {\rm{ }}0.{b_1}{b_2}{b_3}{b_1}{b_2}{b_3} \ldots  \ldots  \ldots  \ldots ..\infty \), find the minimum positive integer  that should be multiplied to \((A + B)\) so that product is always an integer.

Solution: \(A\) and \(B\) both are repeating decimals

\(A =\frac{{{a_1}{a_2}}}{{99}}\)

\(B = \frac{{{b_1}{b_2}{b_3}}}{{999}}\)

Now the minimum positive integer that should be multiplies to \((A + B)\) to make it an integer will be LCM of 99 and 999 = 10989.

An irrational number is any real number that is not a rational number — that is, it is a number which cannot be expressed as a fraction \(m/n\), where \(m\) and \(n\) are integers, with \(n\) non–zero. The most well known irrational numbers are \(\pi \) and\(\sqrt 2 \).  

1. Sum or difference of two irrational numbers may not be irrational.
2. Product or division of two irrational numbers may not be irrational.
3. Product of one rational and one irrational number may or may not be irrational. For example \(3 \times \sqrt 2 \)is irrational but \(0 \times \sqrt 3 \) is rational. Note that 0 is rational.

The constant \(\pi \) is irrational. 

Example 4: If \(A{\rm{ }} = {\rm{ }}0.{a_1}{a_2}{a_1}{a_2} \ldots  \ldots  \ldots  ..\infty \) and \(B{\rm{ }} = {\rm{ }}0.{b_1}{b_2}{b_3}{b_1}{b_2}{b_3} \ldots  \ldots  \ldots  \ldots ..\infty \), find the minimum positive integer  that should be multiplied to \((A + B)\) so that product is always an integer.

Solution:

\(A\) and \(B\) both are repeating decimals

\(A =\frac{{{a_1}{a_2}}}{{99}}\)

\(B = \frac{{{b_1}{b_2}{b_3}}}{{999}}\)

Now the minimum positive integer that should be multiplies to \((A + B)\) to make it an integer will be LCM of 99 and 999 = 10989.

1. Every perfect square ends with 0, 1, 4, 5, 6 and 9.
2. No perfect square ends with 2, 3, 7 and 8 or odd number of zeroes
3. No perfect square can be of the form of 
   \(4k + 2, 4k + 3,3k + 2, 5k + 2\) and  \(5k + 3\).
4. Last two digits of \({n^2},{\rm{ }}{(50\; - \;n)^2},{\rm{ }}{\left( {50\; + \;n} \right)^2},{(100 - n)^2},{\rm{ }}{\left( {100{\rm{ }} + n} \right)^2}\) etc are same. For example last two digits of \(12^2\), \(38^2\) , \(62^2\), \(88^2\) (and so on) are same i.e. 44.
5. Last two digits of any square are last two digits of one of the squares from 1 to 24
6. Square of a perfect square ends only with 1, 5, 6 or \(4n\) zeroes.

Example 5: A four digit perfect square is of the form aabb, where a and b are the single digits. How many such numbers are possible?

Solution: Since last two digits are same, hence \(b\) can be 0 or 4.  Now \(b\) can not be  0 , because in that first two digits are not same. So \(b = 4\) or number is ending with 44 which means number is of the form of \({(50 \pm 12)^2}\) or \({\left( {100\;-\;12} \right)^2}\). Since aabb is also multiple of 11. so the number can be only \({\left( {100\;-\;12} \right)^2} = {\rm{ }}{88^2} = 7744\). There is only one such number.

Example 6: There is a five digit perfect square in which last two digits are same and non zero, also the number formed by the first three digits is a perfect cube. How many such numbers exist?

Solution: Since last two digits are same, hence last digit can be only 4. So the number can be a square of 112, 138, 162, 188, 212, 238, 262, 288, 312. Out of these number first three digits of only \({112^2}\)\(\) is a perfect  cube. \({112^2} = {\rm{ }}12544\).\(\)

Here is the list of divisibility rules of some important numbers which are frequently asked in questions.

Example 01: If \(a\) and \(b\) are single digits and the number \(234a51b\) is divisible by 72, find the values of \(a\) and \(b\).

The least common multiple or lowest common multiple (LCM) or smallest common multiple of two integers \(a\) and \(b\) is the smallest positive integer that is a multiple of both \(a\) and \(b\). Since it is a multiple, it can be divided by \(a\) and \(b\) without a remainder. For example, the least common multiple of the numbers 14 and 6 is 42.

The unique factorization theorem says that every positive integer number greater than 1 can be written in only one way as a product of prime numbers. The prime numbers when combined together, make up a composite number.

Example : Find the value of  LCM (8,9,21).

Solution: First, factor out each number and express it as a product of prime number powers. The LCM will be the product of multiplying the highest power in each prime factor category together. Out of the 4 prime factor categories 2, 3, 5, and 7, the highest powers from each are \({2^3},{\rm{ }}{3^2},{\rm{ }}{5^0},\) and \({7^1}\). Thus, LCM = 23.32.7 = 504.

Type 1:

Suppose there are certain chocolates which are to be distributed in a class equally among all the students. If we distribute 8 chocolates per head, last student gets only 1 chocolate and if we distribute 5 chocolates per head last student again gets 1 chocolate only. By this data we can conclude that number of chocolates is one more than multiple of 8 and one more than multiple of 5. Hence the number of chocolates = \(8{k_1} + 1{\rm{ }} = {\rm{ }}5{k_2} + 1\).

The same question can be framed as to find the number which when divided by 8 and 5 remainders are 1 in each case. If the remainders are same, the number is of the form of \(8{k_{1\;}} + \;1\; = \;5{k_{2\;}} + \;1\) so the number is LCM of (5 and 8) + 1 = 41.

Or the general number of this type = \(40 k +1\)

General number which when divided by \({n_1},{n_2},{n_3},\)…. remainders are same in each case and is equal to \(r\), is:   \(N k + r\), where \(N\) is LCM of  \({n_1},{n_2},{n_3},\)……

Type 2:

Take the same example as discussed above, there are certain chocolates which are to be distributed in a class equally among all the students. If we distribute 8 chocolates per head, last student gets only 7 chocolate and if we distribute 5 chocolates per head last student again gets 4 chocolate only. By this data we can conclude that number of chocolates is one less than multiple of 8 and one less than multiple of 5. Hence the number of chocolates = \(8{k_1}-{\rm{ }}1{\rm{ }} = {\rm{ }}5{k_2}-{\rm{ }}1\).

The same question can be framed as to find the number which when divided by 8 and 5 remainders are 7 and 4 respectively. 

Or the general number of this type = \(40 k - 1\)

General number which when divided by \(a, b, c\),  remainders are \((a - r), (b - r), (c - r)\) etc., is \(Nk – r\), where \(N\) is LCM of  \(a, b, c,\)……

Example 8: Find the smallest positive number which when divided by 7, 11 and 13, remainders are 6, 10 and 12.

Solution: Number when divided by 7 remainder is 6, which means number is one less than multiple of 7, similarly number is one less than multiple of 11 and 13.  

The remainders are \((7 - 1), (11 - 1)\) and \((13 - 1)\), hence the smallest number is 

(LCM of 7, 11 and 13) – 1 = 1001 – 1 = 1000

Type 3:

In some cases remainders are neither equal nor they form any pattern; in this type of case we use algebraic equation to solve such questions. The following example will explain the complete process 

Example 9: Find the smallest number which when divided by 7, 11 and 13 corresponding remainders are 1, 3 and 4.

Solution: Suppose the required number is \(n\)

\(n = {\rm{ }}7{k_1} + {\rm{ }}1{\rm{ }} = {\rm{ }}11{k_2} + {\rm{ }}3\)

\(7{k_1}\; = {\rm{ }}11{k_2} + {\rm{ }}2{\rm{ }} = {\rm{ }}7{k_2} + {\rm{ }}\left( {4{k_2} + {\rm{ }}2{\rm{ }}} \right)\)

Now  \(\left( {4{k_2} + {\rm{ }}2{\rm{ }}} \right)\) must be multiple of 7, hence \({k_2} = {\rm{ }}3\). Smallest value of the number \(n\) can be \(11x3 + 3 = 36\). Hence \(n\) is off the form of \(77 m + 36\) that should be equal to \(n = 13n + 4\)

Hence \(13n =77m + 32\) or \(13n =78m +26 + (- m + 6)\)

Now \((6 - m)\) should be multiple of 13 or zero. So \(m = 6\). 

Number is \(77 \times 6{\rm{ }} + {\rm{ }}36\; = {\rm{ }}462{\rm{ }} + {\rm{ }}36{\rm{ }} = {\rm{ }}498\)

HCF is the largest factor of two or more given numbers. The same can be defined algebraically as HCF of two or more algebraically expressions is the expression of highest dimension which divides each of them without remainder.

HCF is also called GCD (Greatest Common Divisor).

Product of two numbers = \(LCM \times HCF\)

LCM is a multiple of HCF

\({\rm{LCM}}\;{\rm{of}}\;{\rm{fractions}}\;{\rm{ = }}\cfrac{{{\rm{LCM}}\;{\rm{of}}\;{\rm{Numerators}}}}{{{\rm{HCF}}\;{\rm{of}}\;{\rm{denominators}}}}\)

\({\rm{HCF}}\;{\rm{of}}\;{\rm{fractions}}\;{\rm{ = }}\cfrac{{{\rm{HCF}}\;{\rm{of}}\;{\rm{Numerators}}}}{{{\rm{LCM}}\;{\rm{of}}\;{\rm{denominators}}}}\)

HCF of two numbers is same as

HCF( sum of numbers, LCM of numbers)

Example 01: If the HCF of \({2^3} \times {3^5} \times {7^4}\) and \(n\) is \({2^2} \times {3^5}\), then find the minimum value of \(n\)

Example 02: The LCM of the numbers \(\frac{2}{3},\,\frac{4}{9},\,\frac{8}{{27}}\) is how many times of their HCF.

Suppose we have to calculate the HCF of two higher numbers, finding factors will be difficult, so we go for alternative method, division method. For example suppose we have to find the HCF of the numbers 2520 and 1225, let us first find the factors of the two numbers.

\(2520{\rm{ }} = {\rm{ }}{2^3} \times {3^2} \times {5^1} \times {7^1}\) and \(1225{\rm{ }} = {\rm{ }}{5^2} \times {7^2}\)

Clearly HCF of the two numbers will be \(5 \times 7{\rm{ }} = {\rm{ }}35\).

Some times finding factors is not that easy, in these type of cases we must the following division method. Let’s take the following example.

Example 10: Find the HCF of 4003 and 1003

Solution: 

Last divisor which gives 0 remainder, is the required HCF. Hence HCF in this example is 1.

Highest number which divides \(a, b, c\) leaving remainders \(x, y\) and \(z\) respectively, is HCF of  

\((a - x), (b - y), (c - z)\).

Highest number which when divides \(a, b, c\) leaves the same remainders is:

HCF of \((a - b), (b - c), (c - a)\)

Note that  \((a - b), (b - c), (c - a)\) are the positive difference of two numbers.

Lets try some questions on HCF.

Suppose a number \(N\) can be written as \({a^m}{b^n}{c^p} \ldots ,\) where \(a,b,c\) are prime numbers and \(m,n,p\) are natural numbers. Then 

If   where \(a,b,c\) are prime and \(m, n\) and \(p\) are natural numbers

Number of factors ( or divisors)

 \(= (m+1)(n+1)(p+1)……\)

Factors are formed by taking combinations of powers of \(a\), \(b\) and \(c\), we know that \({a^0},{a^1},{a^2}, \ldots {a^m}\) can be the factors, similarly \({b^0},{b^1},{b^2}, \ldots {b^n}\) and \({c^0},{c^1},{c^2}, \ldots {c^p}.\) Hence total number of combinations \(= (m + 1)((n + 1)(p + 1)\).

Sum of all these factors

 \[= \left[ {\frac{{{a^{m + 1}} - 1}}{{a - 1}}} \right]\left[ {\frac{{{b^{n + 1}} - 1}}{{b - 1}}} \right]\left[ {\frac{{{c^{p + 1}} - 1}}{{c - 1}}} \right]....\]

Example 12: Find the number of factors of the number 360.

Solution:  360 can be written as \({2^3}{3^2}{5^1}\)

Hence number of factors = 4.3.2 = 24

Example 13: Find sum of the factors  of the number 360.

Solution: 360 can be written as \({2^3}{3^2}{5^1}\). Hence sum  of the factors 

 = \(\left[ {\frac{{{2^{3 + 1}} - 1}}{{2 - 1}}} \right]\left[ {\frac{{{3^{2 + 1}} - 1}}{{3 - 1}}} \right]\left[ {\frac{{{5^{1 + 1}} - 1}}{{5 - 1}}} \right]\)=15.13.6 =1170

Example 14: Find the number of even factors of the number 360.

Solution:  The factors of 360 are given as:

Since we have to take only even factors, we can not select \({2^0}\). we can select only \({2^1},{\rm{ }}{2^2},{\rm{ }}{2^3}\). Similarly \({3^0},{\rm{ }}{3^1},{\rm{ }}{3^2}\) and \({5^0},{\rm{ }}{5^1}\) can be selected.

Total number of ways = 3.3.2 = 18 ways.

Total number of factors =18.

Example 15: Find sum of perimeters of all possible rectangles whose area is 360 square units and sides are integers.

Solution: To solve this problem let us assume area of the triangle is 10. Possible rectangles are (1, 10), (2, 5). Sum of perimeters = 2{1+10+2+5} 

= 2 (sum of factors).

Hence required sum of the perimeters 

= 2(sum of all factors)

= 2. \(\left[ {\frac{{{2^{3 + 1}} - 1}}{{2 - 1}}} \right]\left[ {\frac{{{3^{2 + 1}} - 1}}{{3 - 1}}} \right]\left[ {\frac{{{5^{1 + 1}} - 1}}{{5 - 1}}} \right]\) =2340.

Sum of reciprocals of the factors of a number N =\(\frac{{{\rm{sum}}\,\,{\rm{of}}\,{\rm{factors}}}}{N}\)

Example 16: A number \(N\) has \(x\) factors, \(2N\) has \(1.5x\) factors, \(6N\) has \(2.25x\) factors, \(30N\) has \(4.5x\) factors. How many factors does the number \(3600N\) have?

Solution:  Let the number \(N\) is of the form  \({2^m}{3^n}{5^p} \ldots ..\)

Hence \(2N = {\rm{ }}{2^{m + }}^1{3^n}{5^p} \ldots ..\)

\(6N = {\rm{ }}{2^m}^{ + 1}{3^n}^{ + 1}{5^p} \ldots ..\)

\(30N = {2^m}^{ + 1}{3^n}^{ + 1}{5^p}^{ + 1} \ldots ..\)

Ratio of number of factors of \(2N\) and \(N\) would be \(\frac{{m + 2}}{{m + 1}}\) = 1.5 (given) \( \Rightarrow \) \(m = 1\)

Similarly \(n = 1, p = 0\)

Now \(3600N\)  =  \({2^4}{.3^2}{5^2}.N\) =  \({2^m}^{ + {\rm{ }}4}{3^n}^{ + {\rm{ }}2}{5^p}^{ + {\rm{ }}2} \ldots ..\)

Hence number of factors

  \(=  (m + 5)(n + 3)(p + 3)…\)

Ratio of number of factors of \(3600N\) and \(N\) is \(\frac{{(m + 5)(n + 3)(p + 3)}}{{(m + 1)(n + 1)(p + 1)}}\, = \frac{{6.4.3}}{{2.2.1}} = 18\).

Product of all factors of a number \(N\)  

= \({\left[ N \right]^{\frac{{Number\,\,of\,\,factors}}{2}}}\)

Suppose the number 30 is represented as product of two positive numbers. Since 30 has 8 factors.

It is visible that total number of pairs

 = \(\frac{{Number\,\,of\,factors}}{2}\) 

If the number is a perfect square, it has odd number of divisors. For example 36 has 9 divisors.

So total number of pairs having distinct factors =\(\frac{{Number\,\,of\,factor\, - \,1}}{2}\)

So total number of pairs (including distinct and same factors) =\(\frac{{Number\,\,of\,factor\, + \,1}}{2}\)

Example 17: In how many ways 900 can be represented as product of two different natural numbers?

Solution:  The number 900 can be written as \({2^2}{3^2}{5^2}\) 

Hence number of factor are 3.3.3 =27

So the number of ways = \((27 - 1)/2 =13\).

If the number has \(‘n’\) distinct prime factors, then number of ways in which the number can be represented as product of two co–primes \( = {\rm{ }}{2^n}^{-1}\)

Example 18: In how many ways the number 210 can n be represented as product of two co–prime numbers?

Solution: The number 210 can be written as  2.3.5.7.

Hence it has 4 distinct prime factors. Required number of ways = \({2^{4-1}} = {\rm{ }}8\) 

Example 19: If \(x\) and \(y\) are co–prime to each other, find the number of solutions of the equation 

\(xy = 2310\).

Solution: The problem is similar to the one discussed above. But in this case the pairs \((a, b)\) and \((b, a)\)   are different. 2310 can be written as 2.3.5.7.11

So total number of pairs = \(2.\left[ {{2^{5-1}}} \right]{\rm{ }} = 32\) ways . 

[ Every pair has to be counted twice]

Suppose we take a number 10, we are interested in numbers less than 10 and co–prime to 10. These numbers are 1,3,7,9.

Now suppose number \(n\) is \({a^m}{b^n}{c^p}\)

These number of co–primes is generally denoted by Euler’s function \(\phi (n)\).

Then number of positive integers less than \(n\) and co–prime to \(n\) is \(n\left( {1 - \frac{1}{a}} \right)\left( {1 - \frac{1}{b}} \right)\left( {1 - \frac{1}{c}} \right)...\)

Sum of all these numbers = \(\frac{{n\times\phi (n)}}{2}\)

Number of ways in which a number can be represented as sum of two numbers which are co–primes to each other is\(\frac{{\phi (n)}}{2}\)

Example 20: Find number of positive integers which are less than 360 and co–prime to 360.

Solution: The number 360 can be written as 233251

\(\phi (360)\)=\(360.\left( {1 - \frac{1}{2}} \right)\left( {1 - \frac{1}{3}} \right)\left( {1 - \frac{1}{5}} \right)\)=96

Let us have a look on this table showing corresponding remainders, when multiples of 13 are divided by 11.\[\frac{{13}}{{11}} \equiv 2\]\[\frac{{13 \times 2}}{{11}} \equiv 4\]\[\frac{{{{13}^2}}}{{11}} \equiv 4\]\[\frac{{{{13}^3}}}{{11}} \equiv 8\]

here we are using a sign \(\equiv\) for remainder. We observe that if a number is doubled, corresponding remainder is also doubled, similarly if number is tripled, corresponding remainder is also tripled.  This pattern can be proved by using simple algebraic equations. When a number \(p\) is divided by \(q\) remainder is \(r\), so we can write \(p = qk +r,\), then\[2p =2qk +2r\]\[3p =3qk +3r\]\[{p^2} = {q^2}{k^2} + {\rm{ }}2qkr{\rm{ }} + {\rm{ }}{r^2}\].

So to find remainder in a big multiplication or exponent of numbers, we can just replace each numbers by corresponding remainders. For example to find remainder when \(1924 \times 1925 \times 1926\) is divided by 1923.\[\frac{{\mathop {(1924)}\limits^1  \times \mathop {(1925)}\limits^2  \times \mathop {(1926}\limits^3 )}}{{1923}} = {\rm{ }}1 \times 2 \times 3{\rm{ }} = {\rm{ }}6\]

Concept of negative remainder:

\[\frac{{{3^{21}}}}{{14}} \equiv \frac{{{{\left( {{3^3}} \right)}^7}}}{{14}} \equiv \frac{{{{27}^7}}}{{14}} \equiv \frac{{{{( - 1)}^7}}}{{14}} \equiv  - 1\]

Since the final remainder cannot be negative, hence it should be 13.

Example 2: Find the remainder when \(192{4^{192{5^{1926}}}}\) is divided by 1925.

Solution: Since \({1925^{1926}}\) is an odd number, so question is similar to \({1924^{{\rm{odd}}\;{\rm{number}}}}\) is divided by 1925.

\[\frac{{{{1924}^{{\rm{odd}}\;{\rm{number}}}}}}{{1925}} \equiv \frac{{{{( - 1)}^{{\rm{odd}}\;{\rm{number}}}}}}{{1925}} =  - 1\;{\rm{or}}\;1924\]

Example 3: Find the remainder when \({2^{100}}\) is divided by 21.

Solution: Nearest power of 2 that is very close to multiple of 21, is 6. We will split the powers of 2 in the group of 6.\[\frac{{{2^{100}}}}{{21}}\,\, \cong \,\frac{{{{({2^6})}^{^{16}}}{{.2}^4}}}{{21}}\, \cong \,\frac{{{{( - 1)}^{16}}.16}}{{21}}\,\, = \,16\]

Example 4: Find the remainder when  \({\left[ {6!} \right]^{7{!^{8!}}}}\) is divided by 13.

Solution: Since \(6! = 720\) and \({\left( {7!} \right)^{8!}}\) Is multiple of 4, so the question can be written in the form \({720^{4k}}\) is divided by 13.\[\frac{{{{720}^{4k}}}}{{13}}\,\, \cong \,\frac{{{5^{4k}}}}{{13}}\,\, \cong \,\frac{{{{25}^{2k}}}}{{13}}\,\, \cong \frac{{{{( - 1)}^{2k}}}}{{13}}\,\, = 1\]

According to Fermat’s Little Theorem, if \(p\) is a prime number and \(a\) is any integer, then \(({a^p} - a)\) is divisible by \(p\). This is written as \[\bbox[5px, border: 2px solid #0071dc]{a^p \equiv a (\bmod p)}\] This can also be written as \[\bbox[5px, border: 2px solid #0071dc]{a^p - a \equiv 0\,(\bmod \;p)}\]

For example \({2^7} - 2\) is a multiple of \(7\), \({3^{11}} - 3\) is a multiple of \(11\) etc. 

When \(a\) and \(p\) are co-prime, then \({a^{p - 1}} - 1\) is a multiple of \(p\).

This can be summarized as:       

1. If \(p\) is a prime number and a is any whole number, then the number \(a^p - a\) is always multiple of \(p\). For example \(4^{41}-4\) is multiple of \(41\) and \(4^{71}-4\) is multiple of \(71\) etc.
2. If \(p\) is a prime number and a is any whole number, then the number \({a^{p-1}}-1\) is always multiple of \(p\) where \(p\) and a are co–prime to each other.

Example 01: Find the remainder when \({2^{101}}\) is divided by 101.

Solution: We know that \({2^{101}}-{\rm{ }}2\) is always multiple of 101

\(\frac{{\mathop {({2^{101}} - 2}\limits^{} )\,\, + \,\,2}}{{101}}\) = 2

Example 02: Find the remainder when \({2^{71}}\) is divided by 142.

If \(\phi (n)\) represents number of positive integers less than \(’n’\) and co–prime to \(n\),  and a number \(‘a’\) is co prime to \(n\), then 

\({a^{\phi (n)}} \equiv 1(\bmod \,\,n)\), which means when \({a^{\phi (n)}}\)is divided by \(n\), remainder is 1. For example the number 100 has 40 co–primes which are less than 100 and 3 is one of them, hence we can conclude that \({3^{40}}\) when divided by 100, remainder will be 1.

Example 25: Find the remainder when \({11^{401}}\) is divided by 100.

Solution: First we will calculate \(\phi \left( {100} \right)\), that is equal to \(100\left( {1 - \frac{1}{2}} \right)\left( {1 - \frac{1}{5}} \right)\) =40

Now we know that 11 is one of the co–primes of 100. Hence \({11^{40}}\) when divided by 100, remainder is 1.

Now \(\frac{{{{11}^{401}}}}{{100}} = \frac{{{{({{11}^{40}})}^{10}}.11}}{{100}} = 11\)

Example 26: Find the remainder when \({11^{360}}\) is divided by 37.

Solution: First we will calculate the value of (37), that is equal to \(37\left( {1 - \frac{1}{{37}}} \right) =36\).

[Since 37 is prime, hence all the positive integers which are less than 37, will be co–prime to 37]

Now we know that 11 is one of the co–primes of 37. Hence \({11^{36}}\) when divided by 37, remainder is 1.

Now \(\frac{{{{11}^{360}}}}{{37}} = \frac{{{{({{11}^{36}})}^{10}}}}{{37}} = 1\)

If \(p\) is a prime number then \((p - 1)! + 1\) is always divisible by \(p\). 

For example \(18! + 1\) is multiple of \(19, 22! + 1\) is multiple of 23 etc. For example if we have to find the remainder when \(28!\) Is divided by 29, 

We can apply this theorem, we know that \(28!+1\) is multiple of 29, hence when \(28!\) is divided by 29, remainder is -1 or 28.

\(\frac{{28!}}{{29}} = \frac{{(28!\, + 1) - 1}}{{29}} =  - 1\) or \(28\)

Example 27: Find the remainder when \(6.27!\) is divided by 31

Solution: \(6.27!\) can be written as \(1.2.3.27!\)

When \(1.2.3.(27!)\) is divided by 31, remainder is  

\((-30).(-29).(-28)(27!)\) that is equal to \((-30!)\), 

now the remainder is  \(\frac{{ - (30!)}}{{31}} = 1\)

1. \(\left[ {\mathop {nnnn.......nnnn}\limits_{(p - 1)\,times} } \right]\) is always divisible by \(p\), where \(p\) is a prime number more than 5.
2. Any number formed by repeating a digit 4 times is always multiple of 11 and  101
3. Any number formed by repeating a digit 5 times is always multiple of 41 and  271
4. Any number formed by repeating a digit 6 times is always multiple of 3, 7, 11, 13, 37 
5. Divisibility of a number formed by repeating a digit n time can be established by using various divisibility theorems.

In successive division quotient obtained from the previous division is divided by the next divisor. For example if 52 is divided by 3, 4 and 7 successively, corresponding remainders will be 1, 1 and 4 as explained below:

Now let us look at the question from a different angle. Suppose we have to find a number which when divided by 3, 4 and 7 successively the corresponding remainders are 1, 1 and 4. We start the solution backward. Suppose the last quotient is x, that is obtained after dividing the previous dividend by 7, hence previous dividend must be \(7x + 4\). Proceeding in the same manner, we get the number as \(84x + 52\).

Smallest such number is obtained by putting \(x\) as 0, number is 52. Second smallest number is obtained by putting \(x = 1\), number = 136

Example 28: Find the smallest four digit number which when divided by 3, 4, 5 and 6 successively, the corresponding remainders are 1, 2, 3 and 4 respectively. Also find the remainder when this number is divided by 60.

Solution: Proceeding in the same manner as discussed above, we get the following table,

Hence the number is \(360x + 283\), smallest 4 digit number is obtained by putting \(x = 2\), hence the number is \(360 × 2 + 283 =1003\).

Remainder when this number is divided by 60 =\(\frac{{360x + 283}}{{60}}= 43\).

Suppose we have to calculate the power of a prime number ‘\(a\)’  in  factorial \(N\), 

Maximum power = \(\left[ {\frac{N}{a}} \right] + \left[ {\frac{N}{{{a^2}}}} \right] + \left[ {\frac{N}{{{a^3}}}} \right] + ....\)

Where \(\left[ {\frac{N}{{{a^n}}}} \right]\) shows greatest integer function.

Example 29: Find the maximum power of 2, 3 and 6 in \(50!\)

Solution: Powers of 2,

\(\left[ {\frac{{50}}{2}} \right] + \left[ {\frac{{50}}{{{2^2}}}} \right] + \left[ {\frac{{50}}{{{2^3}}}} \right] + \left[ {\frac{{50}}{{{2^4}}}} \right] + \left[ {\frac{{50}}{{{2^5}}}} \right]\)

= 25 + 12 + 6 + 3 + 1 =47

Powers of 3,

\(\left[ {\frac{{50}}{3}} \right] + \left[ {\frac{{50}}{{{3^2}}}} \right] + \left[ {\frac{{50}}{{{3^3}}}} \right]\)= 16 + 5 + 1=22

Powers of 6 can not be calculated by this method as the number 6 is not a prime number. Powers of 6 can be calculated by using pairs of 2 and 3. Since ‘3’ has only 22 powers, hence there are only 22 pairs of 2 and 3. So powers of 6 =22

Example 30: Find the total number of zeroes at the end of 100!.

Solution: To calculate number of zeroes at the end of 100!, we must calculate powers of 10 contained in the number 100! and powers of 10 is the number of pairs of 2 and 5.

Powers of 2 in 100!  =

\(\left[ {\frac{{100}}{2}} \right] + \left[ {\frac{{100}}{{{2^2}}}} \right] + \left[ {\frac{{100}}{{{2^3}}}} \right] + \left[ {\frac{{100}}{{{2^4}}}} \right] + \left[ {\frac{{100}}{{{2^5}}}} \right] + \left[ {\frac{{100}}{{{2^6}}}} \right]\) 

\(=50 + 25 + 12 + 6 + 3 + 1 =97\).

Powers of 5 in 100! =\(\left[ {\frac{{100}}{5}} \right] + \left[ {\frac{{100}}{{{5^2}}}} \right]\) = 20 + 4 = 24.

Hence total powers of 10 = 24 or 

Total number of zeroes at the end of 100! =24.

Example 31: Find the number of zeroes at the end of  \(5 \times 10 \times 15 \times  \ldots  \ldots ..495 \times 500\)

Solution: First we will simplify this number:

Suppose \(N\; = {\rm{ }}5 \times 10 \times 15 \times 20 \times 25 \times  \ldots  \ldots ..495 \times 500\)  

\( = {\rm{ }}{5^{100}}\left( {1 \times 2 \times 3 \times 4 \ldots  \times 99 \times 100} \right)\)

\(N = {\rm{ }}{5^{100}}\left( {100!} \right)\)

or \(N\) has 97 powers of 2 ( as discussed in the above example) and 124 powers of 5. 

Total number of powers of 10 is 97

Hence the number is ending with 97 zeroes.

If we observe pattern of last digit of powers of 2, we find that,

Clearly there is a cycle of 4. We can conclude that every power of 2 ends with either 2, 4, 6 or 8 depending on the power.

If the power is multiple of 4, then the last digit is 6, 

If the power is one more than multiple of 4, then the last digit is 2, 

If the power is two more than multiple of 4, then the last digit is 4, 

If the power is three more than multiple of 4, then the last digit is 8 

Power cycle of 3

Clearly there is a cycle of 4. We can conclude that every power of 3 ends with either 3, 9, 7 or 1 depending on the power.

If the power is multiple of 4, then the last digit is 1, 

If the power is one more than multiple of 4, then the last digit is 3, 

If the power is two more than multiple of 4, then the last digit is 9, 

If the power is three more than multiple of 4, then the last digit is 7 

Power cycle of 7

If the power is one more than multiple of 4, then the last two digits are 07, 

If the power is two more than multiple of 4, then the last two digits are 49, 

If the power is three more than multiple of 4, then the last digit are 43

If the power is multiple of 4, then the last digit is 01

Example 32: Find the last two digits of the number \({7^2008}\)

Solution: Since the power, 2008 is multiple of 4, hence the last two digits will be 01

Example 33: Find the last digit of the number. \({123^{321}} \times {217^{312}} \times {122^{221}}\)

Solution: Last digit of the product depends on only the last digits of the input numbers; hence the question is equivalent to:

\({3^{321}} \times {7^{312}} \times {2^{221}}\)

Last digit of \({3^321} =3\),

Last digit of \({7^312} =1\),

Last digit of \({2^221} =2\),

Hence the last digit of the product is 6

Following numbers show a unique pattern 

\({5^n}\)                 always ends with 25

\({5^{{\rm{odd\,\ number}}}}\) ends with 125

\({5^{{\rm{even\,\ number}}}}\) ends with 625

\({76^n}\)         always ends with 76

\({125^{{\rm{odd\,\ number}}}}\) ends with 125

\({125^{{\rm{even\,\ number}}}}\) ends with 625

\({625^{{\rm{any\,\ number}}}}\) ends with 625

\({376^{{\rm{any\,\ number}}}}\) ends with 376

\({9376^{{\rm{any\,\ number}}}}\) ends with 9376

To find number of digits in a product:

Example 34: Find the number of digits in the number \(212354 \times 6524\).

Solution: The number 212354 can be written as \(2.12354 \times {10^5}\) and the number 6524 can be written as \(6.524 \times {10^3}\). Now the product is  \(\left[ {\left( {2.12354 \times {{10}^5}} \right)\left( {{\rm{ }}6.524 \times {{10}^3}} \right)} \right]\)

That is approximately equal to \(13 \times {10^8} = {\rm{ }}1.3 \times {10^9}\)

Hence number of digits = 10.

Example 35: Find the number of digits before decimal in the product \(\left( {\frac{{1235 \times 98134}}{{1125}}} \right)\)

Solution: The number can be written as 

\(\frac{{{\rm{(1}}{\rm{.235}} \times {\rm{1}}{{\rm{0}}^{\rm{3}}}{\rm{)(9}}{\rm{.8134}} \times {\rm{1}}{{\rm{0}}^{\rm{4}}}{\rm{)}}}}{{{\rm{1}}{\rm{.115}} \times {\rm{1}}{{\rm{0}}^{\rm{3}}}}}\)

\( \approx 10 \times {10^4} \approx {10^5}\). Hence the number has 6 digits.

Example 1: Let \(A\) be the set of prime numbers less than 100. We multiply all the elements of \(A\) to obtain a number \(B\). With how many consecutive zeros will \(B\) end?

Solution: From 1 to 100, there are 2 prime numbers 2, 3, 5, 7, 11,…..97. Out of these numbers only one number is even and only one is containing power of 5, hence total number of zeroes at the end of the product is 1

Example 2: Let \(X\) be the set of integers {1, 7, 13, 19, 25, 31,…. 361, 367} and \(Y\) be a subset of \(X\) such that the sum  of no two elements of y is 368. Find the maximum possible number of elements in \(Y\).

Solution: The numbers in the brackets are in \(AP\), where sum of  first and last is 368, sum of second and second last term = 368,  Out of first and last only one can be selected Out of second and second last only one can be selected \(X\) contains 61 terms, hence total number of term in \(Y = 31\)

Example 3: Let \(p, q, r\) are 3 natural numbers such that \(p + q + r = 3t + 7\), where \(t\) is a positive integer. For a given \(t\), find the minimum possible value of \({p^2} + {\rm{ }}{q^2} + {\rm{ }}{r^2}\) 

Solution: We know that if \(a + b\) is given, their product is maximum when both the numbers are equal and for the same condition, \({a^2} + {b^2}\) will be minimum.

Now in this case, \(p, q\) and \(r\) can not be equal , we will take \(p , q\) and \(r\) as close as possible.

\(p = t + 2, q = t + 2 \) and \(r = t + 3\)

Now \({p^2} + {q^2} + {r^2} = {\rm{ }}3{t^2} + {\rm{ }}14t + 17\)

Example 4: "DELHI SWEET HOUSE" sells laddus in boxes of different sizes. The laddus are priced at Rs.5 per laddu up to 400 laddus. For every additional 10 laddus. The price of the whole lot goes down by 10 paise per laddu. What should be the size of the box that would maximize the revenue?

Solution: Suppose there are \(400 +10x\) laddus, so the price of each laddu will be  \(\left( {5 - \frac{x}{{10}}} \right)\) Rs. Total price of the whole lot =\(\left( {5 - \frac{x}{{10}}} \right)\left( {400 + 10x} \right)\) 

\(= (50 - x)(40 + x)\)

Now sum of \((50 - x)\) and \((40 + x)\) is 90, hence their product is maximum when both are same. \(50 - x\) 

\(= 40 + x\) or \(x = 5\)

Total number of laddus = 450

Example 5: When a number \(p\) is divided by \(q\), remainder is 21, when \(2p\) is divided by \(q\), remainder is 3. Find the value of \(p\).

Solution: When \(p\) is divided by \(q\), remainder is 21. Hence when \(2p\) is divided by \(q\), remainder will be 42. But according to the question, remainder is 3, hence \(q\) is either 39 or 13. Also \(q\) can not be 13 because remainder is 21, hence \(q  = 39\).  

Example 6: Product of three numbers is 8960 and HCF of any two numbers is 4. Find LCM of three numbers.

Solution: Suppose the three numbers are \(4a\), \(4b\) and \(4c\), where \(a, b\) and \(c\) are co prime to each other. Given that \(4a.4b.4c = 8960\) \( \Rightarrow abc = {\rm{ }}140\)

Again LCM of the three numbers \(= 4abc\)

\( = {\rm{ }}4 \times 140{\rm{ }} = {\rm{ }}560.\)

Example 7: If two numbers \(M\) and \(N\) are defined as \(M = (2000)!\) and 

\(N{\rm{ }} = {\rm{ }}2002 \times 2003 \times 2004 \times 2005 \times 2006 \times 2007 \times 2008\). Find LCM of \(M\)  and \(N\).

Solution: The numbers 2002, 2004, 2005,2006 and 2008 are clearly composite, hence these numbers are already contained in and 2000!.

The number 2007 is multiple of 9, hence it is also contained in \(2000!\). The number 2003 is a prime number, hence LCM of the numbers \(M\) and \(N\) will be \(2003 \times 2000!\)

Example 8: Find the number of digits in the number \({1002^{2000}}\).

Solution: The number can be written as

\({(1000 + 2)^{2000}} = {1000^{2000}}{\left[ {1 + \frac{2}{{1000}}} \right]^{2000}}\)

= \({10^{6000}}{\left[ {1 + \frac{1}{{500}}} \right]^{500 \times 4}}\)

As we know that \({\left[ {1 + \frac{1}{n}} \right]^n}\) is very close to 2.7, when \(n\) is a large number, thus the approximate value of \({10^{6000}}{\left[ {1 + \frac{1}{{500}}} \right]^{500 \times 4}}\)will be \({10^{6000}}{(2.7)^4} \approx 50 \times {10^{6000}}\), which contains 6002 digits. Thus the number \({1002^{2000}}\) contains 6002 digits.

Example 9: Find the difference in hundreds and tens digit of the three digit number \(abc\) if \(\left[ {\frac{{100a + 10b + c}}{{a + b + c}}} \right]\)is minimum.

Solution:  Since the number is a three digit number, hence \(100a + 10b + c > 100 and a + b + c < 27\), hence to minimize the number \(\left[ {\frac{{100a + 10b + c}}{{a + b + c}}} \right]\), \(c\) must be maximum, because on increasing \(c\), percentage change in \(a + b + c\) is more than that in \(100a + 10b + c\). 

Thus \(c = 9\). Also a should be minimum, because on increasing \(a\), the number \(100a + 10b + c\) increases rapidly. Thus \(a = 1\).

Now \(\left[ {\frac{{100a + 10b + c}}{{a + b + c}}} \right]\)= \(\left[ {\frac{{109 + 10b}}{{10 + b}}} \right]\).

Now increasing \(b\) will increase denominator more rapidly as compared to numerator as

\(\frac{{10}}{{109}} < \frac{1}{{10}}\), thus b must be largest.

Hence \(a = 1, b = 9\) and \(c = 9\) 

Example 10: If \(a, b\) and \(c\) are three single digit numbers such that \((a + b + c)! = 90(abc)\), where \(abc\) is the product of \(a, b\) and \(c\).

Solution: From the given condition it is clear that \((a + b + c)!\) is a multiple of 90. 

Thus  \((a + b + c) = 6\) or \(7\) 

as \(6! = 720\) and \(7! = 5040\).

But if we take \(a + b + c = 7\), then

\(abc = \frac{{5040}}{{90}} = 56\), which is not possible. 

Thus \(a + b + c = 6\) and \(abc = \frac{{6!}}{{90}} = 8\)

So there is only one possibility \((a,\,b,\,c) = (2,\,2,\,2)\)