GMAT Question of the Day: Daily via email | Daily via Instagram New to GMAT Club? Watch this Video

 It is currently 06 Jul 2020, 20:06

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# What is the remainder when (18^22)^10 is divided by 7 ?

Author Message
TAGS:

### Hide Tags

Manager
Joined: 16 Aug 2019
Posts: 126
What is the remainder when (18^22)^10 is divided by 7 ?  [#permalink]

### Show Tags

15 May 2020, 17:07
Bunuel wrote:
Financier wrote:
What is the remainder when (18^22)^10 is divided by 7 ?

А 1
B 2
C 3
D 4
E 5

I think this question is beyond the GMAT scope. It can be solved with Fermat's little theorem, which is not tested on GMAT. Or another way:

$$(18^{22})^{10}=18^{220}=(14+4)^{220}$$ now if we expand this all terms but the last one will have 14 as multiple and thus will be divisible by 7. The last term will be $$4^{220}$$. So we should find the remainder when $$4^{220}$$ is divided by 7.

$$4^{220}=2^{440}$$.

2^1 divided by 7 yields remainder of 2;
2^2 divided by 7 yields remainder of 4;
2^3 divided by 7 yields remainder of 1;

2^4 divided by 7 yields remainder of 2;
2^5 divided by 7 yields remainder of 4;
2^6 divided by 7 yields remainder of 1;
...

So the remainder repeats the pattern of 3: 2-4-1. So the remainder of $$2^{440}$$ divided by 7 would be the same as $$2^2$$ divided by 7 (440=146*3+2). $$2^2$$ divided by 7 yields remainder of 4.

Fermat's little theorem
If p is a prime number

then for any integer a, the number (a^p –a ) is an integer multiple of p, that is, p〡(a^p –a )
and if p & a mutually prime, then p〡(a^p-1 –1)

I was wondering how could we, by using this theorem, to apply it to this question

the question can be simplified into 4^220 = 2^440, so we have to find the number of the exponent that can be divided by 7 as well as be closet to 440

from above theorem, I intuitively think of
2^441- 2 = 441 * x = 7 * 63 * x
2(2^440- 1) = 7 * 63 * x
also 2&7 mutually prime
2^440- 1 = 7 * y (must be multiple of 7)
2^440= 1 (mod7)…..remainer is 1, totally wrong

I check where my missing point lead to this big mistake
I notice in definition it require that p be “prime number”
but 441 = 7^2 * 9 , not prime
and this is how it lead to my false remainer

if we do the calculation in the definition of Fermat’s theorem, which said p must be prime
now assume a = 2^x , x be the unknown and can be any given integer, in the polynomial of
[(2^x)7 - (2^x)] = 7 * z
(2^x)[ (2^x)6 – 1] = 7 * z

also 2^x & 7 mutually prime
7〡[(2^x)6 – 1]
[ (2^x)6 – 1] = 7 * n ……(1)

Here for 6x, find the one closet to 440 since this question mainly concern about (2^440)/7
440 / 6 = 73 …2
440 = 73 * 6 + 2
2^2 [ (2^6)73 – 1] = 2^2 (7 * n)

Thus 2^440 = 2^2 (mod 7), remainer 4 , correct
What is the remainder when (18^22)^10 is divided by 7 ?   [#permalink] 15 May 2020, 17:07

Go to page   Previous    1   2   3   [ 41 posts ]