Last visit was: 24 Jul 2024, 04:25 It is currently 24 Jul 2024, 04:25
Toolkit
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
Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.

# When the number 2^1000 is divided by 13, the remainder in the division

SORT BY:
Tags:
Show Tags
Hide Tags
Manager
Joined: 02 Nov 2018
Status:Manager
Posts: 209
Own Kudos [?]: 918 [39]
Given Kudos: 110
GMAT Club Legend
Joined: 03 Oct 2013
Affiliations: CrackVerbal
Posts: 4915
Own Kudos [?]: 7817 [20]
Given Kudos: 221
Location: India
General Discussion
Intern
Joined: 18 Jun 2020
Posts: 7
Own Kudos [?]: 0 [0]
Given Kudos: 0
Manager
Joined: 28 Jan 2018
Posts: 77
Own Kudos [?]: 84 [0]
Given Kudos: 187
Location: India
GPA: 3.5
Re: When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
CrackVerbalGMAT wrote:
This problem is not the most usual type of remainder questions, tested on the GMAT. What makes this question special is, that, although it appears difficult and intimidating at first look, it can actually be solved using some very fundamental concepts on Remainders.

In any remainder question, play smart by trying to express the dividend in the form of (divisor + 1) or (divisor – 1) (as far as you can) so that the remainder turns out to be 1. Apart from this, use the following shortcuts to find out remainders for large values:

Remainder $$\frac{( A+ B )}{K}$$ = Remainder $$\frac{(A)}{K}$$ + Remainder $$\frac{(B)}{K}$$

Remainder $$\frac{(A * B)}{K}$$ = Remainder $$\frac{(A)}{K}$$ * Remainder $$\frac{(B)}{K}$$

The above concepts can be extended to the sum or product of any number of values.

Also, when you write the dividend (which has a power) in the form of $$(divisor + 1) ^{power}$$, the remainder will always be 1. However, if you write the same dividend as $$(divisor – 1) ^ {power}$$, the remainder will be 1 if the power is even and will be -1 if the power is odd. Since the remainder cannot be negative, we add the divisor to the negative remainder to obtain the final remainder.

Let us now try and apply these concepts to the problem at hand.

By writing down the first few powers of 2, we observe that $$2^6$$ i.e. 64 is the number we can write in the form of (13k -1).

Therefore, $$2^{1000}$$ can be written as ($$2^{996}$$) * ($$2^4$$). So,

Remainder $$\frac{(2^{1000})}{13}$$ = Remainder $$\frac{(2^{996})}{13}$$ * Rem$$\frac{(2^4)}{13}$$.

Let’s now calculate the individual remainders.

Remainder $$\frac{(2^{996})}{13}$$:

$$2^{996}$$ = $$(2^6) ^{166}$$ = $$(13*5 – 1)^{166}$$.
So, here, we have written the dividend, $$2^{996}$$ in the form of $$(13k – 1) ^{even power}$$, where 13 is the divisor. As discussed earlier, since the power is even, the remainder here will be 1.

Remainder$$\frac{(2^4)}{13}$$ = Remainder$$\frac{(16)}{13}$$= 3.

Therefore, final remainder = 1 * 3 = 3.

So, the correct answer option is C.

It’s important to not get flustered by the sheer magnitude of the dividend. Because, as we have demonstrated, if you know the concepts that we have discussed in this post, this question is actually very straight forward. The only effort you will have to put in is to find out the power of 2 which can be written in the form of (13k -1) or (13k + 1). Once that is established, the rest of the solution is simple.

Hope that helps!

But sir, If I divide 2^36 bye 13 I get 9 as remainder, It is not working according to the theory of getting 13k-1 as remainder at 2^6/13, If I divide 2^16 by 13 I get 3 as remainder. I don't get It can you please elaborate on it. Because 2^6 = 13k-1 or 13k+1 only seems to work on some powers and not on every even power. I will be very grateful of you to elaborate on the highlighted portion for clear understanding. Thank you very much in advance sir.
Senior Moderator - Masters Forum
Joined: 19 Jan 2020
Posts: 3128
Own Kudos [?]: 2815 [5]
Given Kudos: 1511
Location: India
GPA: 4
WE:Analyst (Internet and New Media)
Re: When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
4
Kudos
The formula is expressed as A^x/N {where A and N are co-prime}

First we calculate ∅(n) where we use n is prime factor
Let N = P^a+Q^b+R^c.......
So, ∅(n) = n(1-1/p)(1-1/q)(1-1/r)........

We have 2^1000/13 (where 2 & 13 are co prime and we have to find remainder)
N = 13 and 13 prime factors = 13^1
So, ∅(n) = 13(1-1/13)
∅(n) = 13(12/13)
∅(n) = 12

So formula will become
A^∅(n) mod n = 1
2^12 mod 13 = 1 (you can calculate this to verify)

So,
2^(12)x mod 13 = will also be 1 always.
The maximum no. Nearest to 1000 multiple of 12 = 996
2^(12)83 mod 13 = 1
2^996 mod 13 = 1
Remaining is 2^4
Now calculate 2^4/13 (remainder)
16/13 leaves remainder 3.
1 from 2^996 * 3 from 2^4 = 3 as remainder.

Let me know if you don't get any step.

Posted from my mobile device
Senior Manager
Joined: 30 Jun 2019
Posts: 271
Own Kudos [?]: 92 [2]
Given Kudos: 8
Re: When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
2
Kudos
not sure if this is correct approach but
cyclicity of 2
2
4
8
6

2^1000 lands on 4. So Dividing 2^1000 by 13 should be the same remainder as with 2^4
2^4 = 16

16/13 = 1 reminder 3
Manager
Joined: 28 Jan 2018
Posts: 77
Own Kudos [?]: 84 [0]
Given Kudos: 187
Location: India
GPA: 3.5
Re: When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
fireagablast wrote:
not sure if this is correct approach but
cyclicity of 2
2
4
8
6

2^1000 lands on 4. So Dividing 2^1000 by 13 should be the same remainder as with 2^4
2^4 = 16

16/13 = 1 reminder 3

This is what exactly was there in my mind but After dividing 1000 by 4, I got 250 and I ended up dividing 250 by 4 and made a mistake. Thanks mate.
2
4
8
6

Senior Moderator - Masters Forum
Joined: 19 Jan 2020
Posts: 3128
Own Kudos [?]: 2815 [0]
Given Kudos: 1511
Location: India
GPA: 4
WE:Analyst (Internet and New Media)
Re: When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
fireagablast wrote:
not sure if this is correct approach but
cyclicity of 2
2
4
8
6

2^1000 lands on 4. So Dividing 2^1000 by 13 should be the same remainder as with 2^4
2^4 = 16

16/13 = 1 reminder 3

This is what exactly was there in my mind but After dividing 1000 by 4, I got 250 and I ended up dividing 250 by 4 and made a mistake. Thanks mate.
2
4
8
6

We can't use cyclicity here. Because we have to check both 2 as well as 13 cyclicity at the same time which is a time taking process.. Easy way is to use Eulers theorem and solve for ∅
Here we have ∅ as 12
So we will divide 1000 by 12.
Whose maximum value under 1000 is 996
2^4 is hence divided by 13.
Giving away 3

Posted from my mobile device
Senior Moderator - Masters Forum
Joined: 19 Jan 2020
Posts: 3128
Own Kudos [?]: 2815 [0]
Given Kudos: 1511
Location: India
GPA: 4
WE:Analyst (Internet and New Media)
When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
fireagablast wrote:
not sure if this is correct approach but
cyclicity of 2
2
4
8
6

2^1000 lands on 4. So Dividing 2^1000 by 13 should be the same remainder as with 2^4
2^4 = 16

16/13 = 1 reminder 3

It's coincidental, you can't depict all values using this.
1000 is an easy number. We could have some complicated number. And then it will all mess up. ∅ is calculated because of that complex number. Let's say if ∅ was 101 you can't use cyclicity, here 12 is a multiple of four and can be used as cyclicity number among number. So it's better to use Eulers theorem or any other for these specific methods.

Posted from my mobile device
Intern
Joined: 05 Apr 2020
Posts: 16
Own Kudos [?]: 33 [3]
Given Kudos: 108
Re: When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
3
Kudos
2^1000=(2^4)^250
=16^250
=16*16*16.......upto 250 terms
Every time 250 is divided by 13 it leaves a remainder we get
=3*3*3..............upto 250 terms= 3^250
Since in these there can be a factor of 13 ,
we know that 3^3=27( which when divided by 1 gives remainder 1)

so, 3^250= (3^249)*3
=(3^3)^83*3
=(27)^83*3
when divide by 13 we get
=(1)^83*3=3
Hence remainder we got is 3
GMAT Club Legend
Joined: 03 Jun 2019
Posts: 5312
Own Kudos [?]: 4248 [0]
Given Kudos: 161
Location: India
GMAT 1: 690 Q50 V34
WE:Engineering (Transportation)
Re: When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
Asked: When the number $$2^{1000}$$ is divided by 13, the remainder in the division is

$$2^6 = 64 = 13*5 - 1$$
$$1000 = 6*166 + 4$$
$$2^1000 = 2^6*166 * 2^4$$

The remainder when 2^1000 is divided by 13 = (-1)^166 * (16-13) = 3

IMO C
Non-Human User
Joined: 09 Sep 2013
Posts: 34061
Own Kudos [?]: 853 [0]
Given Kudos: 0
Re: When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
Re: When the number 2^1000 is divided by 13, the remainder in the division [#permalink]
Moderator:
Math Expert
94605 posts