Problem Solving

[GMAT math practice question]

m and n are integers. Which of the following cannot be the value of (m^2+1)(n^2+1)?

A. 10
B. 20
C. 50
D. 60
E. 100

=>

D is likely to be the answer as it is the only one which is divisible by 3. We test (m^2+1)(n^2+1) for divisibility by 3. Note that every integer m can be written as 3k, 3k+1 or 3k+2 for some integer k.
If m = 3k, then m^2 = 9k^2, and m^2 + 1 = 9k^2 + 1 = 3(3k^2) + 1.
If m = 3k+1, then m^2 = (3k+1)^2 = 9k^2 + 6k + 1 = 3(3k^2+2k) + 1, and m^2 + 1 = 3(3k^2+2k) + 2.
If m = 3k+2, then m^2 = (3k+2)^2 = 9k^2 + 12k + 4 = 3(3k^2+4k+1) + 1, and m^2 + 1 = 3(3k^2+4k+1) + 2.
In all cases, m^2+1 is not divisible by 3. Similarly, n^2+1 is not divisible by 3. Since 3 is a prime number, this implies that (m^2+1)(n^2+1) is not divisible by 3.

Therefore, A is the answer.
Answer: A