Number Systems
1. Real Numbers
a. Rational - That can be expressed in the form p/q where q <> 0 and p, q are integers
b. Irrational Numbers - That cannot be expressed in the form p/q where q <> 0 and p, q are integers
c. Natural - All consecutive numbers from 1 onwards...
d. Whole - The set if all natural numbers including 0
e. Even - Divisible by 2
f. Odd - Not Divisible by 2
g. Integers - Positive and and negative
h. Prime numbers - The numbers that have no factor other than itself and unity- Ex 2, 3, 5, 7
2. Composite Numbers - The numbers that have factors other than itself and unity- Ex 9, 6
Complex Numbers - Numbers that are expressed in the form a+bi, where i = (-1)^(1/2)
3. Properties:
1. 1 is neither a prime number nor a composite
2. 0 is an even number
3. 2 is the only even prime
4. Operations on even \ odd numbers
2. Even (+ -) Even = Even
3. Odd (+ -) Odd = Even
4. Even * Even = Even
5. Odd * Odd = Odd
6. Odd + - Even = Odd
7. Odd * Even = Even
5. For any two numbers N1 and N2, their product is equal to the product of their LCM and HCF ->N1xN2 = LCM(N1,N2) x HCF(N1,N2)
6. If N1 and N2 are co prime, then HCF(N1,N2) = 1, so N1xN2 = LCM(N1,N2)
7. Sum of the first n natural numbers - [n(n+1)]/2
8. Sum of the squares of first n natural numbers - [n(n+1)(2n+1)]/6
9. Sum of the cubes of first n natural numbers - [n(n+1)/2]^2
10.Sum of even numbers - n(n+1)
11.Sum of odd numbers = n^2
12.If a^p x b^q x c^r are factors of a number N, then the total of factors of N are (p+1)(q+1)(r+1), where a , b and c are prime factors
EX- The unit's digit in the expansion of 2 raised to power 51 is :
2 has a cyclicity of 4 and 51(mod 4) = 3 , so the unit's digit will be same as in 2^3 = 8
EX- How many 0s are there in the expansion 100!
To solve this you need to find the highest power of 10 that divides 100!
Now 10 = 5X2
100/2 = 50
100/2^2 = 25
100/2^3 = 12
100/2^4 = 6
100/2^5 = 3
So the max power of 2 in 100! Is 96
Similarly – We can find the highest power of 5 in 100!
100/5 = 20
100/5^2 = 4
100/5^3 = NA
i.e. = 20+4 = 24
So we have 100!/10 = 100!/(2^96X5^24) = 100!/(10^24 X 2^72)
So the number of 0s in 100! Is 24
EX - The difference between the biggest and the smallest number formed by using 0, 1, 2, 3, 4 exactly once is :
(1) 28000 (2) 32591 (3) 27143 (4) 41976
Soln - 43210 - 01234 = 41976
13.You can perform all the arithmetic operations with remainders that you can with the numbers. For example if the two numbers N1 and N2 on division by “a“, leave remainders R1 and R2, then the remainder when (N1+N2)%a = R1+R2 or (R1+R2)(% a) if r1+r2 > a. Similarly (N1 – N2)%a = (R1 – R2)%a and also (N1*N2)%a = (R1*R2)%a. (read % as remainder from divisor).
14.Fermat's Little Theorem:
a. If p is a prime number and a any integer, then (a^p-a)% p = 0 i.e. a^p- a is completely divisible by 'p'.
b. If a and p are co prime then a^(p-1)%p = 1
15.Euler's Generalization
If 'a' is any number co-prime to 'n' then - a^e(n) % n = 1, where e(n) = euler's quotient
16.For any positive number n, 2<=(n+1/n)^n <=3
17.(n!)^2 > n^n
18.If n is an odd number, then n(n^2-1) is divisible by 24.
19.If n is an odd number greater than 3, then (n^2-1) is divisible by 24.
20.If the sum of 2 number x and y is constant x+y = k, then their product is MAX when x = y = k/2 and this product is = k^2/4
21.On the same lines if the product of two numbers is constant i.e. xy = k, then their sum is MIN when x = y = root(k) and the value is = 2root(k)
Note: This concept can be extended to more than 2 numbers.
Modular Mathematics--------------------------------
This one is for ignorant buddies who find remainder problems and theorems related to it hard to understand.
I believe that algebraic number theory is one of the most intriguing topics of mathematics. Numbers have enchanted mathematicians for centuries and still there is much to be explored. Here is a set of theorems that can be used to solve almost all the problems related with finding remainders. Before starting lets prove that number of primes are infinite. Suppose I have found first few primes as p(1) = 2; p(2) = 3 and so on up to p(n). Product p(1)*p(2)*…*p(n) is divisible by all the primes we have found so far.
That means p(1)*p(2)*…*p(n) + 1 is not divisible by any of the known primes. That means either this number is a prime or it is a composite number having prime factors different from that are known (Caveat: -We have no right to say that this number is prime unless we prove it. A number of coaching institutes say this number is a prime but this is not necessarily true). Hence if we have first n primes we can find at least one more prime and that proves infinitude of primes. Wasn’t it a simple way of proving something of quite an elusive nature? Well that’s the beauty of mathematics.
Why does ISO insist upon standardizing the methods and approaches of running a business? Because when you follow same process again and again, you become proficient at using the process that brings the efficiency and quality in products and services. So if we follow a prescribed set of rules, we will become proficient at solving even difficult remainder problems.
It is necessary to know how a remainder is formally defined. Suppose we have two positive numbers a, b where a>b. a = b*q + R is true for infinite sets of integers (q, R).
Lets say that R is the residue (because we have not defined remainder as yet). We define remainder as value of R that is numerically less than the divisor b and either negative or positive. Or ½r½ < b. A sample statement “ When a number is divided by 29 leaves a remainder 5.” should be interpreted as N = 29x + 5. I won’t explain the trivial cases that are given in almost all the materials, as when a number is divided by two different divisors, remainders are same then remainder when LCM divides the number gives the same remainder etc. Here are the theorems you must know.
First thing we should be clear about is that whatever operation (addition, subtraction or multiplication) happens on the numbers, same operation happens on the remainders of the numbers from a given divisor. Suppose 2 numbers x and y when divided by divisor ‘a’ leave remainders r and R i.e. x = am + r and y = an + R.
(x + y) = a(m + n) + (r + R) hence remainder when (x + y) is divided by a is either (r + R) or remainder when (r + R) is divided by a ( in case r + R is greater than a).
Similarly (x – y)%a = (r – R)%a and also (x*y)%a = (r*R)%a. (read % as remainder from divisor).
I presume everyone knows the application of binomial theorem in finding remainders so won’t explain here.
RULE 1. Chinese remainder theorem: - Do not panic by looking at the name. It is just another buddy that helps in solving remainder problems. I will explain it using a sample problem.
Q. A number when divided by 7 leaves remainder 5 and when divided by 11 leaves remainder 3, find a general solution. There may be easier methods available for solving these questions but motive here is to understand the approach that more or less remains the same even when we move towards questions of higher level. From given statement we can say that number N = 7x + 5 = 11y + 3.
Or x = (11y – 2)/7
Lets say that y when divided by 7 leaves a remainder r i.e. y = 7a + r. 11 leaves either 4 or –3 as remainder from 7 (at times negative remainder makes the calculations easier). Since x is an integer, it gives remainder 0 when divided by 7 therefore 4r – 2 is divisible by 7 since r is the remainder from 7, you’ll have to try values of r up to 6. At r = 4, 4r – 2 becomes divisible by 7. So we can say here that y = 7a + 4. Putting the value of y in N=11y + 3 = 11(7a + 4) + 3 = 77a + 47. Putting a = 0, 47 is the first number of this type and 77a + 47 is the general series of such numbers.
I hope you can understand the process. Now lets say that in the same question another condition is given that when divided by 13, number leaves a remainder 6.
That means N = 13b + 6 along with the previous conditions. We have already solve it for two conditions and found the combined form as 77a + 47. We just need to solve this with the new form 13b + 6.
77a + 47 = 13b + 6
Or b = (77a + 41)/13.
Again using the same process.
77%13 = -1 (Usefulness of negative remainders)
41%13 = 2 (Positives are equally useful)
That clearly means that a%13 = 2
(-1)*(2) + (2) = 0{I have done the same operation on remainders as done on numbs}
Therefore a = 13c + 2; and putting this value in 77a + 47 = 77(13c + 2) + 47
= 1001c + 154 + 47 = 1001c + 201.
Whatever other remainder conditions are given, we can solve in same fashion.
Now you know CHINESE REMAINDER THEOREM.
You need practice to master it. Do you require questions on this? I don’t think so. You can make as many as you wish to.
RULE 2: FERMAT’S LITTLE THEOREM
Using the properties of infinite arithmetic progressions, Fermat proved the theorem that for a prime number ‘p’ that is co prime with another number ‘a’; when a to the power
(p-1) is divided by p, remainder is 1. Or a^(p-1) % = 1. Don’t forget that this theorem is defined only for prime divisors. E.g. 2^4%5 =1; 3^10%11 = 1. Or in more general form
a^{n(p-1)}%p = 1. So if the question is 2^1000%11, remainder will be 1 because power of 2 is a multiple of (11-1).
What if divisor is not a prime? Then we have eular’s generalization of Fermat’s rule.
That generalization says that a^e(n)%n = 1. Where e(n) is eular’s number for divisor n. Also a is co prime with the divisor n. Eular’s number e(n) for divisor n is defined as number of natural numbers less than ‘n’ and co prime with it. How to find e(n)? Suppose I want to find eular’s number of 1001. Prime factors of 1001 are 7,11,13.
e(1001) = 1001(1-1/7)(1-1/11)(1-1/13). In general for a number n having prime factors p1, p2, p3…. e(n) = n (1-1/p1)(1-1/p2)(1-1/p3)…
This knowledge about eular’s theorem is sufficient. Now that we know fermat’s rule and eular’s rule, lets try a sample question.
What are last two digits of 3^96? Last two digits of this number can be obtained by finding remainder when this number is divided by 100. 100 = (2^2)*(5^2). Understand the things clearly here. For 2^2 i.e. 4, eular’s number is 4(1-1/2) = 2 and for 5^2 (25), eular’s number is 25(1-1/5) = 20. Using eular’s theorem, 3^2 %2^2 = 1 and
3^20 %5^2 = 1. if we take LCM of the powers of 3 in two cases(LCM is 20) we find that 3^20 %100 = 1 or last two digits of 3^20 are 01. It can be proved for any other number co prime with hundred. That explains why cyclicity of last two places is generally 20 for all numbers co prime with 100. Last 2 places of 3^96 will therefore be same as last two places of 3^16. (Because 3^96 = 3^80 * 3^16 and 3^80 ends in 01) . How to find last two digits of 3^16? 3^20 = 3^16 * 3^4 lets say last two digits of 3^16 are xy.
Therefore xy * 81 = 01 (considering only last two digits) that’s true for xy = 21.
Another question. What is the remainder when 3^1001 is divided by 1001?
1001 = 7*11*13. 3^6 %7 = 1; 3^10 %11 = 1 and 3^12 %13 = 1. That implies
3^{LCM (6,10,12)} %1001 = 1 or 3^60 %1001 = 1. Using this we can reduce the previous problem into a simpler one. 3^1000 = 3^960 * 3^41, from 3^960, remainder is 1 therefore reminder when 3^1001 is divided by 1001 is same as remainder when 3^41 is divided by 1001. 3^41 %7 = 3^5 %7 = 5 {I presume it should be clear by now}
3^41 %11 = 3
3^40 %13 = 3^5 %13 = 9. It is a number which when divided by 7,11 and 13 gives remainders 5,3 and 11 respectively. N = 7x + 5 = 11y + 3 = 13z + 9. Further we know how to solve it (HINDI CHEENI BHAI BHAI).
I am attaching a list of questions few of which are collected from various threads and a few are made by me. Lets solve all those using the standard methods we have learnt. Solving the problems will make concepts clearer. Remember; try to standardize your approach.
1.What is the remainder when 17^19 + 13^19 is divided by 25?
2.Find the remainder when 104^303 is divided by 101.
3.Find the last two digits in the expansion of 2^ 999.
4.Find the remainder when 2 ^ 1990 is divided by 1990.
5.Remainder when (128 )^500 is divided by 153.
6.Find last 3 digits of 3^1994.
7.What is the remainder when 2^2001 is divided by 2001?
8.What is the remainder when 2^2002 is divided by 2002?
9.What is the remainder when 13^2404 is divided by 2310?
10.What is the remainder when 2^10013 is divided by 3125?
11. Find last 4 digits of (2319)^{10^12 + 2}.
And a lengthy one here.
12. What is the remainder when 17^28820 is divided by 30030?
Solve these first and I’ll post more related with the topic.
Concepts - Cubes
--------------------------
We usually find questions invovling cubes in CAT. like, a big cube painted red is cut into 64 smaller cubes and find the no of smaller cubes with no sides painted etc. etc.
lets assume the cube is devided into n^3 small cubes.
then,
no. of small cubes with ONLY 3 sides painted : 8( all the corner cubes )
no. of small cubes with ONLY 2 sides painted :
A cube is painted on 2 sides means, it is on the edge of the bigger cube ,and we have 12 edges, each having n cubes. but since the corner cubes are painted on 3 sides, we need to neglect them. so in effect, for each side we will have (n-2) small cubes with only 2 sides painted.
thus, then number is, 12 * (n-2)
no of small cubes with ONLY 1 side painted :
for each face of the cube ( 6 faces ) we have (n-2)^2 small cubes with only one side painted. and we have 6 faces in total.
so th number is, 6*(n-2)^2
no of small cubes with NO sides painted :
if we remove the top layer of small cubes from the big cube we will end up a chunk of small cubes with no sides painted.
this number will be equal to, (n-2)^3.