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?
What is the remainder when 7^74 - 5^74 is divided by 24?
This topic has expert replies
-
- GMAT Instructor
- Posts: 2630
- Joined: Wed Sep 12, 2012 3:32 pm
- Location: East Bay all the way
- Thanked: 625 times
- Followed by:119 members
- GMAT Score:780
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.
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.
-
- GMAT Instructor
- Posts: 2630
- Joined: Wed Sep 12, 2012 3:32 pm
- Location: East Bay all the way
- Thanked: 625 times
- Followed by:119 members
- GMAT Score:780
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.
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.
-
- GMAT Instructor
- Posts: 2630
- Joined: Wed Sep 12, 2012 3:32 pm
- Location: East Bay all the way
- Thanked: 625 times
- Followed by:119 members
- GMAT Score:780
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?
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?
GMAT/MBA Expert
- Scott@TargetTestPrep
- GMAT Instructor
- Posts: 7247
- Joined: Sat Apr 25, 2015 10:56 am
- Location: Los Angeles, CA
- Thanked: 43 times
- Followed by:29 members
Note that 7^2 = 49 produces a remainder of 1 when divided by 24. Since 7^3 = 7^2 x 7, the remainder from the division of 7^3 by 24 is 7 and since 7^4 = 7^2 x 7^2, the remainder from the division of 7^4 by 24 is 1. We can generalize this as follows: 7^n produces a remainder of 1 when n is even and produces a remainder of 7 when n is odd.
Similarly, 5^2 = 25 produces a remainder of 1 when divided by 24. Since 5^3 = 5^2 x 5, the remainder from the division of 5^3 by 24 is 5 and since 5^4 = 5^2 x 5^2, the remainder from the division of 5^4 by 24 is 1. We can generalize this as follows: 5^n produces a remainder of 1 when n is even and produces a remainder of 5 when n is odd.
Thus, the remainder from division of 7^74 and 5^74 by 24 are both 1, and so the remainder from the division of 7^74 - 5^74 is 1 - 1 = 0.
Answer: A
Scott Woodbury-Stewart
Founder and CEO
[email protected]
See why Target Test Prep is rated 5 out of 5 stars on BEAT the GMAT. Read our reviews