Number Theory Fundas  Sibanand Pattnaik

Prime numbers:
Numbers divisible only by themselves and 1 are called prime numbers.
Smallest prime number = 2 which is also the only even prime number because every other even number will be a multiple of 2. Rest all prime numbers are odd.
There are 25 prime numbers less than 100. Since all prime numbers other than 2, are odd, therefore the sum and difference any two prime numbers (other than 2) must be even.
All prime numbers greater than 3 can be written as 6k+1 or 6k1
Square of all prime numbers greater than 3 can be written as 24k+1How many 2 digit numbers are there such that the sum of their digits is a prime number?
a) 31
b) 33
c) 25
d) 27Sum of the digits is prime means the sum of the digits can be
2: 11,20
3:12,21,30
5:41,14,23,32,50
7:61,16,25,52,34,43,70
11:92,29,83,38,74,47,65,56
13:94,49,85,58,76,67
17:98,89
There are 33 such numbers. Hence (b)Factorization:
If a natural number is expressed as the product of prime number (factors) then the factorisation of the number is called its prime factorisation.
72=2×2×2×3×3
600=2×2×2×3×5×5
9900=2×2×3×3×5×5×11Number of factors
Let there be a composite number N and its prime factors be a,b,c,d,… etc. and p,q,r,s,… etc respectively i.e., if N can be expressed as
N=a^p.b^q.c^r.d^s…
Then the number of total divisors or factors of N is.
(p+1).(q+1)(r+1)(s+1)…Example: Find the number of factors of 24
24 is divisible by 1,2,3,4,6,8,12 and 24.
We see that there are total 8 factors namely
Lets use the method discussed above
24 = 8 x 3 = 23 x 31
So the number of factors = (3+1)(1+1) = 8 factorsEXAMPLE: Find the total number of factors of 360.
Solution: 360=2^3×3^2×5
Since the powers are 3 , 2 and 1
∴ Number of factors = (3+1)×(2+1)×(1+1)=24EXAMPLE: Find the total number of factors of 540.
Solution: 540=2×2×3×3×5
Or 540=2^2×3^3×5^1
Therefore total number of factors of 540 is (2+1)(3+1)(1+1)=24EXAMPLE: The total number of divisors of 10500 except 1 and itself is:
Solutions:10500=2×2×3×5×5×5×7
Or 10500=2^2×3^1×5^3×7^1
∴ Total number of factors of 10500 is (2+1)(1+1)(3+1)(1+1)=48
But we have to exclude 1 and 10500
So there are only 482=46 factors of 10500 except 1 and 10500.EXAMPLE: The total number of factors of 36 is:
Solution: 36=2^2×3^2
∴ Number of factors = (2+1)(2+1)=3×3=9N has 12 factors. Which of the following cannot be the number of factors N^2?
a) 33
b) 35
c) 45
d) 54N can be of any of the following form:
P^5x Q^1 therefore N^2 = P^10x Q^2; therefore N^2 has 33 factors
P^3x Q^2 therefore N^2 = P^6x Q^4; therefore N^2 has 35 factors
P^2x Q^1 x R^1 therefore N^2 = P^4x Q^2 x R^2; therefore N^2 has 45 factors
Therefore 54 is the answerNUMBER OF WAYS OF EXPRESSING A COMPOSITE NUMBER AS A PRODUCT OF TWO FACTORS
Let us consider an example of small composite number say, 90
Then 90 =1×90
Or =2×45
Or =3×30
Or =5×18
Or =6×15
Or =9×10
So it is clear that the number of ways of expressing a composite no. as a product of two factors =1/2× the no. of total factorsExample: Find the number of ways of expressing 180 as a product of two factors.
Solution: 180 =2^2×3^2×5^1
Number of factors = (2+1)(2+1)(1+1)=18
Hence, there are total 18/2=9 ways in which 180 can be expressed as a product of two factors.Perfect Squares: As you know when you express any perfect square number 'N' as a product of two factors as √N x √N, and you also know that since in this case √N appears two times but it is considered only once while calculating the no. of factors so we get an odd number as number of factors so we can not divide the odd number exactly by 2 as in the above formula. So if we have to consider these two same factors then we find the number of ways of expressing N as a product of two factors=((Number of factors+1))/2 .
Perfect Squares as product if 2 distonct factors: Again if it is asked that find the no. Of ways of expressing N as a product of two distinct factors then we do not consider 1 way (i.e.,N=√N×√N) then no. Of ways = (Number of factors1)/2
Example: Find the number of ways of expressing 36 as a product of two factors.
Solution: 36 =2^2×3^2
Number of factors = (2+1)(2+1)=9
Hence the no. Of ways of expressing 36 as product of two factors = (9+1)/2=5.
As 36=1×36,2×18,3×12,4×9 and 6×6Example: In how many of ways can 576 be expressed as the product of two distinct factors?
Solution: 576 =2^6×3^2
∴ Total number of factors = (6+1)(2+1)=21
So the number of ways of expressing 576 as a product of two distinct factors = (211)/2=10.
Note since the word ‘distinct’ has been used therefore we do not include 576=26×26.Factorial
Factorial of N: 1 x 2 x 3 x 4 … x N
0!= 1
Last digit of any factorial after 5! Will always be 0, as there always be a 5 and a 2
For example 6! Will include at least one 5 and one 2. Therefore last digit will be 0What is the last digit of 1! + 2! + 3! ... + 100!
We just need to calculate only the last digit for 1! + 2! +3! + 4! : 3
Why did i not proceed after 4! ??
Because those won't contribute to "last digit" as they their last digit shall be zeroHighest power of a prime number in a factorial is found by successive division
Example: Find the highest power of 3 in 20!
20/3: 6
6/3: 2
2/3 : 0
So highest power of 3 in 20! = 6+2 = 8Highest power of 5 in N! is more than 27 and less than 31. For how many values of N is this possible?
Highest power in 115 to 119 is 27, question says more than 27..so it has to be at least 120..highest power of 5 in 125 is 31..so it has to be less than 125....So 5 values are possible
Highest power of a composite number: take the larger prime number amongst the factors of the composite number
For example if you have to find the highest power of 10, then since 10 = 5 x 2, therefore take 5 and not 2. Highest power of 10 in any factorial will be same as the highest power of 5.
If the questions says that find the number of 0s at the end of N!, then the question is about finding the highest power of 10 in N! which we now know is same as finding the highest power of 5 in N!
For example highest power of 6 in 200!
6 = 2 x3
So highest power of 3 in 200! : 66 + 22 + 7 + 2 = 97Find the highest power of 18 in 250!
18 = 2 x 3^2
Highest power of 3 in 250! = 83 + 27 +9 + 3 + 1 = 123
So highest power of 3^2 = 123/2 = 61Find the highest power of 12 in 150! ?
12 = 2^2 x 3
Highest power of 3 in 150! = 50+16+5+1 = 72
Highest power of 2 in 150! = 75+37+ 18+9+4+2+1 = 146
So highest power of 2^2 in 150! = 73
Therefore highest power of 12 in 150! = 72You must have noticed that though in the previous question, answer eventually was as per the power of 3, the powers of 2 and 3 were very close to each other.in such cases we do need to calculate the power of each prime number..we cannot assume that the bigger prime number will have a smaller power.
Find the highest power of 135 in 200! ?
135 = 3^3 x 5
Highest power of 5 in 200! = 40+8+1 = 49
Highest power of 3 in 200 = 66+22+7+2 = 97
Therefore highest power of 3^3 in 200! = 32
So highest power of 135 in 200! Is 32Finding the Last Digit
Last digit of any number raised to a power is decided by the last digit of the base
For example last digit of 5763^67 is same as the last digit of 3^67
So we just need to know the concept of last digit for single digit numberNow for single digit numbers, the whole thing can be divided in 3 categories
0, 1, 5, 6: last digit is always same, raised to any power.
Example 5^113 will end in 5’
6^239 will end in 6
2346 ^ 5732 will end in 64, 9: Here there is a cycle of 2;
For 4 it is 4 and 6 and for 9 it is 9 and 1
So odd powers of 4 will end in 4 and even power in 6
Odd powers of 9 will end in 9 and even power in 1
Example:
564 ^ 231 will end in 4
75689 ^ 568 will end in 12, 3, 7 and 8
Here there is a cycle of 4
Divide the power by 4 and take the remainder as the power
For example: last digit of 2347 ^2347 is same as 7^2347
Divide the power by and take the remainder; to find the remainder on dividing by 4, we just need to take the last 2 digits
So last digit of 2347^2347 is same as 7^47
Divide 47 with 4; remainder is 3
So last digits is same as that of 7^3 = 3
Example: 5748 ^5748
Same as 8^48
On dividing 48 with 4 the remainder is 0
When the remainder is 0, we take it as 4
So 8^4; last digit is 6
Find the last digit of : (101^101 + 102^102……109^109)
101^101: 1
102^102: 2^2 : 4
103^103: 3*3: 7
104^104: 6
105^105: 5
106^106:6
107:107:7^3: 3
108^108: 8^4: 6
109^109: 9
Last digit: 7
So , 1 4 7 6 5 6 3 6 9 adds up to 47 so last digit is 7Find the last digit of 3^(2^2^2….)
We know that is the base is 3, we need to divide the power by 4 and take the remainder
Now when you divide a number with 4, possible remainders are 1, 2, 3 and 0
Remainder of 3 can also be taken as remainder of 1; for example 19 divide by 4 is 4x4+3 (remainder 3) but it can also be written as 4x51 (remainder 1)
Remainder of 2 will only be there when the given power is even. Any even power raised to any number when divided by 4 will give the remainder as 0
Remainder of 0 will be taken as 4; for finding the last digit
So when we divide (2^2^2..) with 4, the remainder is 0
Any even digit ^ any number will always be divisible by 4
So the last digit of 3^(2^2^2….) is same as 3^4 = 1Find the last digit of (1002 ^ 1003 ^ 1004…..2000)
1002 ^ 1003 ^ 1004…..2000)
(2 ^ 1003 ^ 1004…..2000)
2 ^ ( (1) ^1004…..2000)
1^even number = 1
2^ (1^…..) = 2Find the last digit of: 2468^ (4682^6824^8246)
8^(2^even number..)
8^4 = 6
So 6Finding the second last digit
DISCLAIMER: REMAINDER AND 2ND LAST DIGIT HARDLY COME IN THE CAT BUT FB GROUPS ABOUND WITH THEM..SO DONT WASTE TIME TRYING TO SOLVE VERY DIFFICULT QUESTIONS.
Cyclicity
There lies the cyclicity of tens' place digit of all the digits. This is given below:
Digits Cyclicity
2, 3, 8 20
4, 9 10
5 1
6 5
7 4Example 2367^2367
Take 7^2366; this will be same as 7^2 (as 7 has a cyclicity of 4 so we divide the power with 4)
7^2 = 49
Now, Multiply the 2nd last digit of the given number with the last digit of power and place the last digit of the original number in the last place
Last digit of 6 x7 = 2
So 27
Now multiply 27 with 49; last 2 digits are 23Example 3438 ^ 126
8 has a cyclicity of 20, so 8^6
8^3: 12
So 8^6: 44Last digit of 3 x 6 = 8; so 88
44 x 88 = 16SHORT CUT FOR LAST 2 DIGITS OF NUMBERS ENDING WITH 1:
EXAMPLE: 2341 ^ 678
Multiply the 2nd last digit of base with last digit of the power: 4 x 8 = 32
Last digit was 2
So last digit of overall expression is 21HCF/LCM
HCF: Factorize each number, Take the lowest power of each prime number and multiply
For example in 720, 120 and 540, prime factors with their lower power will be: 2^2 , 3^1 , 5^1; HCF = 60
LCM: Factorize each number, Take the highest power of each prime number and multiply
For example in 720, 120 and 540, prime factors with their highest power will be: 2^4 , 3^3 , 5^1; LCM = 2160Important rules for HCF:
 HCF of 1 and any number is 1
 HCF of 2 equal numbers is that number itself. HCF of 5,5 is 5
 If in a set of numbers, one number is the factor of all other numbers, or all numbers are multiples of one number, then HCF is that number. For example HCF of (3, 6, 12, 15, 24, 30, 120) is 3, as all the other numbers are multiples of 3
 If in a set of numbers no 2 numbers have a common factor, i.e. they are all coprime to each other then the HCF is 1. For example HCF of (34, 39, 77, 23, 95) is 1, as no 2 numbers in the entire set has a common factor.
Important rules for LCM:
 LCM of 1 and any number is that number. For example LCM of 1,5 is 5
 LCM of 2 equal numbers is that number itself. LCM of 5,5 is 5
 If in a set of numbers, one number is the multiple of all other numbers, or all numbers are factors of one of the numbers, then LCM is that number. For example LCM of (6, 8, 12, 15, 24, 30, 120) is 120, as all the other numbers are factors of 120
 If in a set of numbers no 2 numbers have a common factor, i.e. they are all coprime to each other then the LCM is the product of all numbers. For example LCM of (3, 11, 7, 2, 5) is 2310, as no 2 numbers in the entire set has a common factor.
There are 1224 boys and 468 girls in a school which are to be divided into equal sections of either boys or girls alone. Find the total number of sections thus formed.
Answer Should be cannot be determined because you can have 1 student or 2 students in a class.
If they mention that minimum number of sections are to be formed with each section having the same number of boys or girls, then we have to find the HCF of the 2 numbers
Say the number of boys in each class = Number of girls in each class = N
Therefore N must be a factor of both 1224 and 468
Also number of sections = 468/N + 1224/N
To minimise the number of sections, we must maximize N
HCF (1224,468)= 36.
Total number of students (1224+468)/36= 47.Q) How many pairs of numbers can you have whose LCM is 144?
a) 22
b) 21
c) 18
d) 23It's unordered pairs as variables are IMPLICIT .. explanation in case of ORDERED video , i ve posted .. Unordered video i shall make n post tonight .. FORMULA everyone knows , concept is important .. Concept part shall be explained in the video.
12^2 = 2^4 * 3^2
Ordered = (2 * 4 + 1 ) (2 * 2 + 1) = 45
unordered = (45  1 )/2 +1 = 23Find the greatest possible number with which when we divide 37 and 58, it leaves the respective remainder of 2 and 3.
Since when we divide 37 and 58 by the same number then we get remainders 2 and 3 respectively. So (372) and (583) must be divisible hence leaving the remainders zero. It means 35 and 55 both are divisible by that number so the HCF of 35 and 55 is 5. Hence the greatest possible number is 5.
Find the largest possible number with which when 60 and 98 are divided it leaves the remainders 3 in each case.
Since 60 and 98 both leave the remainders 3 when divided by such a number. Thus 57=(603) and 95=(983) will be divisible by the same number without leaving may remainder. So the HCF of 57 and 95 is 19. Hence 19 is the highest possible number.Find the largest possible number with which when 38, 66 and 80 are divided the remainders remains the same.
In this (since we do not know the value of remainder) we take the HCF of the difference of the given numbers. So the HCF of (6638),(8066),(8038)
= HCF of 28,14,42 = 14
Hence 14 is the largest possible number which leaves same remainder (=10) when it divides either 38, 66 or 80.What is the least possible number which when divided by 24, 32 or 42 in each it leaves the remainder 5?
Since we know that the LCM of 24, 32 and 42 is divisible by the given numbers. So the required number is
=LCM of 24,32,42)+(5)=672+5=677
Hence such a least possible number is 677.
In the above question how may numbers are possible between 666 and 8888 ?
Since the form of such a number is 672m +5, where m=1,2,3,…So, the first no.=672×1+5=677 and the highest possible number in the given range
=672×13+5
=8736+5=8741
Thus the total numbers between 666 and 8888 are 13.What is the least possible number which when divided by 21,25, 27 and 35 it leaves the remainder 2 in each ?
The least possible no.
= (LCM of 21, 25, 27 and 35)m + 2
= 4725m+2
= 4727 (for the least possible value we take m = 1)When the remainders are different for different divisors but the respective difference between the divisors and the remainders remain constant.
What is the least possible number which when divided by 18, 35 or 42 it leaves the 2,19, 26 as the remainders respectively ?
Since the difference between the divisors and the respective remainders is same.
Hence the least possible number
= (LCM of 18,35 and 42)16
= 63016 [∴(182)=(3519)=(4226)=16]
= 614
What is the least possible number which when divided by 2, 3, 4, 5, 6 it leaves the remainders 1, 2, 3, 4, 5 respectively ?
Since the difference is same as
(21)=(32)=(43)=(54)(65)=1
Hence the required number = (LCM of 2,3,4,5,6)1
=601=59
In the above problem what is the least possible 3 digit number which is divisible by 11 ?
Since the form of the number is 60m1, where m=1,2,3,…but the number (60m1) should also be divisible by 11 hence at m=9 the number becomes 539 which is also divisible by 11. Thus the required number = 539.Difference between LCM & HCF of 2 Numbers is 27. How many pairs of numbers satisfy the condition?
a) 3
b) 4
c) 5
d) 6Let the HCF and LCM be H and L and the numbers be Ha and Hb. Therefore
Hab  H= 27 OR
H(ab1)=27Possibilities
H ab1 ab a,b Numbers
1 27 28 28,1 or 7,4 28,1 or 7,4
3 9 10 10,1 or 5,2 30,3 or 15,6
9 3 4 4,1 36,9
27 1 2 2,1 54,27
Hence (d)Practice Questions with Solutions
If k is a factor of (n+5) and (6n+54) where n is a natural number, how many possible values of k are there?
a) 6
b) 7
c) 8
d) 9As given k must be a factor of 6n+30 and is also a factor of 6n+54.
So it must be a factor of (6n+54) – (6n+30) = 24 = 2^3 x 3
Therefore k can take 8 values
Hence (c)The sum of all the factors of 480 including 1 and the number itself is 1512. What is the sum of the reciprocals of all the factors?
a) 3.15
b) 2.85
c) 2.55
d) 3.45Sum of reciprocals = (sum of factors)/480
1512/480= 3.15Find the last two digits of 89^102
a) 23
b) 21
c) 01
d) 69(89^2)^51 89^2 same as 11^2 > 21^51 = 21
Q) The highest power of 5 in N! is 34. Find the highest power of 7 in N!.
a) 23
b) 26
c) 22
d) Cannot be determinedHighest power of 5 in 125!= 31.
Highest power of 5 in 140!=34
But highest power of 5 in 141!, 142!, 143! And 144! Is also 34.
So N can be 140 to 144, any of these values
However the highest power of 7 in any of these values is same i.e. 22A! + B! = N^2, Where A, B and N are whole numbers. How many possible combinations are there?
a) 1
b) 2
c) 3
d) 40! + 4! = 5^2
1! + 4! = 5^2
0! + 5! = 11^2
1! + 5! = 11^2
Hence 4 combinations are possiblex, y and z are natural numbers such that x > y > z > 1 and PRODUCT= 3003. Let A and B be the maximum and minimum values of x + y + z. Find AB.
a) 152
b) 45
c) 107
d) None of the above3003= 3 x 7 x 11 x 13
A= 143+7+3= 153
B= 21 + 11 + 13= 45
AB= 108
Hence (d)How many natural numbers less than 4444 are "not co primes" to 247?
a) 585
b) 341
c) 244
d) 557247= 13 x 19
So all multiples of 13 and 19 has to be excluded till 4444
Multiples of 13 : 341
Multiples of 19: 233
Multiple of both 13 and 19 i.e. of 247: 17
Therefore number of numbers less than 4444 which are coprime to 247: 341+23317= 557N , a natural number has 2 prime factors. N^3 can have which of the following number of factors?
a) 18
b) 90
c) 70
d) 84n^3 means exponent should be a multiple of 3
70= 10 * 7 i.e (9+1) * (6+1) both powers have to be multiple of 3Let D be the number of divisors of a natural number N. Let D1 be the number of divisors of D, D2 the number of divisors of D1 and so on. What will be the final value of Dn?
a) 1
b) 2
c) 3
d) None of the aboveYou will finally end up with a prime number which will have 2 divisors. 2 has 2 divisors. Hence (b)
In how many ways can 3660 be written as the sum of 2 or more consecutive positive integers?
a) 2
b) 3
c) 4
d) More than 4Direct formula for natural numbers = number of odd factors  1
So 3660 = 2^2 * 3 * 5 * 61
so odd factors = 8
Answer = 8  1 = 7
as in case of "integers" its 2 * (number of odd factors)  1
had it been asked "integers then ur answer would have been 16  1 = 15Else you can think this way :
3660 = 61 x 3 x4 x5
3660= a + (a+1) + (a+2)...+ (a+(n1)
Then 3660 = n x Average of the above series
If the number of terms in the series is odd, then the middle term of the series will be the average
So say the number of terms is 61, then the middle term will be 3x4x5= 60. So the series will be: (30+31+32...60+61+62...90)
If the number of terms is 3, the average will be 61x4x5= 1220. So the series is 1219+1220+1221.
Therefore if the number of terms is odd, its easy to construct a series like this
3660 has 7 odd factors other than 1N has 6 factors and lies between 250 and 350. How many values of N are possible?
a) 12
b) 13
c) 14
d) None of the aboveIf a and b are prime numbers then N= a^5 or N= a^2 x b
N= a^5 :No values
N= a^2 x b
If a= 2, then b can take prime values of 67, 71, 73, 79, 83: 5 values
If a= 3, then b can take prime values of 29, 31, 37: 3 values
If a= 5, then b can take prime values of 11, 13: 2 values
Total values: 10N^2 has 15 factors. M^2 has 9 factors. Which of the following cannot be the number of factors that MxN can have, if M and N are co prime to each other?
a) 24
b) 32
c) 20
d) 40N= a^7 OR N= a^2xb^1
M= p^4 OR M= p^1xq^1
Where a,b, p and q are prime numbers
Therefore M x N=
i) a^7 x p^4 : 40 factors
ii) a^2 x b x p^4 : 30 factors
iii) a^7 x p x q : 32 factors
iv) a^2 x b x p x q= 24 factorsSum of HCF and LCM of 2 numbers is 30. How many such pairs of numbers exist?
a) 6
b) 4
c) 7
d) 8h(1+xy) = 30
h=1 xy=29 so 2^0=1
h=2 xy= 14 = 2*7 so 2^1= 2
h=3 xy=9 = 3^2 so 2^0= 1
h=5 xy=5 so 2^0=1
h=6 xy=4 so 2^0=1
h=10 xy=2 so 2^0=1
h=15 xy=1 so 1
> 1 + 2 + 5 * 1= 8N is a natural number such that N/9 is a perfect square and N/4 is a perfect cube. Find how many factors does the smallest value of N have?
a) 18
b) 24
c) 14
d) 21N=2^2 * 3^6
factors= 21How many ways can 1500 be expressed as product of 3 integers ?
1500 = 2^2 *3 * 5^3
ordered solutions = 4c2 * 3c2 * 5c2 = 180
integral : here we can have any 2 out 3 elements as negative ( for example , xyz = x * y * z)
so 3c2 = 3 ways so total 180 * 3 = 540 negative solutions
so finally 180 + 540 = 720 ordered integral solutions
total perfect squares in 1500 = 4
Total cubes = 1
So (a,a,b) cases = 3 and (a,a,a) cases = 1
now for integral (a,a,b), each of it can be (a,a,b) and (a,a,b)
finally 2 * 4 1 = 7 aab types and only 1 aaa type
unordered = [720  3 * 7 1]/6 + 8 = 124
so its 124 ways