Number Theory Concepts For CAT - Hemant Malhotra


  • Director at ElitesGrid | CAT 2016 - QA : 99.94, LR-DI - 99.70% / XAT 2017 - QA : 99.975


    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 2015 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 = 2m, what is the remainder when N! is divided by 2N ?

    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 M2 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

    x2 = 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


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.