Problem Solving

What is the remainder when 7^74 - 5^74 is divided by 24?

A. 0
B. 1
C. 2
D. 3
E. None of these

The OA is A.

Wow. I need a lot of help here. How can I solve this PS question? Experts, can you help me?

This one requires remainder and/or factoring skills that the GMAT doesn't expect of you, at least in 2017. The cleverest ways of solving this will use remainder properties that will spark more questions than they answer, so let me give a clumsier approach that's more in keeping with the GMAT.

7�� - 5�� =>

(7²)³� - (5²)³� =>

49³� - 25³�

And what do you know, 49 has remainder 1 by 24, and 25 has remainder 1 by 24! This means we've really got

1³� - 1³�, or 0

So that big number is divisible by 24, and its remainder by 24 is 0.

Just to follow up on my last post, that solution relies on multiplicative remainders, a topic that shouldn't appear on the GMAT. To get a feel for how these work, consider something like this:

5 has remainder 1 when divided by 4. (For the rest of the post, I'll use the term "mod 4" rather than "when divided by 4".) Notice that 5 * 5 = 25, which also has remainder 1 mod 4. This because the remainders are multiplicative: if we multiply remainder 1 mod 4 by remainder 1 mod 4, we end up with remainder 1 * 1 mod 4. We need to be treating each number by the same mod (we can't do remainder 1 mod 4 * remainder 1 mod 3, at least not that simply), but if we do, the multiplication sorts out our remainders for us.

With that in mind, once I see that 49 = 1 mod 24, I can replace any 49 I see with 1, so 49 * 49 * 49 * ... * 49 is the same, mod 24, as 1 * 1 * 1 * ... * 1.

I know I said above that I wouldn't do this, but here's another explanation I just couldn't resist:

7�� - 5�� =>

(7² - 5²) * (7�² + 5² * 7�� + 5� * 7�� + ... + 5�� * 7² + 5�²) =>

24 * (7�² + 5² * 7�� + 5� * 7�� + ... + 5�� * 7² + 5�²)

So our number divides by 24!

To make this useful, here's a follow up question: how do I know that my factorization works?