Coprimes below 'n' : GMAT Problem Solving (PS)

Coprimes below 'n'

Oldest

Best Reply

Author

Message

TAGS:

Intern

Joined: 11 Aug 2009

Posts: 8

Followers: 0

Kudos [?]: 1 [0], given: 6

Coprimes below 'n' [#permalink]

11 Aug 2009, 12:53

00:00

Question Stats:

50% (04:23) correct

50% (01:43) wrong

based on 0 sessions

Q) How many numbers exist below 2100 such that the only common factor between that number and 2100 is 1?
a) 480
b) 343
c) 326
d) 540
e) 700

The OA is given as

[Reveal] Spoiler:

Please explain how to proceed on this one.

Manager

Joined: 25 Jul 2009

Posts: 119

Schools: NYU, NUS, ISB, DUKE, ROSS, DARDEN

Followers: 2

Kudos [?]: 103 [3] , given: 17

Re: Coprimes below 'n' [#permalink]

11 Aug 2009, 13:12

This post received
KUDOS

I guess you posted this query in the wrong thread!

Anyways, I dont think such a question will ever appear on the GMAT. This is a direct application of Euler-Totient Function (Refer http://2000clicks.com/MathHelp/NumberFa ... nction.htm)

To apply this function to the question posted, we will have to factorize 2100:
=> 2100 = 2^2 * 3 * 5^2 * 7
=> 2100 has 4 prime factors viz. 2,3,5 & 7

According to Euler-Totient Fn the number of numbers below 2100 that have 1 as the only common factor with 2100 are:
=> 2100 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5) * (1 - 1/7)
=> 2100 * 1/2 * 2/3 * 4/5 * 6/7
=> 480

ANS: A

PS: Where did you get this question?
_________________

KUDOS me if I deserve it !!

My GMAT Debrief - 740 (Q50, V39) | My Test-Taking Strategies for GMAT | Sameer's SC Notes

Intern

Joined: 11 Aug 2009

Posts: 8

Followers: 0

Kudos [?]: 1 [0], given: 6

Re: Coprimes below 'n' [#permalink]

11 Aug 2009, 13:22

Thats brilliant! Thanks!

How can you bew so sure that such a question will never appear on the GMAT?

Manager

Joined: 10 Jul 2009

Posts: 174

Followers: 1

Kudos [?]: 17 [0], given: 8

Re: Coprimes below 'n' [#permalink]

11 Aug 2009, 13:36

Good explanation!!!

Manager

Joined: 25 Jul 2009

Posts: 119

Schools: NYU, NUS, ISB, DUKE, ROSS, DARDEN

Followers: 2

Kudos [?]: 103 [0], given: 17

Re: Coprimes below 'n' [#permalink]

11 Aug 2009, 15:09

sergbov123 wrote:

Thats brilliant! Thanks!

How can you bew so sure that such a question will never appear on the GMAT?

Because there is no other way of solving this sum within 2 minutes and obviously GMAC does not expect the test taker to know about Euler-Totient Fn. I mean this isnt a Math Olympiad man!
_________________

KUDOS me if I deserve it !!

My GMAT Debrief - 740 (Q50, V39) | My Test-Taking Strategies for GMAT | Sameer's SC Notes

Re: Coprimes below 'n' [#permalink] 11 Aug 2009, 15:09

		Similar topics	Author	Replies	Last post
Similar Topics:		Done GMAT 3 times in 2004 n got below 500-Any advice?	sokoletu	8	08 Feb 2006, 15:01
		What is the value of m+n? Refer to the addition table below,	shehreenquayyum	1	02 Jul 2006, 12:18
	3	Coprimes below 'n'	sergbov123	4	11 Aug 2009, 12:53
	2	n	GMATD11	9	28 Feb 2011, 03:12
		Co-prime integer (high level question)	adgir	4	09 Jan 2012, 13:45

Coprimes below 'n'

Main navigation

GMAT Resources

Partners

MBA Resources

GMAT ® is a registered trademark of the Graduate Management Admission Council ® (GMAC ®). GMAT Club's website has not been reviewed or endorsed by GMAC.

GMAT Courses

Admissions Consulting

Coprimes below 'n'

Coprimes below 'n'

Main navigation

GMAT Resources

Partners

MBA Resources