Important Concepts in Number Theory  Kamal Lohia

kamal_lohia last edited by kamal_lohia
Faculty and Content Developer at Tathagat  Delhi College of Engineering
Counting & Summation
How many 1 digit natural numbers are there?
9 (1 9)How many 2 digit natural number are there?
90 (10  99)How many 3 digit natural numbers are there?
900 (100  999)How many ndigit natural numbers are there?
I hope you got the pattern by now. 9 × 10^{n1}Palindromes are the numbers which read same forward and backward.
How many palindrome numbers are there less than 1 million?
1  Digit palindromes (a) = 9
2  Digit palindromes (aa) = 9 × 1 = 9
3  Digit palindromes (aba) = 9 × 10 × 1 = 90
4  Digit palindromes (abba) = 9 × 10 × 1 × 1 = 90
5  Digit palindrome (abcba) = 9 × 10 × 10 × 1 × 1 = 900
6  Digit palindromes (abccba) = 9 × 10 × 10 × 1 × 1 × 1 = 900
So total number of palindromes less than 1 million is = 2(9 + 90 + 900) = 2(999) = 1998.
How many times you write digit 1 while writing all natural numbers from 1 to 1000?
No need of hectic work. Just see that if we write numbers from 000 to 999, then each digit from 0 to 9 is being used at each place equally. And total number of digits being used to write these 1000 3digit numbers (from 000 to 999) is 3000. So digit 1 has been used 3000/10 = 300 times from 1 to 999 and once in 1000. So final answer becomes 300 + 1 = 301. Please read it patiently. I am sure it'll be clear to you easily.
How many times you write digit 0 while writing all natural numbers from 1001 to 2000?
This should not be any problem anymore. Answer is 300.
Just see that from 000 to 999, we write 1000 numbers using each of the digit from 0 to 9 being used at every place equally i.e. 3 × 1000/10 = 300 times each. And in this question, we have numbers from 1001 to 2000. Just remove the thousandth digit and arrange remaining digits accordingly. Isn't it simple? :)
If we write all natural numbers from 1 to 99, then how many of them contain digit 1?
Read carefully. Answer is 19 not 20 :)
While writing all natural numbers from 100 to 199, how many contain digit 1?
That was easy. It's 100 :)
Now a CAT like problem
To write all the page numbers of a book, exactly 136 times digit 1 has been used. Find the number of pages in the book.
From 1 to 99, 20 times digit 1 is used.
From 100 to 199, 120 times digit 1 is used.
So, total pages should be 4 less than 199 i.e.195.
Another (Last for now) type of counting.
All the page numbers of a book has been added and sum was found to be 1000. But teacher told that one page number has been mistakenly added 3 times. Can you identify the mistakenly added page number?
a. 5 b. 10 c. 27 d. cannot be determined
Number of pages, n should be such that n (n + 1)/2 < 1000. We get approximately n < 45.
For n = 44, Sum = 990 i.e. 10 = twice the sum of mistakenly added number (say X ) i.e. X = 5.
For n = 43, Sum = 946 i.e. 54 = 2X or X = 27.
No other values satisfy. So answer can be 5 or 27. (d)
Finding the SumSum of first 'n' consecutive natural numbers is a three digit number whose digits are same. Find 'n'.
1 + 2 + 3 + ...+ n = n (n + 1)/2 = aaa = a (111) = a × 3 × 37
i.e. n (n + 1) = a × 2 × 3 × 37
As ‘a’ is a single digit number, only a = 6 satisfies. That is n = 36.
Sum of five consecutive integers is A. Find the sum of next five consecutive integers.
Each corresponding term in the next five consecutive integers is at a gap of 5 from its counterpart in previous five consecutive integers.
That means the required sum is A + 25.
In General: If sum of n consecutive integers is A, then sum of next n consecutive integers is A + n^{2}.
Sum of four 2digit consecutive odd integers when divided by 10 results in a perfect square. How many such sets of four 2digit numbers are possible?
Four consecutive 2digit numbers will have average as an even number situated between two central odd numbers. So certainly it'll be a 2digit number.
That means sum of four numbers should be of the form S = 4 × Avg but this need s to be of the form 10 × a^{2 }also.
That means Avg should be a two digit number of the form 10 × b^{2 }where b is a single digit number. (Think why??)
Only possible values for b are 1, 2 or 3 so that Avg remains a 2digit number.
But b = 1 is negated as in that case all four numbers will not be 2digit numbers.
So TWO cases are possible(i) Avg = 10 × 2^{2 }= 40 i.e. numbers are 37, 39, 41, 43 And (ii) Avg = 10 × 3^{2 }= 90 i.e. numbers are 87, 89, 91 and 93.
Sum of first n consecutive natural numbers is a perfect square for n = 1, 8. Find next two such values.
I am leaving its explanation for you to do on your own. Answer is 49 and 288.
S = (n) (n+1)/2, so either n, or n+1 has to be the 2nd multiple of a perfect square Check for all odd perfect squares and its neighbors.
Digit Sum & Last digit(s)
Digital sum of a number is the single digit obtained by adding all the digits of a number continuously. Important point to observe is that ‘Digital Sum’ of a number is nothing but its remainder when divided by 9 :)
For example: DS (12345) = DS (1+2+3+4+5) = DS (15) = DS (1+5) = DS (6) = 6.
Let’s take one more: What is the sum of sum of sum of digits of 25! Where n! is product of first n positive integers starting from 1?
As 25! < 10^{25 }
So sum of digits of 25! Is certainly less than or equal to the sum of digits of greatest number less than or equal to 10^{25 }which is for 9999… 25 digits= 9 + 9 + … 25 digits= 225.
With similar logic sum of sum of digits of 25! Is certainly less than or equal to the sum of digits of greatest number less than or equal to 225 which is for 199 = 1 + 9 + 9 = 19.
Same way sum of sum of sum of digits of 25! Is certainly less than or equal to the sum of digits of greatest number less than or equal to 19 which is for 19 = 1 + 9 = 10.
That means required answer cannot be more than 10. But, also, we know that 25! Is a multiple of 9, so sum of sum of sum of digits of the number will always be multiple of 9.
So answer here is 9.
Confusing??? Let’s take easier one this time :)
Find the digital sum of 7^{100}
We just need to find the remainder of the number with 9. Answer is 7 and explanation, I am leaving for the reader.
Concept of digital sum finds its use in mainly checking calculations or in, a better manner, eliminating options in an exam like CAT.
Some properties of Digital Sum:
If two numbers are multiplied to give an answer, then we can check the calculation using concept of digital sum. Digital sum of product of digital sums of the two numbers will be same as the digital sum of the answer.
E.g. 25 × 35 = 875
DS (25) = 7
DS (35) = 8
DS (7 × 8 ) = DS (56) = DS (5 + 6) = DS (11) = 2
Also DS (875) = DS (8 + 7 + 5) = DS (20) = 2.
Remember, if digital sum of the product is not matching, then there IS some calculation error certainly. But vice versa is not true. That is, matching of digital sum doesn’t ensure whether product is correct or not.
Digital sum of perfect squares is 1, 4, 7 or 9. (Again that doesn’t say that every number with a digital sum of 1, 4, 7 or 9 is a perfect square).
Digital sum of perfect cubes is always 1, 8 or 9.
Last digit of a numberWe know that unit digit of the number 2012 is 2.
what is the unit digit of 2012 × 2012?
Certainly it is 4 as it depends only on the unit digits of the numbers being multiplied 2012 × 2012 i.e. 2 × 2 = 4.
what is the unit digit of 2012 × 2013 × 2014?
With similar logic, it also depends on the unit digit of numbers being multiplied 2012 × 2013 × 2014 i.e. 2 × 3 × 4 i.e. unit digit of 24 i.e. 4.
Next a better problem: What is the unit digit of 2012^{2012}?
With the logic discussed above, unit digit of 2012^{2012 }depends on unit digit of 2^{2012}.
Now we observe a pattern in the unit digits of all the digits as follows:
So we find that after every fourth power, unit digit of powers of 2 starts repeating. Strange and important point is that, it is true for all digits. Some repeat at every power (e.g. 0, 1, 5, 6), some after every two powers (e.g. 4, 9) and remaining after every fourth power (e.g. 2, 3, 7, 8 ).
The numbers which give same last digit as itself, when raised to any positive integral power are known as singledigit Automorphic numbers and they are 0, 1, 5, 6. Similarly 2digit automorphic numbers are 00, 01, 25 and 76. We’ll use them later. :)
This is the table of the unit digits of powers of all the digits (i.e. numbers of the form a^{b})
You don’t need to mug up the table. But this is just for your reference. You can always count mentally the unit digits of any digit up to its fourth power. Important Point to observe is that fourth power of all even digit (except 0) ends in 6 and that of all odd digits (except 5) ends in 1.
HOW TO FIND LAST TWO DIGITS OF A NUMBERAs unit digit depends on product of unit digits of the numbers being multiplied, same way last two digits of a number depends on the product of last two digits of the numbers being multiplied.
That means Last two digits of 2012 × 2013 = TD(12 × 13) = TD(156) = 56.
A question for you now: What are the last two digits of 2012 × 2013 × … × 2031.
It’s simple. Answer is ZERO. Because the product contains enough 5’s and 2’s (e.g. 2025 and 2012).
Now comes the important point for which this topic was written. Please read every word carefully. I am not giving the reason behind every step. So please be cautious that it is to be used Asitis. No malfunctioning should be done without expertise.
LAST TWO DIGITS OF A NUMBER ENDING IN 1
71^{83} : Unit digit (UD) of this number is always going to be 1 (because 1 is a single digit Automorphic number, as told above). And ten’s digit is obtained by unit digit of product of ten’s digit of the number (7 here) with unit digit of exponent (3 here).
That means TD(71^{83}) = UD(3 × 7)1 = UD(21)1 = 11
I hope this is clear.
Let’s take one more example:
Find the last two digits of 561^{165}.
Now TD (561^{165}) = TD(61^{165}) = UD(5 × 6)1 = UD(30)1 = 01.
One more: Find the last two digits of 79^{78}.
Caution – You cannot directly use the method here as the unit digit of the base number is not 1. But remember, as we talked earlier, every odd digit (except 5) can be raised to a positive integral power such that it’s unit digit becomes 1.
So we first need to convert the base number’s unit digit to be 1 by using some part of exponent.
TD(79^{78}) = TD(79^{2})^{39 }= TD(41^{39}) = UD(9 × 4)1 = UD(36)1 = 61.
Important points to remember:
Last two digits of (50n + x)^2 = Last two digits of (50n  x)^2 = Last two digits of x^2 (x and n are integers)
Last two digits of a number are same as the remainder obtained when the number is divided by 100.
LAST TWO DIGITS OF EVEN NUMBERS
Every even number contains some odd part and some even.
For example 62^{31 }can be written as 2^{31 }× 31^{31}.So to find the last two digits of an even number, we just need to know how to find last two digits of powers of 2, in addition to previously acquired knowledge.
Now, again, automorphic number comes to rescue. I told you above that 76 is two digit automorphic number i.e. which when raised to any positive integral power, always ends in 76 as last two digits.
i.e. TD(76^{n})= 76.
For your good fortune, 20 is the smallest power of 2 which ends in 76. That means TD(2^{20k}) = 76 where k is a positive integer.
Also one more property is associated with 76.
i.e. TD(76 × 2^{n}) = 2^{n }where n is a positive integer greater than 1.
Let’s take an example: Find the last two digits of 2^{2012}.
TD(2^{2012}) = TD(2^{20})^{100 }× TD(2^{12}) = TD(76)^{100 }× TD(2^{12}) = TD(76 × 2^{12}) = TD(2^{12}) = 96.
I hope this is clear.
Basic concepts of Remainders
What is the remainder when 2007 is divided by divided by 7?
It is simple; just divide 2007 by 7 to get the remainder as 5.
Did anybody use any shortcut in this?
I'll tell you later :)
Another simple one:
What is the remainder when 2008 is divided by 7?
Now it is smarter to use the earlier known data from previous question.
If 2007 = 7a + 5
Then certainly 2008 = 2007 + 1 = 7a + 5 + 1 = 7a + 6.
Ok. Next one.
What is the remainder when 2007 × 2008 is divided by 7?
It is simply (5 × 6) = 2 mod 7.
Most of you use it some knowingly and some unknowingly too.
Funda is simple: Remainders of product of some numbers is obtained by product of individual remainders of the number with same divisor.
As 2007 = 7a + 5 and 2008 = 7a + 6
So 2007 × 2008 = (7a + 5)(7a + 6) = (7a)^{2 }+ (5 + 6)7a + 5 × 6 = 5 × 6 mod 7 = 2 mod 7.
Question was simple but important learning is as said above that "Remainder of Product of some number depends on Product of their individual Remainders with same divisor."
One more thing to tell (for those who are unaware of the 'alien' phrase MOD):
When I say 31 = 3 mod 7, that mean 31 is a number of the form 7a + 3 OR in other words, we can also say 31 leaves remainder 3 when divided by 7. So just to avoid this long sentence every time, we use this internationally used term 'mod'. I hope it'll trouble you no more throughout the session.
Li'l advanced:
What is the remainder when (2007 × 2007 × 2007.... 2007 times) (2008 × 2008 × 2008....2008 times) is divided by 7?
It is equivalent to (2007^{2007}) (2008^{2008}) mod 7 = (5^{2007}) (6^{2008}) mod 7.
Now observe that 5 mod 7 = 2 mod 7 and also 6 mod 7 = 1 mod 7.
Remember that term before 'mod' doesn't always give the remainder. It tell us only the form of the number. e.g. 5 mod 7 = 7a + 5 = 7a + 7  2 = 7(a + 1)  2 = 2 mod 7.
Hope you got it. Now observe one more thing that we can also write:
5 mod 7 = 2 mod 7 = 9 mod 7 = 16 mod 7 and also
5 mod 7 = 12 mod 7 = 19 mod 7 = 26 mod 7.
That means you can add/subtract the divisor any number of times from the number before 'mod' and it'll not change the form of the number.
You'll realize it's use later in the session.
Back to problem, we need to find {(2) ^{2007}} × {(1) ^{2008}} mod 7 = (2^{2007}) mod 7.
Further we see that 2^{3 }= 8 = 1 mod 7.
So (2^{2007}) mod 7 = (2^{3})^{669 }mod 7 = 1 mod 7 = 6 mod 7.
What is the remainder when 2007^{2008 ^ 2009 }is divided by 7?
We have seen from previous question that 2007 = 2 mod 7
So 2007^{ 2008^2009 }= (2)^{2008^2009 }mod 7 = (2^{2008^2009}) mod 7.
Also we saw that 2^{3 }= 1 mod 7. So we need to see whether the power of 2 (i.e. 2008^{2009 }here) is divisible by 3 or not.
That means we have a sub question in the original question that to find the remainder of 2008^{2009 }by 3.
Now 2008^{2009 }= 1^{2009 }mod 3 = 1 mod 3 (as 2008 = 1 mod 3)
Using this info in previous part, we get 2007^{2008^2009 }= (2^{{3k+1}}) mod 7 = 2 × (2^{3})^{k }mod 7 = 2 mod 7
Please read it slowly to grasp the logic completely.
EULER's Theorem and Euler's Totient Function
Now we know what remainder is and how to find it. But many of you might be thinking that in earlier questions we found 2^{3}= 1 mod 7 manually. What if the number is much larger and divisor is also larger number so that just by seeing, we cannot say anything specific.
So for your comfort, EULER made a theorem which says
M^{phi(N) }= 1 mod N
where HCF(M, N) = 1 and phi(N) = Euler's Totient Function = number of numbers less than N and coprime to N.
For those who don't know how to find phi(N), again EULER comes to rescue. So cheers. :)
If N = (a^{p}) × (b^{q}) × (c^{r})....where a, b, c are distinct primes and p, q, r are their respective powers
Then phi(N) = N(1  1/a)(1  1/b)(1  1/c)....
How many numbers less than 101 are coprime to 100?
It is simply phi(100) = 100(1  1/2)(1  1/5) = 40.
How many numbers less than 2100 are multiples of 3 but not multiple of 2, 5 and 7?
It is simply phi(700) = 700(1  1/2)(1  1/5)(1  1/7) = 240. Can you think why??
How many numbers less than 1200 are not divisible by 15 but divisible by 12?
It means number should be divisible by 3 and 4 but not by 5. So it is 1200(1/3)(1/4)(4/5) = 80.
Try to grasp what I have done.
This is a very simple logic that "Out of every three consecutive numbers, exactly one is divisible by 3 and two are not". Similarly "Out of every four consecutive numbers, exactly one is multiple of 4 and three are not" and so on. So just use it. But remember, there is one condition to abide by. If I am considering divisibility or nondivisibility by 2, 3, 5 (say), then my total number should be multiple of / divisible by 2, 3 and 5. Otherwise, you won't get the integral answer. And never try to be over smart by rounding offs or taking some nearest integer or something else.
how many of first 100 numbers are multiple of 2 and 5 but not of 3
First take a number nearest to 100 which is multiple of 2, 5 as well as 3 i.e. 90.
So till 90, we get the required numbers as (1/2)(1/5)(2/3)(90) = 6.
And after that we have 100 i.e. 1 more. So answer will be 7.
Another type of questions:
Find the sum of all the numbers less than 101 which are coprime to 100.
As we used the symmetry pattern of numbers in previous problem, that out of every 'n' consecutive numbers exactly 1 is divisible by n and remaining (n  1) are not. Similarly, here, when I remove the multiple of 2 or 5 from first 100 numbers, the remaining coprime numbers also depicting a pattern. Can you identify this?
See and try to learn the logic:
Among first 100 natural numbers, what is the pattern besides that each number is obtained by adding 1 to previous one?
There is one more (which is applicable to basically in all APs) , that sum of first and last is same as sum of second and secondlast and so on.
Similarly, when we have only 'coprime to 100' numbers left with us, which are 40 in number as calculated in F1, they also appear in such pattern that "sum of First and last is same as sum of second and secondlast and so on" And each of this sum is equal to 100.
Alternately, you can think of any two numbers less than 100 whose sum is 100.
x + y = 100.
So if x is multiple of 2, then y is also.
If x is not multiple of 2, then y also can't be multiple of 2.
Similarly, for 5 also.
That means if x is not multiple of 2 as well as 5 i.e. 2 is coprime to 100, then y is also coprime to 100.
That means for every coprime number less than 100, there is another which adds up to the previous one and make the sum 100.
So, answer for this question becomes 20 × 100 = 2000.
Similar one...
Find the sum of the numbers which are less than 2100 and are multiples of 3 but not multiple of 2, 5 and 7?
With same logic, it is 120*2100 = 252000.
Find the sum of the numbers which are less than 1200 and are not divisible by 15 but divisible by 12?
It's not a magic trick anymore. Answer is 40*1200 = 48000.
For how many values of n, phi (n) is odd? For example if n = 2, phi (2) = 1 is odd.
There are no more of such values. :)
Remainder Theorems
Fermat’s Theorem: M^{p }– M is divisible by p where p is a prime number and HCF(M, p) = 1
i.e. M^{p }= M mod p
For example: 2^{7 }– 2 is divisible by 7 or 2^{7 }= 2 mod 7.
Fermat’s Little Theorem: M^{p  1 }= 1 mod p where p is a prime number and HCF(M, p) = 1.
In later years, Euler generalize it for nonprimes also as
Euler’s Theorem: M^{phi(N) }= 1 mod N where phi(N) is Euler’s Totient function and HCF(M, N) = 1
We discussed Euler’s Totient Function already.
Let's use this to find remainders.
Find the remainder when 53^{54 }is divided by 19.
That’s easy one.
As HCF(53, 19) = 1, we can use Euler’s theorem or Fermat’s theorem as 19 is a prime number.
So we know that 53^{18 }= 1 mod 19
i.e. (53^{18}) (53^{18}) (53^{18}) = 53^{54 }= (1)(1)(1) mod 19 = 1 mod 19.
What should be added to 21^{22 }so that it is divisible by 23?
we know that 21^{22 }= 1 mod 23 as 23 is a prime number and HCF(21, 23) = 1. (Fermat’s Theorem)
So we must add 22 to the number to make it divisible by 23.
What are the last two digits of 79^{121}?
Don't worry, last two digits of a number is it's remainder only when it is divided by 100. That means you are to find the remainder of the number with 100.
As 100 and 79 are coprime, we can use Euler's th. Also phi(100) = 40.
So 79^{40 }= 1 mod 100
and 79^{121 }= 79 mod 100.
What if Number and divisor are not coprime i.e. HCF(M, N) is not equal to 1?
No issues: Just take the HCF of the number and divisor our and fond remainder of remaining number with remaining divisor.
Final answer will be HCF times the remainder obtained by remaining number and remaining divisor.
Find the remainder when 2^{32 }is divided by 32.
Don’t get bewildered by the trap. Answer is zero. :D
Find the remainder when 3^{12 }is divided by 12.
Now HCF of number and divisor is 3.
So the required remainder will be 3*[3^{11 }mod 4] = 3(1) mod 12 = 9 mod 12.
MOD  We talked something about the phrase/operation earlier also. Let’s repeat them and try to be more familiar with it. When I say 31 = 3 mod 7, that mean 31 is a number of the form 7a + 3 OR in other words, we can also say 31 leaves remainder 3 when divided by 7. So just to avoid this long sentence every time, we use this internationally used term 'mod'.
Remember that term before 'mod' doesn't always give the remainder. It tell us only the form of the number e.g. 5 mod 7 = 7a + 5 = 7a + 7  2 = 7(a + 1)  2 = 2 mod 7.
Hope you got it. Now observe one more thing that we can also write:
5 mod 7 = 2 mod 7 = 9 mod 7 = 16 mod 7 and also 5 mod 7 = 12 mod 7 = 19 mod 7 = 26 mod 7.
That means you can add/subtract the divisor any number of times from the number before 'mod' and it'll not change the form of the number.
Also if we say that 21N = 7 mod 8
That means 7*3N = 7*1 mod 8
Or 3N = 1 mod 8
Or 3N = (1 + 8 ) mod 8 = 9 mod 8 = 3*3 mod 8
That means N = 3 mod 8.
Read every step carefully.
Now let’s use this in remainder problems
If 20N is divisible by 7, find the remainder when N + 20 is divided by 7.
It’s simple to get that N = 0 mod 7
So N + 20 = (0 + 20) mod 7 = 20 mod 7 = (20 – 7 – 7) mod 7 = 6 mod 7.
If 37N = 5 mod 41, find the remainder when N is divided by 41.
37N = 5 mod 41
(37  41) N = 4N = 5 mod 41
4N = 5 mod 41 = (5 + 41) mod 41 = 36 mod 41 = 4*9 mod 41
N = 9 mod 41.
Solve one more to get hold of concept.
Find the smallest natural number N such that 13N = 17 mod 19.
13N = 17 mod 19
(13  19)N = (17  19) mod 19
6N = 2 mod 19
3N = 1 mod 19 = (1  19) mod 19 = 18 mod 19 = 3(6) mod 19
N = 6 mod 19 = 13 mod 19.
Do 5 more problems on this.
Find smallest N such that
i. 31N = 5 mod 17
II. 23 N = 15 mod 19
III. N(N+1) = 2 mod 20
iv. 14N = 3 mod 23
v. 213N = 102 mod 315
Solutions:
i. 31N = 5 mod 17
3N = 12 mod 17
N = 4 mod 17.
ii. 23N = 15 mod 19
(23  19)N = (15+19+19+19) mod 19
4N = 72 mod 19
N = 18 mod 19.
iii. N(N+1) = 2 mod 20
N(N+1) = 1(1 + 1) mod 20
N = 1 mod 20
BUT also, N(N+1) = (2 + 20 + 20) mod 20 = 6(6 + 1) mod 20
So N = 6 mod 20 is also possible.
Also, N(N + 1) = (2 + 180) mod 20 = 13(13 + 1) mod 20
So N = 13mod 20 is also possible.
Similarly N(N + 1) = (2 + 340)mod20 = 18(18 + 1) mod 20
So N = 18 mod 20 also possible.
That means there four possible values of N i.e. 1, 6, 13, 18 mod 20. But smallest is of course 1.
iv. 14N = 3 mod 23
9N = 3 mod 23
3N = 1 mod 23 = 24 mod 23
N = 8 mod 23 = 15 mod 23.
v. 213N = 102 mod 315
102N = 102 mod 315
N = 1 mod 315
N = 314 mod 315
We will do a better problem now.
Find the remainder when 39^{39 }is divided by 41.
Using Euler’s we know that 39^{40 }= 1 mod 41 as HCF(39, 41) = 1
Let’s say 39^{39 }= x mod 41.
39^{40 }= 39 × 39^{39 }= 1 mod 41
39x = 1 mod 41
2x = 40 mod 41
x = 20 mod 41.Next type of problems: If divisor is composed of more than one prime number, then we can break it into its coprime factors and find the individual remainders and then combine them.
Find the remainder when 2^{77 }is divided by 77.
You can directly use phi(77) = 60. But then it’ll be lengthy to find the remainder of 2^{17 }with 77.
So it’s better to find the remainder individually with 7 and 11 and then combine them.
Now 2^{77 }= [(2^{6})^{12}][2^{5}] = 2^{5 }mod 7 = 4 mod 7. (as phi(7) = 6 and HCF(2, 7) = 1)
And 2^{77 }= [(2^{10})^{7}][2^{7}] = 2^{7 }mod 11 = 4 mod 11. (as phi(11) = 10 and HCF(2, 11) = 1)
Now comes the big problem: HOW TO COMBINE THESE REMAINDERS TO GET THE REMAINDER WITH 77.
There are three different methods you can do that.
First is COMMON TERM FINDING method
Write the sequence of numbers 4 mod 7 i.e. 4, 11, 18, 25, 32, 39, …… and
4 mod 11 i.e. 4, 7, 18, 29, ……………
AND we are to just find the smallest common number which is there in both the sequences. 18 it is.
Second is USING EQUATIONS
Write the equation for remainder R = 7a + 4 = 11b – 4
i.e. 7a = 11b – 8 = 7b – 7 + 4b – 1
As LHS is divisible by 7, RHS must be.
So we need to find the smallest b such that 4b – 1 is divisible by 7 and voila... b = 2 satisfies.
That means R = 11*2 – 4 = 18.
Third is imported one CHINESE REMAINDER THEOREM
First step: The two divisors, to be combined, should be coprime
Second step: Write an equation using the two divisors such that the difference between the integral multiple of two divisors is 1.
So in this case we get 11 × 2 – 7 × 3 = 1
Now remainder is obtained by multiplying an extra term with each term of LHS i.e.remainder of the other divisor.
So it becomes [11 × 2 × 4 – 7 × 3 × (4)] mod 77 = (88 + 84) mod 77 = (11 + 7) mod 77 = 18 mod 77.
How many four digit numbers exist such that when divided by 7, 9 and 11 one gets the remainders of 2, 3 and 4 respectively.
7a + 2 = 7a + 2  350 = 7a  348 9b + 3 = 9b + 3  351 = 9b  348 11c + 4 = 11c + 4  352 = 11c  348 So N = 7 × 9 × 11d  348 = 693d  348 = 693d + 345
Here remainders from the three numbers have difference of 1. So I just need to found their multiple with gap of 1 as above and job is done.
And it is also not time consuming as multiple of 11 should give digit sum 1 as it had to be one more than multiple of 9 and multiple of nine will always give digital sum 9 or 0. So 11 (digital sum 2) should be multiplied with a number with digital sum 5 i.e. 5, 14, 23, 32, 41, ...etc. Automatically number one less than this will be multiple of 9. So I just need to check whether number one more less than this multiple of 7 or not.....
General divisibility rules
a^{n }+ b^{n }is divisible by a + b if n is an odd natural number.
a^{n }– b^{n }is divisible by a + b if n is an even natural number.
a^{n }– b^{n }is divisible by a – b if n is any natural number.
a^{n }+ b^{n }+ c^{n }+ … is always divisible by (a + b + c + …) if a, b, c, …are in AP and n is an odd natural number.P(x) is divisible by (x  a) iff P(a) = 0
P(x) gives remainder P(a) when divided by (x  a)
Any (p  1) digit repunit number is always divisible by p where p is a prime number greater than 5.
I can go on forever with this. But I’ll have to stop now. :)
Writing A Number As Sum Of Two Or More Consecutive Positive Integers
In how many ways can 2010 be written as sum of two or more than two consecutive positive integers?
For example: 2010 = 669 + 670 + 671.
Now every number can be written as a sum of consecutive integers.
Ex (3)+(2)+(1)+ 0 + 1+ 2+ 3+ 4 = 4
But not all numbers can be written as sum of consecutive positive integers.
A number can be written as the sum of consecutive positive integers if, and only if, its prime factorization includes an odd prime factor; then, since 2 is the only even prime number, the conclusion is that the powers of 2 are the only numbers that cannot be written as the sum of consecutive positive integers.
Number of ways to write a natural number, N as sum of two or more than two consecutive positive integers is given by number of odd positive integral divisors of N  1. So in this particular question, number of odd divisors of 2010 is 8. hence the required number of ways = 7.
Now take an example of 36.
now 361=35 has four positive odd integral divisors. So 36 can be expressed as sum of two or more positive consecutive integers in four possible ways. But how to construe those ways if the number is large?
Ex 60; 601=59; 59 has two odd divisors, but the number of ways to express 60 as sum of consecutive positive integers is three:
60 = 19+20+21 = 10+11+12+13+14 = 4+5+6+7+8+9+10+11
Also in how many ways can any natural number be expressed as sum of consecutive positive even integers or consecutive possible odd integers?
Number of ways to write a natural number,N as sum of two or more than two consecutive natural numbers = (number of odd divisors of N)  1.
If N = 36, then the required number of ways are = 3  1 = 2.
If N = 60, then required number of ways are = 4  1 = 3.Now if question is to find the number of ways to write a natural number,N as sum of two or more than two consecutive even natural numbers, then first condition is that n must be an even number. Number of ways remains same as above. Let's check for 60.
60 = 3*20 = 5*12 = 4*15
So, 60 = 18 + 20 + 22 = 8 + 10 + 12 + 14 + 16 = 12 + 14 + 16 + 18.Now if question is to find number of ways to write a natural number,N as sum of two or more than two consecutive odd natural numbers, then N has to be an odd number or a multiple of 4. Number of ways can be calculated accordingly.
Perfect Squares
Some Properties (Square of integers)
Unit Digit of a perfect Square cannot be 2, 3, 7 or 8.
Ten's digit of a perfect square is always even except when unit digit of perfect square is 6.
Digital sum of a perfect square is 1, 4, 7 or 9.
All perfect squares are of the form 3a or 3a + 1.
All perfect squares are of the form 4a or 4a + 1.
All perfect squares are of the form 5a or 5a + 1 or 5a  1.
How many numbers of the set S {1, 11, 111, … } are perfect squares?
Only 1. As all other numbers are of the form 4a + 3 which cannot be a perfect square.
How many numbers of the set P{4, 44, 444, 4444, ....} are perfect squares?
again only 4 is perfect square.
How many five digit perfect squares can be formed by using the digits 1, 2, 3, 4, 5 exactly once?
None. As digital sum of the number will be (1 + 2 + 3 + 4 + 5) mod 9 = 6 which is not possible for a perfect square.
Find the number of positive integral pairs (a, b) such that a^{2 }+ b^{2 }= 1000.
As RHS is multiple of 4, both terms at LHS should be of the form 4k i.e. a, b both are multiple of 2.
Also as RHS is of the form 3k + 1, one of a, b is multiple of 3. (Think why??)
As 31^{2 } < 1000 < 32^{2}, none of a, b is more than 31. And also we got to know that one of a, b is multiple of 2 as well as 3 i.e. 6 and other is multiple of 2 only.
Now you can easily check that multiple of 6 can be 6, 12, 18, 24, or 30 only.
18^{2 }+ 26^{2 }= 324 + 676 = 1000, and
30^{2 }+ 10^{2 }= 900 + 100 = 1000
So four cases for (a, b) are possible.
Nimai and Nitai are two brothers who have some mangoes with them to sell. They fix the price of each mango to be equal to the number of total mangoes with both of them together initially. Together they sell all the mangoes and after that they start distributing the money collected in this particular fashion. First Nimai takes a 10 rupee note, then Nitai takes a 10 rupee note and so on. In end it's turn of Nitai who don't get any more 10 rupees. Can you tell me how much rupees he get in his last turn?
As Nimai started the distribution part and took a 10 rupee note first and in the end also, he is able to take a 10 rupee note. That means Total amount, which needs to be a perfect square for n mangoes @ n rupees per mango, is odd multiple of 10 plus some more which is less than 10. That means ten's place digit of the perfect square is ODD. So certainly unit digit of perfect square is 6.
Factorial
How to find power of a prime number contained in a factorial
No theory. Direct result.
Find the highest power of 2 contained in 200!
Just divide 200 by 2 and add the quotient thus obtained divided by 2 and so on. See how.
200! Contains 100 + 50 + 25 + 12 + 6 + 3 + 1 = 197 powers of 2.
One more: Find the number of zeroes at the end of the number 200!
This time we need to find the powers of 5, so we need to divide 200 and subsequent quotients by 5 and add them to get the answer as 40 + 8 + 1 = 49.
So 200! ends in exactly 49 zeroes at the end.
How to find power of a composite number contained in a factorial
No difference. You just need to find the powers contained for all the prime factors and group the accordingly.
Find the highest power of 200 that divides 200! completely.
200 = 2^{3 }× 5^{2 }
We have already calculated the powers of 2 and 5 contained in 200!
So number of 2^{3 }available = [197/3] = 65 and number of 5^{2 }available = [49/2] = 24.
That means we can form exactly 24 pairs of 2^{3 }and 5^{2 }in 200! Or 24 is the highest power of 200 which divides 200! completely.
How to find remainders of factorial numbers
Wilson Theorem states: (p  1)! + 1 = 0 mod p where p is a prime number.
For example 30! + 1 = 0 mod 31 or in other words we can say 30! + 1 is divisible by 31.
We can further work on it to get that
(p  1)! = 1 mod p
(p  1)! = (p  1) mod p
(p  2)! = 1 mod p
2(p  3)! = 1 mod p
2(p  3)! = 1 mod p
2(p  3)! + 1 = 0 mod p and many more. :)