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

Re: funny remainder... [#permalink]
Show Tags
05 Aug 2008, 00:28
D 0. 2.5 minutes



Senior Manager
Joined: 06 Apr 2008
Posts: 428

Re: funny remainder... [#permalink]
Show Tags
05 Aug 2008, 00:42
Is this really a GMAT Q?



Director
Joined: 27 May 2008
Posts: 540

Re: funny remainder... [#permalink]
Show Tags
05 Aug 2008, 00:47
1
This post received KUDOS
13 = 58  45 14 = 58  44 15 = 58  43 16 = 58  42
13^7 + 14^7 + 15^7 + 16^7 = (5845)^7 + (5844)^7 + (5843)^7 + (5842)^7
if we open this ... in all (58x)^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

Re: funny remainder... [#permalink]
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 = (5845)^7 + (5844)^7 + (5843)^7 + (5842)^7
if we open this ... in all (58x)^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

Re: funny remainder... [#permalink]
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 = (5845)^7 + (5844)^7 + (5843)^7 + (5842)^7
if we open this ... in all (58x)^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

Re: funny remainder... [#permalink]
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 = (5845)^7 + (5844)^7 + (5843)^7 + (5842)^7
if we open this ... in all (58x)^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

Re: funny remainder... [#permalink]
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

Re: funny remainder... [#permalink]
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

Re: funny remainder... [#permalink]
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

Re: funny remainder... [#permalink]
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^n1*b ....... )



Manager
Joined: 15 Jul 2008
Posts: 205

Re: funny remainder... [#permalink]
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^n1*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

Re: funny remainder... [#permalink]
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^n1*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

Re: funny remainder... [#permalink]
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

Re: funny remainder... [#permalink]
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.51.5)^7 + (14.50.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

Re: funny remainder... [#permalink]
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.51.5)^7 + (14.50.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

Re: funny remainder... [#permalink]
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

Re: funny remainder... [#permalink]
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

Re: funny remainder... [#permalink]
Show Tags
12 Aug 2008, 06:05
a^n + b^n = (a+b)(a^na^(n1)*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

Re: funny remainder... [#permalink]
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
_________________
Your attitude determines your altitude Smiling wins more friends than frowning




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



Go to page
1 2
Next
[ 22 posts ]



