stonecold wrote:

If P is a prime number greater than 5, what is the remainder when P^2 is divided by 8.

A) 4

B) 3

C) 2

D) 1

E) Cannot be determined

If we let P = 7, then the remainder when P^2 is divided by 8 is 1 since 49/8 = 6 remainder 1.

If we let P = 11, then the remainder when P^2 is divided by 8 is 1 since 121/8 = 15 remainder 1.

If we let P = 13, then the remainder when P^2 is divided by 8 is 1 since 169/8 = 21 remainder 1.

At this point, you might wonder: is the remainder always 1? If it is, then the answer will be D; otherwise, the answer will be E. Let’s prove it algebraically.

Since any prime number greater than 5 is odd, and an odd number can be written as 4n + 1 or 4n + 3 for some positive integer n, we can express P as P = 4n + 1 or P = 4n + 3.

Case 1: If P = 4n + 1, we have:

P^2 = (4n + 1)^2 = 16n^2 + 8n + 1

We see that the first two terms are divisible by 8; thus, the remainder must be the last term, which is 1.

Case 2: If P = 4n + 3, we have:

P^2 = (4n + 3)^2 = 16n^2 + 24n + 9

We see that the first two terms are divisible by 8 and the last term 9 has a remainder of 1 when it’s divided by 8; thus, the remainder must be 1.

Thus, we see that when the square of a prime (greater than 5) is divided by 8, the remainder will always be 1.

Alternate Solution:

Let’s consider P^2 - 1 = (P - 1)(P + 1).

Since P > 5, both P - 1 and P + 1 are even because P is prime. Moreover, since P - 1 and P + 1 are consecutive even integers, one of them is divisible by 4. Since each of P - 1 and P + 1 are even and since, furthermore, one of them is divisible by 4, their product, which is P^2 - 1, is divisible by 8. Since P^2 - 1 is divisible by 8, P^2 will leave a remainder of 1 when divided by 8.

Answer: D

_________________

Scott Woodbury-Stewart

Founder and CEO

GMAT Quant Self-Study Course

500+ lessons 3000+ practice problems 800+ HD solutions