Find all School-related info fast with the new School-Specific MBA Forum

 It is currently 04 May 2015, 15:15

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

# Is integer Q evenly divisible by 6? (1) Q= 1, where N is a

Author Message
TAGS:
SVP
Joined: 03 Feb 2003
Posts: 1608
Followers: 6

Kudos [?]: 76 [0], given: 0

Is integer Q evenly divisible by 6? (1) Q= 1, where N is a [#permalink]  07 Oct 2003, 09:45
00:00

Difficulty:

(N/A)

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: 233
Location: United States
Followers: 1

Kudos [?]: 2 [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: 1608
Followers: 6

Kudos [?]: 76 [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: 770
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 13

Kudos [?]: 52 [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: 11
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: 233
Location: United States
Followers: 1

Kudos [?]: 2 [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: 770
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 13

Kudos [?]: 52 [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

Director
Joined: 13 Nov 2003
Posts: 971
Location: Florida
Followers: 1

Kudos [?]: 32 [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: 3469
Followers: 61

Kudos [?]: 702 [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: 770
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 13

Kudos [?]: 52 [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

Director
Joined: 13 Nov 2003
Posts: 971
Location: Florida
Followers: 1

Kudos [?]: 32 [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
Senior Manager
Joined: 05 May 2003
Posts: 427
Location: Aus
Followers: 2

Kudos [?]: 5 [0], given: 0

Can we not just apply few numbers from 1,2,3 for N and check for the result ?
Director
Joined: 13 Nov 2003
Posts: 971
Location: Florida
Followers: 1

Kudos [?]: 32 [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: 770
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 13

Kudos [?]: 52 [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

Director
Joined: 13 Nov 2003
Posts: 971
Location: Florida
Followers: 1

Kudos [?]: 32 [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: 1608
Followers: 6

Kudos [?]: 76 [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: 770
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 13

Kudos [?]: 52 [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, 02:45, edited 1 time in total.
GMAT Instructor
Joined: 07 Jul 2003
Posts: 770
Location: New York NY 10024
Schools: Haas, MFE; Anderson, MBA; USC, MSEE
Followers: 13

Kudos [?]: 52 [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: 92
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 Replies Last post
Similar
Topics:
1 If n is a positive integer, is 10^n - 1 divisible by q? 4 17 Jun 2011, 22:27
If n and k are positive integers, is n divisible by 6? (1) n 15 29 May 2008, 12:31
If N is a positive integer, is 10^n - 1 divisible by q? 1. Q 2 21 Nov 2007, 02:04
If n and k are positive integers, is n divisible by 6? (1) n 5 01 Oct 2007, 05:47
If n and k are positive integers, is n divisible by 6? (1) n 7 12 May 2006, 10:54
Display posts from previous: Sort by