Number Theory Concepts For CAT - Hemant Malhotra

[hemant_malhotra]

Let N = 44444444......4444444 (2045 times). find remainder when N is divided by 103 ?

44444 mod 103 = 51
any number written p - 1 times div by p where p is prime
so only last 5 digits will be dere so 44444 mod 103=51

Let N = 111...111 ( 73 times ). When N is divided by 259, the remainder is R1, and when N is divided by 32, the remainder is R2. Then R1 + R2 is equal to

A. 6
B. 8
C. 253
D. None of these

Any digit repeated p - 1 times is divisible by p where p is prime
111111 ( repeated 6 times ) is divisble by 259 ( = 37 * 7 ) = > 1111... repeated 72 times is divisible by 259. As there are 73 one's in the number remainder is 1.
OR 111....... 36 times is divisible by 37 = > 1111...72 times is divisible by 37 = > only last 1 will be there giving a remainder of 1 ( we can use either of this method )

For 32 (2^5) we need find the remainder for last 5 digits. General rule for 2^n is to check the last n digits , for remainder.
check 11111 mod 259, we get 7 as the remainder

so sum 7 + 1 = 8, our answer!

What is remainder when 2014 ²⁰¹⁵ is divided by 121 ?

Use Eulers theorm, 121 = 11 * 11 = > E (121)=121 * 10/11 = 110
now 2014^2015 mod 121 = (-43)^35 mod121
= -43*(43*43)^17 mod 121
= -43*(34)^17 mod 121
= -43*34*(34*34)^8 mod 121
= -43*34*(-54*-54)^4
= -43*34*(12)^4 mod 121
= -43*34*144*23 mod 121 = -43*34*23^2 mod 121 = -43*34*45 Mod 121
= -87 mod 121 = 34.

OR

78 ^ 2015 mod 121 = ( 1+ 77 ) ^ 2015 mod 121= 77C0+2015C1*77 + rest of the terms divisble by 11 = ( 1+ 2015 * 77 ) mod 121 = 34

If m is a natural no. and N = 2^m, what is the remainder when N! is divided by 2^N ?

highest power of 2 in N! = (2^m)-1 = N -1
N! = 2^(N-1)*k
N! mod 2^N = 2^(N-1) { k mod 2} =2^(N-1)

P is a prime number greater than 30. When P is divided by 30, the remainder is x.  How many different values of x are possible ?

a. 9
b. 8
c. 10
d. 11

P = 30n + x, P has to be 6k+1 or 6k-1. Hence x also has to be of the form 6k+1 or 6k-1. Possible values of x are 1,5,7,11,13,17,19,23,25,29. out of these x cannot be 5 or 25. hence 8 values

OR just find number of coprime less than 30 = 30*1/2*2/3*4/5 = 8

If n = 1 + x, where x is the product of 4 consecutive natural numbers, then n is:
I. an odd number.
II. an even number.
III. a prime number.
IV. a perfect square.

1) II only
2) III and IV only
3) I and IV only
4) I only
5) None of these

For 4 consecutive natural number there will be atleast 2 even numbers so product will be even = > x is even and x+1 is odd
so 1 is true and 2nd is false
now to decide where n is prime or not
try for first four natural numbers which give a prduct of 24 and therefor n =25, therefore n is not prime but could be prefect square

OR

n= (a-1)*(a)*(a+1)(a+2)
n= (a^2+a-1)(a^2+a-1)
so n is perfect square

OR

or x= 2*3*4*5. then 120+1=121=11^2

so option 3.

If 2n + 1 and 3n + 1 ( n # 0 ) are perfect squares, find remainder when n is divide by 40 ?

n = 40 so 2n+1 = 81 = 9^2
3n+1 = 121 = 11^2
40 mod 40 = 0

Bonus Concept

(P-2)(P-2) mod P = (P-1)/2, Where P is prime greather than 2

example - (39)^39 mod 41, here p=41 = > (41-2)^(41-2) mod 41= (41-1)/2=20 so remainder is 20

The sum of 6 natural numbers (not necessarily distinct) is 23. Let M denote the positive difference of the maximum and minimum of the LCM of these 6 numbers. Then total number of divisors that divide M² but doesn't divide M are

(a) 22
(b) 33
(c) 18
(d) 26
(e) none

Minimum occurs when the numbers are 6, 6, 6, 2, 2, 1.
Maximum occurs when the numbers are 7, 5, 4, 3, 2, 2.
To achieve min LCM look for max number of hcf among the 6C2 pairs. so we need number in form of coprime.
Thus, M = 414. Now, 414 =2*3^2*23 , M has 2*3*2 = 12 divisors M^2 has 3*5*3 = 45 divisors.
so 45-12=33 divisors

N = 98765432109876543210.... ( 1000 digits ).What is the least positive value of n such that N + n is divisible by 11 ?

divisiblity rule of 11:
Numerals whose alternating sum of digits is divisible by 11 represent numbers divisible by 11. Here the"alternating sum" means we alternate the signs from positive to negative to positive to negative, and so on. 10 to an odd power plus 1 is divisible by 11, and 10 to an even power minus 1 is divisible by 11. This test can also be applied recursively
example- 12342
1-2+3-4+2=0 so div by 11
Another one,  2131415
2-1+3-1+4-1+5=11 so div by 11
In given case, make a group of 10 numbers and add all such group, there will be 100 groups so total sum is 9876543210*100 =987654321000 , now use alternate sum approach so remainder is -5 ; so u need to add 5

Exactly one of the five numbers listed below is a prime number. Which one is the prime number ?

(a) 999,991
(b) 999,973
(c) 999,983
(d) 1,000,001
(e) 7,999,973

a) (10^3)^2 - 3^2 = > (1003)(997)
b) (10^2)^3 - 3^3 = > divisible by (10^2 -3) = 97
d) (10^2)^3 + 1^3 = > divisible by 101
e) (2*10^2)^3 - 3^3 = > divisible by 200 -3 = 197
so c is prime

Find the smallest prime number N such that the following is true:
The largest prime factor of N−1 is A;
The largest prime factor of A−1 is B;
The largest prime factor of B−1 is 7

a) 187
b) 347
c) 119
d) 311

use options.
for N = 347
346 = 2*173
172 = 4*43
42= 2*3*7

What are the number of co-primes of y less than y, where y is the largest number with which when 486, 686 and x are divided the remainders are the same and x is the largest 3 digit number which when divided by 3 or 8 leaves a remainder of 2 in each case.

a) 10
b) 20
c) 30
d) 40
e) None of these

24k+2= 986
486, 686 y=100
coprimes= 100*(1/2)(4/5)=40

Let x and y be positive integers such that (x − y) and (x + y) are prime. Then which of the following statements is/are true?
I. x^2 + y^2 cannot be prime.
II. x^2 + y^2 cannot be even.
III. x^2 − y^2 may be even or odd.

a) I only
b) II only
c) III only
d) I and III only
e) I and II only

If x and y are integers, then (x − y) and (x + y) are either both even, or both odd.
Since (x − y) and (x + y) are prime numbers, therefore, both are odd, and so one of x and y needs to be an even number and the other has to be an odd number.
(x^2 + y^2) and (x^2 − y^2) will always be odd.
II is true and III is false.
Now consider x = 5 and y = 2
x^2 + y^2 = 25 + 4 = 29 which is a prime number.
I is false.
so option 2

x² = 444447555561 , find x

a) 666661
b) 666669
c) 233331
d) 2111119

digital sum of x^2=9
So digital sum of x shud be 3
Option b's digital sum is 3 hence b.

Let x, y, z be prime numbers in the arithmetic progression such that x > y > z. Which among the following is always true ?

(a) x – z is divisible by 12
(b) x + y is divisible by 8
(c) xz - 1 is divisible by 7
(d) atleast two of the above
(e) none of the above

x=7 , y=5 and z=3, Option E

How many ordered and unordered triplets of non-negative integers (a , b , c) are there such that root(a) + root(b) + root(c) = root(625)

RHS is an integer and LHS terms are either positive or 0, that means all of the LHS terms need to be integers.
let a = x ^2 , b = y^2 and c = z^2
x + y + z = 25
[a+b+c+....r terms = n , whole number solutions of such equation is n+r-1Cr-1]
ordered = 27C2 = 351
as for every x there will be a x^2 and that will be the value of a.
UNORDERED : Values allowed are 0-25 for x,y,z
Out of these 351 ordered solutions, solutions are either
1. x,y,z all distinct , so ordered had 3!, i.e. 6 solutions for one set of x,y,z
2. x,y,z, two similar and third distinct, so ordered will have 3!/2!, i.e 3 solutions for one set of x,y,z
3. x,y,z all same... only one solution per set
but here in our case x,y,z can not be all same.
Now, two same , & one distinct :
0,0,25
1,1,23
.........12,12,1
so 13 sets
so, all distinct sets = [total solution - 3 * (two same & 1 distinct)]/6
= 351 - 39/6 = 312/6 = 52
in all solutions which are un-ordered = 52 + 13 = 65

Bonus Concept

In how many ways can a number be expressed as a sum of two or more consecutive natural numbers ? number of odd factors -1

If N is a natural no. less than 100, then for how many values of N are the nos. 6N+1 and 15N+2 relatively prime?
HCF(6N+1,15N+2))
HCF((12N+2,15N+2))
HCF((12N+2,3N))
HCF((12N+2,2))
HCF((6n+1,1))
so all numbers will give hcf as 1 so 99

How many Ways 199 can be represented as sum of 3 distinct positive integers ?
a+b+c=199
we need positive integers so
a=a'+1
b=b'+1
c=c'+1
so a'+b'+c'=196
now total cases 196+3-1c3-1=198c2
now this will include cases when all r different let those cases are x
and way to arrange them is 6 so 6x
now case when 2 are same and one is different
2a'+b;=196
b'=196-2a'
so 99 cases
and way to arrange them is 3!/2!=3
so 99*3=
now when all are same
so 3a'=196
a'=196/3 whihc is not possible so no case
now total ordered=6x+3*99
so x=198c2-3*99/6

A=333....333 (51 digits) and B= 666....666 (51 digits). Find 52nd digit (counting from right) in the product A*B is
a) 9
b) 7
c) 2
d) 1
e) none of the above

Check out the pattern, 3*6=18 so 2nd right digit is 1 here ... now 33*66=2178 so 3rd right is 1 .... same in 51 digits , 52nd will be 1

What will be remainder when (67^67 + 67) is divided by 68
67 mod 68=-1
so (-1)^67-1
so -2
so 68-2=66 remainder

I went to 'murugan idly shop' to get packed breakfast for my guests.There were 4 types of idli available and i wanted to take atleast 1 pack of each and atmost 5 packs of any.If I bought a total of 10 packs of idly,in how many ways could I have been billed?
a) 80
b) 84
c) 68
d) 56

a+b+c+d=10
1+a'+1+b'+1+c'+1+d'=10
so a'+b'+c'+d'=6
here 0 < =a' < =4
6+4-1c4-1=9c3
now a'=5+a''
5+a''+b'+c'+d'=6
so a''+b;+c'+d'=1
so 4c3
same for all 4 so 4*4c3=16
so 9c3-16
9*8*7/3*2-16
84-16=68

If a and b are natural numbers with no common prime factor and c is the greatest common divisor of (a+ b) and (a^2 +b^2) then how many values can c take?
1) 0
2) 1
3) 2
4) 3
5) Cannot be determined

gcd(a,b) = 1.
a^2+b^2= (a+b)^2-2ab
now c will divide either 2 or ab
Case 1:c divided ab
so c either divides a or b ,If c divides a it must divide a as well
so c will divide a and b both so c=1
Case 2: c divides 2.
c=1 or 2
so value of c could be 1 or 2

Digital sum of 1! +2!... +10 !

1!+2!+3! mod 9=0
4!+5!+6!
4!*(1+5+6)
4!*12 mod9=0
7!+8!=7!(1+8 ) so mod9=0
9!+10! multiple of 9=0
so digital sum=9

a+b+c+d=21, number of solutions such that a,b,c,d are distinct natural numbers.

method 1 :
a=x+1
b=x+y+2
c=x+y+z+3
d=x+y+z+w+4
so 4x + 3y + 2z + w = 11
(6+5+3+2) + (4+3+1) + (2+1) = 27
So, 24*27 = 648 solutions
This is just simple counting

method 2 :
a+b+c+d=21
so a'+1+b'+1+c'+1+d'+1=21
so a'+b'+c'+d'=17
so total solution =17+4-1c4-1=20c3
now we want all distinct cases
so remove cases
case1- when three values are equal
so a=b=c
so 3a+d=20
so a wiill vary from 1 to 6 so 6 soulution
and total ways to arrange them 4!/3!=4
case2- when two are equal
so a=b
2a+c+d=20
so 45 cases but this will include cases when three are equal so remove that cases so 39 cases a
and way to arrange them 4!/2!*2!=12
so 20c3-4*6-12*39=648

Consider a pair (a,b) of natural numbers satisfying a + b^2 +c^3 = abc where c is the greatest common divisor of a and b .Then , how many such pairs are possible?
(a) 2
(b) 3
(c) 4
(d) 5
(e) 6

let a = Mc, b = Nc, so that M and N are coprime. Then: Mc + N^2c^2 +c^3 = MNc^3.
M+N^2c+c^2=MNc^2
So c must divide M. Put M = M'c, then M' + N^2 + c = M'Nc^2.
So M' = (N^2 + c)/(Nc^2 - 1). so M'c^2 = N + (N+c^3)/(Nc^2 - 1). So (N + c^3)/(Nc^2 - 1) is an integer. If c = 1, (N+1)/(N-1) can only be an integer for N = 2 or 3. so (a, b) = (5, 2) and (5, 3).

let c > 1
bcz (N + c^3)/(Nc^2 - 1) is an integer and positive, we must have N + c^3 > = Ng^2 - 1, so N < = (c^3 + 1)/(c^2 - 1). If c = 2, then N < = 3. Then N = 1 gives the solution (a, b) = (4, 2), N = 2 gives (N + c^3)/(Nc^2 - 1) non-integral and hence no solution,

N = 3 gives the solution (a, b) = (4, 6). and for c > 2 there will be no solution so number of values=4

The positive integer N has exactly six distinct integer divisors inclusing 1 and N. The product of five of these is 648. Which of the following must be a divisor of N
A.  4
b.  9
C. 12
D. 16
E.  24

method1- product of factors=N(number of factors/2))
let 6th factor=k
so k*648=N^3
so k*3^4*2^3=N^3
RHS is prefect cube so LHS shuld be perfect cube
so k=3^2=9

Method2 : N = 2*3^2
648 = 1*2*3*6*18
remaining 9 so OA=9

Which of the following is the largest?
a. 419/471
b. 498/533
c. 488/598
d. 455/519

method1-

488/598 there is a difference of 110 which is almost 60*2 20% less than denominator.
D. 455/519 difference=45+19=65 approx more than 10% of denominator.
A. 419/471 difference=21+31=52 more than 10% of denominator.
B. 498/533=35 less than 10% of denominator so B

2512/1089 = ?
a. 2.15
b. 2.30
c. 2.45
d. 2.60

all options are more than 2, hence we start with finding 2*1089 = 2178.
2512 = 2178 + 334
Since 0.1*1089 = 109 (approx), so 334 = 0.3*1089(approx)
Thus, 2512 = (2 + 0.3) * 1089 and the answer will be 2.3

Find value of 1.04^6
1.04^6 is nothing but 6 succesive change of 4% -- now try to mentally : two succesive change of 4% is 8.16%;
now u need to find 3 succesive chang of 8.16% now 2 succesive change of 8.16 is 17% (approx; now two succesive change of 17% & 8.17 % is 27%(approx) so 1.04^6 = 1.27(approx)

How many sets of three or more consecutive odd numbers can be formed such that their sum is 500?
1) 10
2) 0
3) 3
4) 4
5) 5

odd numbers with d=2
sum=500
n/2*(2a+(n-1)*2))=500
n^2+(a-1)*n=500
here a is odd
so a-1 will be even
and so (a-1)*n will be even
so n^2+even=even
so n^2 will be even so n will be even
now
n=500/n- (a-1)
we want n =even
500=2^2*5^3
so find even factors
(2,250) and (10,50) (50,10) and (250,2)
here first term is n
n is greater than 2 so 1st case rejected so 3 case possible

Exactly one of the five numbers listed below is a prime number. Which one is the prime number?
(a) 999,991
(b) 999,973
(c) 999,983
(d) 1,000,001
(e) 7,999,973

a) (10^3)^2 - 3^2 = (1003)(997)
b) (10^2)^3 - 3^3 divisible by (10^2 -3)= 97
d) (10^2)^3 + 1^3 divisible by 101
e) (2*10^2)^3 - 3^3 divisible by 200 -3 =197
so c) is prime