CAT 2018 Slot 1 Quant Solutions: Key Number Theory Problems & Strategies
CAT 2018's Quantitative Ability section included challenging number theory problems. Below is a structured analysis of key questions, solving strategies, and common pitfalls for candidates.
1. Problem 1: Divisors of an Integer
Question:
Find the number of positive integers that divide both ( N = 2^3 \times 3^2 \times 5^1 ) and ( M = 2^2 \times 3^1 \times 7^2 ).
Solution:
Key Concept: GCD (greatest common divisor) determines common divisors.
Steps:
Compute ( \text{GCD}(N, M) = 2^{\min(3,2)} \times 3^{\min(2,1)} \times 5^{\min(1,0)} \times 7^{\min(0,2)} = 2^2 \times 3^1 = 12 ).
Number of divisors of GCD(12) = ( (2+1)(1+1) = 6 ).
Answer: 6
Common Mistake:
Directly counting divisors of ( N ) and ( M ) separately (incorrect approach).
2. Problem 2: Remainders & Modular Arithmetic
Question:
What is the remainder when ( 7^{100} + 5^{100} ) is divided by 12?
Solution:
Key Concept: Euler’s Theorem (( a^{\phi(n)} \equiv 1 \mod n )) or cyclicity.
Steps:
( 7 \mod 12 = 7 ), cycle for ( 7^k \mod 12 ): 7, 1, 7, 1… (period 2).
( 7^{100} \mod 12 = 1 ) (even exponent).
( 5 \mod 12 = 5 ), cycle for ( 5^k \mod 12 ): 5, 1, 5, 1… (period 2).
( 5^{100} \mod 12 = 1 ).
Total remainder: ( 1 + 1 = 2 \mod 12 ).
Answer: 2
Common Mistake:
Forgetting to reduce exponents modulo ( \phi(n) ) or miscalculating cycles.
3. Problem 3: Prime Factorization Application
Question:
A number ( N ) has exactly 12 divisors. If ( N ) is divisible by 6 but not by 4, how many such numbers exist?
Solution:
Key Concept: Divisor count formula: ( (a_1+1)(a_2+1)... ).
Steps:
( N = 2^a \times 3^b \times \text{other primes} ).
Constraints:
( a \geq 1 ) (divisible by 2), ( b \geq 1 ) (divisible by 3).
( N \not\equiv 0 \mod 4 \Rightarrow a = 1 ).
Divisor count: ( (1+1)(b+1)(c+1)... = 12 ).
Possible factorizations of 12:
( 12 = 2 \times 6 \Rightarrow b+1 = 6, \text{other primes} = 0 \Rightarrow b=5 ).
( 12 = 2 \times 2 \times 3 \Rightarrow b+1=2, c+1=3 \Rightarrow b=1, c=2 ).
Valid ( N ):
Case 1: ( N = 2^1 \times 3^5 = 486 ).
Case 2: ( N = 2^1 \times 3^1 \times 5^2 = 150 ).
Total numbers: 2.
Answer: 2
Common Mistake:
Overlooking the "not divisible by 4" condition or miscounting prime factors.
4. Problem 4: Diophantine Equation
Question:
Find the number of positive integer solutions to ( 3x + 4y = 100 ).
Solution:
Key Concept: Linear Diophantine equations.
Steps:
General solution: ( x = x_0 + 4t ), ( y = y_0 - 3t ).
Find particular solution: ( x_0 = 0 \Rightarrow y = 25 ).
( x > 0 \Rightarrow 4t > 0 \Rightarrow t \geq 1 ).
( y > 0 \Rightarrow 25 - 3t > 0 \Rightarrow t < 8.33 ).
Valid ( t ): 1 to 8. Total solutions: 8.
Answer: 8
Common Mistake:
Ignoring non-negative constraints for ( x ) and ( y ).
Final Tips for CAT 2018 Quant
Number Theory: Master GCD/LCM, modular arithmetic, and prime factorization.
Time Management: Skip brute-force problems (e.g., complex equations).
Check Constraints: Always verify divisibility, positivity, and edge cases.
Practice Set (Varying Difficulty):
Find the remainder of ( 3^{100} ) divided by 13.
How many positive integers divide ( 10^6 ) but not ( 10^5 )?
For detailed solutions, refer to CAT 2018 official answer key or platforms like * Oliveboard * or * Vimal’s CAT Course *.
Target Score Strategy:
Easy Questions (1-2 min): Solve quickly (e.g., Problem 1).
Medium Questions (3-5 min): Focus on modular arithmetic (Problem 2).
Hard Questions (6+ min): Tackle Diophantine equations (Problem 4) last.
Let me know if you need further clarification! 📚✨
|
