GATE CS 2014 Set 2 Q.59 (CS Q.49): Combinatorics, Counting, Recurrence Relations and Generating Functions

The number of distinct positive integral factors of 2014 is _____.

Your answer

Official answer and solution

Solution

Find the prime factorization of 2014 and apply the divisor formula.

Prime Factorization:
- Divide by 2: $2014 / 2 = 1007$ .
- Test primes on $1007$ $1007$ :
  - $\sqrt{1007} \approx 31.7$ .
  - $1007$ is not divisible by 3 ( $1+0+0+7 = 8$ ), 5, 7 ( $1007 = 7 \times 143 + 6$ ), 11 ( $1007 = 11 \times 91 + 6$ ), 13 ( $1007 = 13 \times 77 + 6$ ), 17 ( $1007 = 17 \times 59 + 4$ ).
  - Test 19: $1007 / 19 = 53$ .
- Both 19 and 53 are prime numbers.
$2014 = 2^1 \times 19^1 \times 53^1.$
Divisor Count Formula:
For $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ , the number of positive integral divisors is:
$d(n) = (a_1 + 1)(a_2 + 1)(a_3 + 1) = (1 + 1)(1 + 1)(1 + 1) = 2 \times 2 \times 2 = 8.$
Listing the Divisors:
The 8 divisors are: $1, 2, 19, 38, 53, 106, 1007, 2014$ .

Final answer

Common trap

Assuming 1007 is prime without testing divisors up to sqrt(1007).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.