What is the remainder when 7^7 is divided by 19?
Ho do I solve this one?
remainder problem
This topic has expert replies
GMAT/MBA Expert
- Brent@GMATPrepNow
- GMAT Instructor
- Posts: 16207
- Joined: Mon Dec 08, 2008 6:26 pm
- Location: Vancouver, BC
- Thanked: 5254 times
- Followed by:1268 members
- GMAT Score:770
Two questions:aarzoo wrote:What is the remainder when 7^7 is divided by 19?
Ho do I solve this one?
1) Where are the 5 answer choices that always accompany GMAT questions?
2) What is the source of this question?
Unless I'm missing something, this question really isn't a GMAT-quality question, since it requires too much number crunching (e.g., looking for a pattern by finding the remainder when 7^2, 7^3 and 7^4 are divided by 19)
We could use some modular arithmetic (https://en.wikipedia.org/wiki/Modular_arithmetic) to solve this, but I believe this would be out of scope for the GMAT.
Cheers,
Brent
-
- 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'd use some smaller powers to help you.
7� = 7³ * 7³ * 7
Now look for powers of 19 close to these. 7³ = 343, and 19² = 361, so those are good candidates. Notice that 361 - 19 = 342, so 343 / 342 has remainder 1. Thus 7³ has remainder 1 by 19, and
7� = 7³ * 7³ * 7 = (remainder 1) * (remainder 1) * (remainder 7) = remainder 7.
7� = 7³ * 7³ * 7
Now look for powers of 19 close to these. 7³ = 343, and 19² = 361, so those are good candidates. Notice that 361 - 19 = 342, so 343 / 342 has remainder 1. Thus 7³ has remainder 1 by 19, and
7� = 7³ * 7³ * 7 = (remainder 1) * (remainder 1) * (remainder 7) = remainder 7.