|
Author |
Message |
|
TAGS:
|
|
|
SVP
Joined: 03 Feb 2003
Posts: 1683
Followers: 4
Kudos [?]:
16
[0], given: 0
|
Is integer Q evenly divisible by 6? (1) Q= 1, where N is a [#permalink]
 07 Oct 2003, 10:45
Question Stats:
0% (00:00) correct
 0% (00:00) wrong based on 0 sessions
Is integer Q evenly divisible by 6?
(1) Q=[7^N]–1, where N is a positive integer
(2) Q is evenly divisible by [2^2]*[7^7]*[3^3]
|
|
|
|
|
|
|
Manager
Joined: 26 Aug 2003
Posts: 238
Location: United States
Followers: 1
Kudos [?]:
1
[0], given: 0
|
D?
(1) Guessed the numbers and did some pattern matching.
(2) In other words Q is divisible by 108 * 7^7, since 108 is divisible by 6, so is Q.
|
|
|
|
|
|
SVP
Joined: 03 Feb 2003
Posts: 1683
Followers: 4
Kudos [?]:
16
[0], given: 0
|
D is correct
(1) can you prove it?
(2) Q contains 2 and 3 and so divisible by 6.
|
|
|
|
|
|
GMAT Instructor
Joined: 07 Jul 2003
Posts: 773
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 5
Kudos [?]:
9
[0], given: 0
|
stolyar wrote: D is correct
(1) can you prove it?
(2) Q contains 2 and 3 and so divisible by 6.
(1):
(x + y)^n will contains n + 1 terms in its expansion: n of those terms will have some factor of x and the last one will be y^n. Now let x = 6 and y = 1. Regardless of what n is, there will be one y^n or 1^n term in the expansion plus a whole bunch of other terms all divisible by 6. Hence, if we subtract out the y^n term, we are left with a sum of terms all divisible by x (or 6) hence the sum of those terms is also divisible by 6.
_________________
Best,
AkamaiBrah
Former Senior Instructor, Manhattan GMAT and VeritasPrep
Vice President, Midtown NYC Investment Bank, Structured Finance IT
MFE, Haas School of Business, UC Berkeley, Class of 2005
MBA, Anderson School of Management, UCLA, Class of 1993
|
|
|
|
|
|
Intern
Joined: 27 Jul 2003
Posts: 13
Followers: 0
Kudos [?]:
0
[0], given: 0
|
(1)
x^n - y^n is always divisible by x-y.
Hence 7^7 - 1^7 is divisible by 7-1 = 6 
Bharathi.
|
|
|
|
|
|
Manager
Joined: 26 Aug 2003
Posts: 238
Location: United States
Followers: 1
Kudos [?]:
1
[0], given: 0
|
Agree on D.
bhars18 wrote: (1) x^n - y^n is always divisible by x-y. Hence 7^7 - 1^7 is divisible by 7-1 = 6 Bharathi. Good proof/method!
|
|
|
|
|
|
GMAT Instructor
Joined: 07 Jul 2003
Posts: 773
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 5
Kudos [?]:
9
[0], given: 0
|
wonder_gmat wrote: Agree on D. bhars18 wrote: (1) x^n - y^n is always divisible by x-y. Hence 7^7 - 1^7 is divisible by 7-1 = 6 Bharathi. Good proof/method! Hmm. Is this something that a GMAT candidate is expected to know? Can you derive this using elementary math?
_________________
Best,
AkamaiBrah
Former Senior Instructor, Manhattan GMAT and VeritasPrep
Vice President, Midtown NYC Investment Bank, Structured Finance IT
MFE, Haas School of Business, UC Berkeley, Class of 2005
MBA, Anderson School of Management, UCLA, Class of 1993
|
|
|
|
|
|
VP
Joined: 13 Nov 2003
Posts: 1031
Location: Florida
Followers: 1
Kudos [?]:
5
[0], given: 0
|
proof:
step 1.
n=1
x^n - y^n = (x-y)
step 2.
n=k
x^k-y^k = (x-y) * constant .........eq 1.
step 3.
n=k+1
x^(k+1) - y^(k+1) = x^(k+1) - y^(k+1) + xy^k - xy^k
=x(x^k-y^k) + y^k(x-y)
=x(x-y)*constant + y^k(x-y) ........from eq 1.
=(x-y)(x*constant+y^k)
=(x-y)*constant
|
|
|
|
|
|
CEO
Joined: 15 Aug 2003
Posts: 3550
Followers: 55
Kudos [?]:
626
[0], given: 781
|
dj wrote: proof: step 1. n=1 x^n - y^n = (x-y) step 2. n=k x^k-y^k = (x-y) * constant .........eq 1. step 3. n=k+1 x^(k+1) - y^(k+1) = x^(k+1) - y^(k+1) + xy^k - xy^k =x(x^k-y^k) + y^k(x-y) =x(x-y)*constant + y^k(x-y) ........from eq 1. =(x-y)(x*constant+y^k) =(x-y)*constant is that constant ALWAYS an integer??
|
|
|
|
|
|
GMAT Instructor
Joined: 07 Jul 2003
Posts: 773
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 5
Kudos [?]:
9
[0], given: 0
|
dj wrote: proof: step 1. n=1 x^n - y^n = (x-y) step 2. n=k x^k-y^k = (x-y) * constant .........eq 1. step 3. n=k+1 x^(k+1) - y^(k+1) = x^(k+1) - y^(k+1) + xy^k - xy^k =x(x^k-y^k) + y^k(x-y) =x(x-y)*constant + y^k(x-y) ........from eq 1. =(x-y)(x*constant+y^k) =(x-y)*constant Sorry. I don't see how you conclude step 2 from step 1. In fact, step 2 simply states what you are trying to prove.
_________________
Best,
AkamaiBrah
Former Senior Instructor, Manhattan GMAT and VeritasPrep
Vice President, Midtown NYC Investment Bank, Structured Finance IT
MFE, Haas School of Business, UC Berkeley, Class of 2005
MBA, Anderson School of Management, UCLA, Class of 1993
|
|
|
|
|
|
VP
Joined: 13 Nov 2003
Posts: 1031
Location: Florida
Followers: 1
Kudos [?]:
5
[0], given: 0
|
yes, step 3 is just the extrapolation of step 2. you can derive step 2 from step 1, as x^n - y^n = (x-y)*1 for n=1, x^k - y^k will follow the same pattern.
proof:
step 1.
n=1
x^n - y^n = (x-y)
step 2.
n=k
x^k-y^k = (x-y) * some interger .........eq 1. relate this with step 1.
step 3. .... extrapolates step 2.
n=k+1
x^(k+1) - y^(k+1) = x^(k+1) - y^(k+1) + xy^k - xy^k
=x(x^k-y^k) + y^k(x-y)
=x(x-y)*constant + y^k(x-y) ........from eq 1.
=(x-y)(x*constant+y^k)
=(x-y)*constant
|
|
|
|
|
|
Director
Joined: 05 May 2003
Posts: 560
Location: Aus
Followers: 2
Kudos [?]:
3
[0], given: 0
|
Can we not just apply few numbers from 1,2,3 for N and check for the result ?
|
|
|
|
|
|
VP
Joined: 13 Nov 2003
Posts: 1031
Location: Florida
Followers: 1
Kudos [?]:
5
[0], given: 0
|
yes, the best way is to put in the integers and come onto the result. I was just trying to prove it using basic maths... 
|
|
|
|
|
|
GMAT Instructor
Joined: 07 Jul 2003
Posts: 773
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 5
Kudos [?]:
9
[0], given: 0
|
dj wrote: yes, the best way is to put in the integers and come onto the result. I was just trying to prove it using basic maths... Yes, you can use numbers, but this does not prove that it is true for ALL n.
For example, it is not obvious to me why x^4132 - y^4132 MUST have (x-y) as one of its factors.
I'm sorry. It is not obvious to me why x^k - y^k = (x-y) * some number. In addition, step 3 says nothing different that step 2, but neither give me any rationale of why it is true. Your attempt at an inductive proof is incomplete - you must show 1) GIVEN x^k - y^k is divisible by x-y then IT FOLLOWS that x^(k+1) - y^(k+1) is also divisible by x-y. 2); it works for k = 1. Number 2 is fine, but number 1 doesn't work for me.
The explanation of why this is so is the essense of your "proof" and IMO you have simply hand-waved it by.
_________________
Best,
AkamaiBrah
Former Senior Instructor, Manhattan GMAT and VeritasPrep
Vice President, Midtown NYC Investment Bank, Structured Finance IT
MFE, Haas School of Business, UC Berkeley, Class of 2005
MBA, Anderson School of Management, UCLA, Class of 1993
|
|
|
|
|
|
VP
Joined: 13 Nov 2003
Posts: 1031
Location: Florida
Followers: 1
Kudos [?]:
5
[0], given: 0
|
when x and y are integers, (x+y) will be an integer.
for all the values of n, the result will be (x-y) * an integer.
n=2, (x-y)*(x+y)...this is an integer
n=3, (x-y)*(x^2+y^2+xy)...this is an integer
n=4, (x-y)(x+y)(x^2+y^2)....these 2 are integers
....
this leads to (x^n - y^n)/(x-y) = an integer.
think, this suffice.
|
|
|
|
|
|
SVP
Joined: 03 Feb 2003
Posts: 1683
Followers: 4
Kudos [?]:
16
[0], given: 0
|
my initial idea:
(2) is obvious
(1) Q=[7^N]–1, where N is a positive integer
Q=[7^N]–[1^N], a distribution will always contain member [7–1], or 6.
|
|
|
|
|
|
GMAT Instructor
Joined: 07 Jul 2003
Posts: 773
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 5
Kudos [?]:
9
[0], given: 0
|
dj wrote: when x and y are integers, (x+y) will be an integer.
for all the values of n, the result will be (x-y) * an integer.
n=2, (x-y)*(x+y)...this is an integer
n=3, (x-y)*(x^2+y^2+xy)...this is an integer
n=4, (x-y)(x+y)(x^2+y^2)....these 2 are integers
....
this leads to (x^n - y^n)/(x-y) = an integer.
think, this suffice.
All you have done is demonstrate that it works for the first 4 terms. While this certainly suggests the result, it is definitely not PROOF.
_________________
Best,
AkamaiBrah
Former Senior Instructor, Manhattan GMAT and VeritasPrep
Vice President, Midtown NYC Investment Bank, Structured Finance IT
MFE, Haas School of Business, UC Berkeley, Class of 2005
MBA, Anderson School of Management, UCLA, Class of 1993
Last edited by AkamaiBrah on 01 Dec 2003, 03:45, edited 1 time in total.
|
|
|
|
|
|
GMAT Instructor
Joined: 07 Jul 2003
Posts: 773
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 5
Kudos [?]:
9
[0], given: 0
|
stolyar wrote: my initial idea:
(2) is obvious
(1) Q=[7^N]тАУ1, where N is a positive integer
Q=[7^N]тАУ[1^N], a distribution will always contain member [7тАУ1], or 6.
This certainly seems to be true but can you PROVE it for ALL n via a simple proof?
I.e.;Given Q = x^n - 1, prove that for ALL positive integers n, Q is a multiple of x-1
stolyar, i have faith in you.... 
_________________
Best,
AkamaiBrah
Former Senior Instructor, Manhattan GMAT and VeritasPrep
Vice President, Midtown NYC Investment Bank, Structured Finance IT
MFE, Haas School of Business, UC Berkeley, Class of 2005
MBA, Anderson School of Management, UCLA, Class of 1993
|
|
|
|
|
|
Manager
Joined: 25 Jan 2004
Posts: 95
Location: China
Followers: 1
Kudos [?]:
2
[0], given: 0
|
dj wrote: when x and y are integers, (x+y) will be an integer.
for all the values of n, the result will be (x-y) * an integer.
n=2, (x-y)*(x+y)...this is an integer
n=3, (x-y)*(x^2+y^2+xy)...this is an integer
n=4, (x-y)(x+y)(x^2+y^2)....these 2 are integers
....
this leads to (x^n - y^n)/(x-y) = an integer.
think, this suffice.
Relate the n-th step to (n+1)th. That is the trick of Mathematical Induction.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Similar topics |
Author |
Replies |
Last post |
|
Similar
Topics:
|
 |
|
|
If n and k are positive integers, is n divisible by 6? (1) n
|
nocilis |
5 |
02 Feb 2005, 22:37 |
|
|
|
|
If n and k are positive integers, is n divisible by 6? (1) n
|
TOUGH GUY |
7 |
12 May 2006, 11:54 |
|
|
|
|
If N is a positive integer, is 10^n - 1 divisible by q? 1. Q
|
bmwhype2 |
2 |
21 Nov 2007, 03:04 |
 |
|
|
If n and k are positive integers, is n divisible by 6? (1) n
|
kapilnegi |
15 |
29 May 2008, 13:31 |
|
|
|
|
If n is a positive integer, is (10^n)-1 divisible by Q ?
|
bblast |
2 |
17 Jun 2011, 23:27 |
|
|
|
|
|
|
close
