It is currently 23 Feb 2018, 08:44

### 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

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# What will be the remainder when 13^7 + 14^7 + 15^7 + 16^7 is

Author Message
Current Student
Joined: 11 May 2008
Posts: 553
What will be the remainder when 13^7 + 14^7 + 15^7 + 16^7 is [#permalink]

### Show Tags

04 Aug 2008, 23:51
This topic is locked. If you want to discuss this question please re-post it in the respective forum.

What will be the remainder when 13^7 + 14^7 + 15^7 + 16^7 is divided by 58?
57
1
30
0
28
Director
Joined: 27 May 2008
Posts: 540

### Show Tags

05 Aug 2008, 00:28
D 0.

2.5 minutes
Senior Manager
Joined: 06 Apr 2008
Posts: 428

### Show Tags

05 Aug 2008, 00:42
Is this really a GMAT Q?
Director
Joined: 27 May 2008
Posts: 540

### Show Tags

05 Aug 2008, 00:47
1
KUDOS
13 = 58 - 45
14 = 58 - 44
15 = 58 - 43
16 = 58 - 42

13^7 + 14^7 + 15^7 + 16^7
= (58-45)^7 + (58-44)^7 + (58-43)^7 + (58-42)^7

if we open this ... in all (58-x)^7. there be 7 terms with powers of 58 and one term with only x
all powers of 58 will be divisible by 58
we just need to check 45+44+43+42 = 174 also divisible by 58

remainder 0
Senior Manager
Joined: 06 Apr 2008
Posts: 428

### Show Tags

05 Aug 2008, 00:55
durgesh79 wrote:
13 = 58 - 45
14 = 58 - 44
15 = 58 - 43
16 = 58 - 42

13^7 + 14^7 + 15^7 + 16^7
= (58-45)^7 + (58-44)^7 + (58-43)^7 + (58-42)^7

if we open this ... in all (58-x)^7. there be 7 terms with powers of 58 and one term with only x
all powers of 58 will be divisible by 58
we just need to check 45+44+43+42 = 174 also divisible by 58

remainder 0

Thanks ... makes sense!
Manager
Joined: 15 Jul 2008
Posts: 205

### Show Tags

05 Aug 2008, 02:57
durgesh79 wrote:
13 = 58 - 45
14 = 58 - 44
15 = 58 - 43
16 = 58 - 42

13^7 + 14^7 + 15^7 + 16^7
= (58-45)^7 + (58-44)^7 + (58-43)^7 + (58-42)^7

if we open this ... in all (58-x)^7. there be 7 terms with powers of 58 and one term with only x
all powers of 58 will be divisible by 58
we just need to check 45+44+43+42 = 174 also divisible by 58

remainder 0

I am not clear on this. The x terms all have power 7. How do you deal with that ?
If 45+44+43+42 = 174 is divisible by 58, is 45^7 + 44^7 + 43^7...... also divisible by 58 ?
Senior Manager
Joined: 06 Apr 2008
Posts: 428

### Show Tags

05 Aug 2008, 03:11
bhushangiri wrote:
durgesh79 wrote:
13 = 58 - 45
14 = 58 - 44
15 = 58 - 43
16 = 58 - 42

13^7 + 14^7 + 15^7 + 16^7
= (58-45)^7 + (58-44)^7 + (58-43)^7 + (58-42)^7

if we open this ... in all (58-x)^7. there be 7 terms with powers of 58 and one term with only x
all powers of 58 will be divisible by 58
we just need to check 45+44+43+42 = 174 also divisible by 58

remainder 0

I am not clear on this. The x terms all have power 7. How do you deal with that ?
If 45+44+43+42 = 174 is divisible by 58, is 45^7 + 44^7 + 43^7...... also divisible by 58 ?

If you expand any ploynomial such that (x - y ) ^n, you will always find x in all terms except last. So in this Q all you have to ensure is that sum of last terms is divisble by 58 or not. If yes then sum is divisible by 58
Manager
Joined: 15 Jul 2008
Posts: 205

### Show Tags

05 Aug 2008, 03:17
nmohindru wrote:

If you expand any ploynomial such that (x - y ) ^n, you will always find x in all terms except last. So in this Q all you have to ensure is that sum of last terms is divisble by 58 or not. If yes then sum is divisible by 58

I know that rule - binomial expansion. x will always be present in all terms except the last. But the last term will have power n.
In context of current question, the last terms are not 45, 44, 43, and 42. But 45^7, 44^7, 43^7, and 42^7

I also know 45+44+43+42 = 174 is divisible by 58.
But does that mean 45^7 + 44^7 + 43^7 + 42^7 is also divisible by 58 ?
Senior Manager
Joined: 06 Apr 2008
Posts: 428

### Show Tags

05 Aug 2008, 03:40
bhushangiri wrote:
nmohindru wrote:

If you expand any ploynomial such that (x - y ) ^n, you will always find x in all terms except last. So in this Q all you have to ensure is that sum of last terms is divisble by 58 or not. If yes then sum is divisible by 58

I know that rule - binomial expansion. x will always be present in all terms except the last. But the last term will have power n.
In context of current question, the last terms are not 45, 44, 43, and 42. But 45^7, 44^7, 43^7, and 42^7

I also know 45+44+43+42 = 174 is divisible by 58.
But does that mean 45^7 + 44^7 + 43^7 + 42^7 is also divisible by 58 ?

Hmmm .... you are right

I was trying another thing according to which

$$a^n + b^n + c^n + d^n$$ is divisible by a + b + c + d if n is odd.

$$a^3 + b^3 = (a + b) (a^2 -ab + b^2)$$

This will give us the answer
Manager
Joined: 15 Jul 2008
Posts: 205

### Show Tags

05 Aug 2008, 03:46
nmohindru wrote:

Hmmm .... you are right

I was trying another thing according to which

$$a^n + b^n + c^n + d^n$$ is divisible by a + b + c + d if n is odd.

$$a^3 + b^3 = (a + b) (a^2 -ab + b^2)$$

This will give us the answer

Cud u plz elaborate on the rule ? What is the rule, and under what conditions does it hold ?
Senior Manager
Joined: 06 Apr 2008
Posts: 428

### Show Tags

05 Aug 2008, 03:56
bhushangiri wrote:
nmohindru wrote:

Hmmm .... you are right

I was trying another thing according to which

$$a^n + b^n + c^n + d^n$$ is divisible by a + b + c + d if n is odd.

$$a^3 + b^3 = (a + b) (a^2 -ab + b^2)$$

This will give us the answer

Cud u plz elaborate on the rule ? What is the rule, and under what conditions does it hold ?

The rule is

$$a^n + b^n + c^n + d^n$$ is divisible by a + b + c + d if n is odd.

because $$a^n + b^n + c^n + d^n$$ when n is odd will become (a + b + c + d) (a^n - a^n-1*b ....... )
Manager
Joined: 15 Jul 2008
Posts: 205

### Show Tags

05 Aug 2008, 04:10
nmohindru wrote:

The rule is

$$a^n + b^n + c^n + d^n$$ is divisible by a + b + c + d if n is odd.

because $$a^n + b^n + c^n + d^n$$ when n is odd will become (a + b + c + d) (a^n - a^n-1*b ....... )

I think there are additional constraints, i can think of atleast one.. that a,b,c,d need to be consecutive numbers. Coz it doesnt work with a=1, b=2, c=4. but works with 1,2,3 or 2,3,4 or 1,2,3,4.

But thanks buddy. Thats todays gain.. one new rule.
Senior Manager
Joined: 06 Apr 2008
Posts: 428

### Show Tags

05 Aug 2008, 04:15
bhushangiri wrote:
nmohindru wrote:

The rule is

$$a^n + b^n + c^n + d^n$$ is divisible by a + b + c + d if n is odd.

because $$a^n + b^n + c^n + d^n$$ when n is odd will become (a + b + c + d) (a^n - a^n-1*b ....... )

I think there are additional constraints, i can think of atleast one.. that a,b,c,d need to be consecutive numbers. Coz it doesnt work with a=1, b=2, c=4. but works with 1,2,3 or 2,3,4 or 1,2,3,4.

But thanks buddy. Thats todays gain.. one new rule.

Yes you are right .... works only for consecutive numbers
GMAT Tutor
Joined: 24 Jun 2008
Posts: 1346

### Show Tags

05 Aug 2008, 04:19
arjtryarjtry wrote:
What will be the remainder when 13^7 + 14^7 + 15^7 + 16^7 is divided by 58?
57
1
30
0
28

If you know modular arithmetic:

13^7 + 14^7 + 15^7 + 16^7 is clearly even --> divisible by 2

If it's also divisible by 29, it's divisible by 58.

Notice
16 ~ -13 mod 29
15 ~ -14 mod 29

(~ means 'congruent to')

13^7 + 14^7 + 15^7 + 16^7 ~ 13^7 + 14^7 + (-14)^7 + (-13)^7 mod 29
~ 0 mod 29

So the expression is divisible by 2 and 29, and thus by 58.
_________________

GMAT Tutor in Toronto

If you are looking for online GMAT math tutoring, or if you are interested in buying my advanced Quant books and problem sets, please contact me at ianstewartgmat at gmail.com

Director
Joined: 27 May 2008
Posts: 540

### Show Tags

05 Aug 2008, 05:24
good discussion..

another method came to my mind while driving home today ...

13^7 + 14^7 + 15^7 + 16^7
= (14.5-1.5)^7 + (14.5-0.5)^7 + (14.5+0.5)^7 + (14.5+1.5)^7

if you open it all terms with odd powers of 1.5 and 0.5 will cancel each other.....

for every Postive term with 7C0, 7C2, 7C4 and 7C6, we can take out 4*14.5 as a common factor .... (i did that on paper) and guess what is 4*14.5... its 58 ...
Manager
Joined: 15 Jul 2008
Posts: 205

### Show Tags

05 Aug 2008, 06:49
durgesh79 wrote:
good discussion..

another method came to my mind while driving home today ...

13^7 + 14^7 + 15^7 + 16^7
= (14.5-1.5)^7 + (14.5-0.5)^7 + (14.5+0.5)^7 + (14.5+1.5)^7

if you open it all terms with odd powers of 1.5 and 0.5 will cancel each other.....

for every Postive term with 7C0, 7C2, 7C4 and 7C6, we can take out 4*14.5 as a common factor .... (i did that on paper) and guess what is 4*14.5... its 58 ...

too good professor..
Director
Joined: 27 May 2008
Posts: 540

### Show Tags

05 Aug 2008, 07:01
bhushangiri wrote:
too good professor..

not that good...
i think i just got lucky with this question .... there are faults in both of my approaches ... somehow got the right answer
moral : try solving maths question while driving, your approach may be wrong, but you'll get the right answer
Retired Moderator
Joined: 18 Jul 2008
Posts: 959

### Show Tags

05 Aug 2008, 17:48
Just wondering. How do you rate the difficulty on this question if it was on that gmat?
Intern
Joined: 10 Aug 2008
Posts: 22
Schools: Emory Goizueta (Class of 2013)
WE 1: Management consultant
WE 2: Marketing consultant

### Show Tags

12 Aug 2008, 06:05
a^n + b^n = (a+b)(a^n-a^(n-1)*b+...+b^n)

13^7+16^7 = 29*(13^6 - 13^5*16+....+16^6) ->29*an odd number (as 13^6 is odd while the others are all even)
Similarly 14^7+15^7= 29*an odd number

13^7+14^7+15^7+16^7=29*an even number=29*2k=58k
Thus, the sum is divisible by 58
SVP
Joined: 07 Nov 2007
Posts: 1789
Location: New York

### Show Tags

12 Aug 2008, 06:32
IanStewart wrote:
arjtryarjtry wrote:
What will be the remainder when 13^7 + 14^7 + 15^7 + 16^7 is divided by 58?
57
1
30
0
28

If you know modular arithmetic:

13^7 + 14^7 + 15^7 + 16^7 is clearly even --> divisible by 2

If it's also divisible by 29, it's divisible by 58.

Notice
16 ~ -13 mod 29
15 ~ -14 mod 29

(~ means 'congruent to')
13^7 + 14^7 + 15^7 + 16^7 ~ 13^7 + 14^7 + (-14)^7 + (-13)^7 mod 29
~ 0 mod 29

So the expression is divisible by 2 and 29, and thus by 58.

I couldn't understand the highlighted part.

Could you elaborate
_________________

Smiling wins more friends than frowning

Re: funny remainder...   [#permalink] 12 Aug 2008, 06:32

Go to page    1   2    Next  [ 22 posts ]

Display posts from previous: Sort by

# What will be the remainder when 13^7 + 14^7 + 15^7 + 16^7 is

Moderator: chetan2u

 Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.