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

It is currently 24 Oct 2014, 19:41

Close

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
Your Progress

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

Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.

Events & Promotions

Events & Promotions in June
Open Detailed Calendar

For every positive even integer n, the function h(n) is

  Question banks Downloads My Bookmarks Reviews Important topics  
Author Message
TAGS:
Senior Manager
Senior Manager
User avatar
Joined: 16 Jan 2009
Posts: 362
Concentration: Technology, Marketing
GMAT 1: 700 Q50 V34
GPA: 3
WE: Sales (Telecommunications)
Followers: 2

Kudos [?]: 73 [0], given: 16

Re: Smallest Prime Factor [#permalink] New post 17 Mar 2009, 13:37
nitindas wrote:
This is a question from GmatPrep and answer is
5. greater than 40

The smallest prime factor cannot be 3 bcoz lets say:
we have to find smallest prime factor of 2*4*6 +1

This comes out to be 49

whereas 2 is the smallest prime factor of 2*4*6

but 2+1 =3 is not the factor of 49.

Can somebody explain how to find the smallest prime factor in such a case?


If you would have considered the actual example , you would have reched the answer.
Please see my response below.
_________________

Lahoosaher

Kaplan GMAT Prep Discount CodesKnewton GMAT Discount CodesGMAT Pill GMAT Discount Codes
1 KUDOS received
Senior Manager
Senior Manager
User avatar
Joined: 16 Jan 2009
Posts: 362
Concentration: Technology, Marketing
GMAT 1: 700 Q50 V34
GPA: 3
WE: Sales (Telecommunications)
Followers: 2

Kudos [?]: 73 [1] , given: 16

Re: Smallest Prime Factor [#permalink] New post 17 Mar 2009, 13:52
1
This post received
KUDOS
Our aim is to find the smallest prime factor in (2*4*6*8*10*........100)+1.
(2*4*6*8*10*........100)+1
=[2(1) * 2(2) *2(3)......2(50)]+1
=[2^50 * 50!]+1

Now , Take a simpler example....

5! is divisible by prime numbers less than or equal to 5 (2,3,5)

You can see that 5!+1 is not divisible by prime numbers less than or equal to 5 (2,3,5) [5!+1 = 121 is divisible by the prime number 11]

Take another example, 6!.

6! is divisible by prime numbers less than or equal to 6 (2,3,5)

In the same way , in above example , 50! will be devisible be prime numbers smaller than 50 ; however 50!+1 will not be.
So answer is
5. greater than 40.
_________________

Lahoosaher

Manager
Manager
avatar
Joined: 27 May 2008
Posts: 204
Followers: 1

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

Re: Smallest Prime Factor [#permalink] New post 18 Mar 2009, 01:52
Manager
Manager
User avatar
Joined: 14 Nov 2008
Posts: 200
Schools: Stanford...Wait, I will come!!!
Followers: 3

Kudos [?]: 34 [0], given: 3

Re: Smallest Prime Factor [#permalink] New post 13 Apr 2009, 03:24
Too good.
But is there any way that we can actually find the prime number?

amolsk11 wrote:
Our aim is to find the smallest prime factor in (2*4*6*8*10*........100)+1.
(2*4*6*8*10*........100)+1
=[2(1) * 2(2) *2(3)......2(50)]+1
=[2^50 * 50!]+1

Now , Take a simpler example....

5! is divisible by prime numbers less than or equal to 5 (2,3,5)

You can see that 5!+1 is not divisible by prime numbers less than or equal to 5 (2,3,5) [5!+1 = 121 is divisible by the prime number 11]

Take another example, 6!.

6! is divisible by prime numbers less than or equal to 6 (2,3,5)

In the same way , in above example , 50! will be devisible be prime numbers smaller than 50 ; however 50!+1 will not be.
So answer is
5. greater than 40.
1 KUDOS received
GMAT Club team member
avatar
Joined: 16 Mar 2009
Posts: 115
Location: Bologna, Italy
Followers: 40

Kudos [?]: 458 [1] , given: 19

Re: Smallest Prime Factor [#permalink] New post 13 Apr 2009, 10:31
1
This post received
KUDOS
lgon wrote:
Too good.
But is there any way that we can actually find the prime number?

As it's said, all we need to know is that this number is going to be grater than 50. )))
But, yeah, do the prime factorisation for 2^50*50! + 1 = 34243224702511976248246432895208185975118675053719198827915654463488000000000001, :lol:
I have no idea how to find it mathematically though, (if there is such a way at all) other than dividing that number by primes starting with 53 and looking if there is a remainder.
By the way the smallest prime factor is 79 in this case. I wrote simple program in LISP to find it )), took me under 2 min's. Why can't I bring my lappie to the test?
_________________

My Recent Posts:
All GMAT CAT Practice Tests - links, prices, reviews
Master thread - GMAT Prep classes links to reviews and ratings
Review: GMATPrep (GMAT Prep) & PowerPrep (Power Prep) Tests

Have trouble finding answers on this site? Ask me!

GMAT Instructor
avatar
Joined: 24 Jun 2008
Posts: 978
Location: Toronto
Followers: 261

Kudos [?]: 710 [0], given: 3

Re: Smallest Prime Factor [#permalink] New post 13 Apr 2009, 14:57
lgon wrote:
Too good.
But is there any way that we can actually find the prime number?


No, not without computer assistance. In general, if a very large number only has large prime factors, it can take eons to factorize it, even with a computer. This fact is actually the basis of all internet cryptography - internet encryption can be broken, but it would take too much computing time to do it in any reasonable amount of time. So while relatively few people are aware of the fact, prime number theory is the reason you can do banking or shopping on the internet, or send private emails. Without it, the internet would be a very different thing.
_________________

Nov 2011: After years of development, I am now making my advanced Quant books and high-level problem sets available for sale. Contact me at ianstewartgmat at gmail.com for details.

Private GMAT Tutor based in Toronto

Manager
Manager
avatar
Joined: 28 Jun 2008
Posts: 50
Followers: 0

Kudos [?]: 10 [0], given: 31

question from practice exam [#permalink] New post 27 May 2009, 11:13
Hi guys I was wonderig if anyone could offer some suggestions on how to solve this problem:

For every positive integer n, the function h(n) is defined by the roduct of all even integers from 2 to N inclusve. If p is the smallest prime factor of h(100)+1, then p is

a. between 2 and 10
b. between 10 and 20
c. between 20 and 30
d. between 30 and 40
e. greater than 40


[Reveal] Spoiler: Official Answer
answer: e.
1 KUDOS received
Manager
Manager
avatar
Affiliations: Beta Gamma Sigma
Joined: 14 Aug 2008
Posts: 211
Schools: Harvard, Penn, Maryland
Followers: 4

Kudos [?]: 27 [1] , given: 3

Re: question from practice exam [#permalink] New post 27 May 2009, 12:48
1
This post received
KUDOS
should be E.

the equation works out to be h(n) = n(n-2)(n-4)(n-6)(n-8)....(n-(n-2))

so h(100) = 100*98*96*94*92.....4*2

which is a gigantic even number, with the smallest prime factor of 2

however, when you add one, it becomes prime itself (or safe to assume so), so the smallest prime factor could be insinuated to be itself, or a gigantic random number way over 40.
1 KUDOS received
Intern
Intern
User avatar
Joined: 16 May 2009
Posts: 3
Followers: 0

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

Re: question from practice exam [#permalink] New post 29 May 2009, 11:56
1
This post received
KUDOS
scorpio7 wrote:
Hi guys I was wonderig if anyone could offer some suggestions on how to solve this problem:

For every positive integer n, the function h(n) is defined by the roduct of all even integers from 2 to N inclusve. If p is the smallest prime factor of h(100)+1, then p is

a. between 2 and 10
b. between 10 and 20
c. between 20 and 30
d. between 30 and 40
e. greater than 40


[Reveal] Spoiler: Official Answer
answer: e.


This question is testing the concept of coprimes.
2 positive integers are coprime when their greatest common factor (their only common factor) is 1.
Now note that two different prime numbers are always coprime.
For example, 3 and 7 are coprime. So are 13 and 19.
But the two integers need not be prime numbers in order to be coprime.
For example, 4 and 9 are coprime (1 is their only common factor).
Also, Important!
Two consecutive integers are always coprime. The question is testing you on this concept.
Let's solve it now:
h(n) = 2*4*6*....................*n. ----n is even.
h(100) = 2*4*6*........ 94*96*98*100.
h(100) = (2^50)*(1*2*3*.......47*48*49*50). Note:I have pooled together all the 2s from all the even integers from 2 to 100; that's how I got 2^50. Now, the largest prime number involved in the above factorization is 47. All the prime from 2 to 47 are also involved in the above factorization. Actually, 47 is the greatest prime factor of h(100).
Since h(100) and h(100) + 1 are consecutive integers, they are necessarily coprime (see above). h(100) and h(100) + 1 have no common factor except 1, so they have no common prime factor either. The smallest prime factor of h(100) +1 must then be greater than 47.
Clearly, this prime factor is greater than 40.

By the way, you cannot assume that h(100) + 1 is a prime number. Just use the concept of coprimes.

That said, this is a previous post of mine in this forum. I was then TheGMATDoctor. You can check out my posts by doing a search.
---------------------------------------
This was today's GMAT math recipe from the GMAT Chef.
_________________

Dakar Azu is The GMAT Chef. He has sweet recipes for virtually every type of GMAT question, be it quantitative or verbal. Dakar has been teaching the GMAT since 2003 and is the founder of 700-GMAT Club at http://700gmatclub.com and GMAT lounge Social at http://gmatlounge.net .

CEO
CEO
User avatar
Joined: 29 Mar 2007
Posts: 2593
Followers: 16

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

Re: Smallest Prime Factor [#permalink] New post 09 Jul 2009, 14:27
selvae wrote:
http://gmat-maths.net84.net/forum/topic.php?id=39&replies=2#post-45


His analysis is not correct. H(100) =/ 2*50!... this is implying that 2*4*6 = 2(1*2*3) which is obviously not true.

Needs to be 2^50*50!.


E is the answer though. I get it by testing out numbers. But this is by no means full-proof.
Intern
Intern
avatar
Joined: 23 Jun 2009
Posts: 47
Followers: 0

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

Tough GMAT question. Please help...! THANKS! [#permalink] New post 21 Jul 2009, 19:09
For every positive integer n, the function h(n) is defined to be the product of all the even integers from 2 to n, inclusive. If p is the smallest prime factor of h(100)+1, then p is...
A) between 2 and 10
B) between 10 and 20
C) between 20 and 30
D) between 30 and 40
E) greater then 40


I would really appreciate a response to this question. I feel like I am missing a fundamental principle/trick. This question has been bugging me for about a week.
Manager
Manager
User avatar
Joined: 27 Jun 2008
Posts: 160
Followers: 2

Kudos [?]: 19 [0], given: 11

Re: Tough GMAT question. Please help...! THANKS! [#permalink] New post 21 Jul 2009, 23:39
I could reduce it to 2^50X50!+1 but cant reduce further, clues anyone...
1 KUDOS received
Senior Manager
Senior Manager
avatar
Joined: 23 Jun 2009
Posts: 359
Location: Turkey
Schools: UPenn, UMich, HKS, UCB, Chicago
Followers: 5

Kudos [?]: 95 [1] , given: 60

Re: Tough GMAT question. Please help...! THANKS! [#permalink] New post 22 Jul 2009, 00:00
1
This post received
KUDOS
h(100) = 100x99x98....3x2
h(100)+1= 100x99x98....3x2 + 1
So it can not be divided by any number b/w 2 and 100.
e.g. it can not be divided by 91 because h(100)= y.91 (y is the multiplication of other numbers b/w 2 and 100)
so h(100)+1=y.91 + 1 so this number is equal to 1 in (mod 99). For any number b/w 2 and 100 this holds.
So the greatest prime number will be h(100)+1 or a number that is b/w 100 and h(100)+1. Both are greater than 40

E ;)
Senior Manager
Senior Manager
avatar
Joined: 23 Jun 2009
Posts: 359
Location: Turkey
Schools: UPenn, UMich, HKS, UCB, Chicago
Followers: 5

Kudos [?]: 95 [0], given: 60

Re: Tough GMAT question. Please help...! THANKS! [#permalink] New post 22 Jul 2009, 00:03
Quote:
I could reduce it to 2^50X50!+1 but cant reduce further, clues anyone...
How can you did it? For example is 2^50x50! divisible by 93 or 97? But h(100) is divisible by both 93 and 97 ;)
Manager
Manager
User avatar
Joined: 27 Jun 2008
Posts: 160
Followers: 2

Kudos [?]: 19 [0], given: 11

Re: Tough GMAT question. Please help...! THANKS! [#permalink] New post 22 Jul 2009, 00:30
Thanks maliyeci, I see what you are saying, Ignore 2^50X50!+1 I just tried to reduce the factorial thinking it will lead somewhere.
Current Student
avatar
Affiliations: ?
Joined: 20 Jul 2009
Posts: 191
Location: Africa/Europe
Schools: Kellogg; Ross ($$); Tuck
Followers: 2

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

Re: Tough GMAT question. Please help...! THANKS! [#permalink] New post 22 Jul 2009, 04:37
Quote:
h(100) = 100x99x98....3x2
h(100)+1= 100x99x98....3x2 + 1


Shouldn't we have h(100) = 100x98x96x94x.....x6x4x2 ?

Function h is said to be the product of even integers from 2 to n.
3 KUDOS received
Current Student
avatar
Affiliations: ?
Joined: 20 Jul 2009
Posts: 191
Location: Africa/Europe
Schools: Kellogg; Ross ($$); Tuck
Followers: 2

Kudos [?]: 29 [3] , given: 6

Re: Tough GMAT question. Please help...! THANKS! [#permalink] New post 22 Jul 2009, 04:54
3
This post received
KUDOS
Here is my way of doing it:

h(100) and h(100)+1 are relatively prime, so they cannot have a prime factor in common other than 1.

(for any integer n, n and n+1 are relatively prime)

so we have h(100)= 100x98x.....x4x2 = 2(1x2x3x4x.....x49x50)
so we know that any number from 1 to 50 is a factor of h(100) and therefore cannot be a factor of h(100)+1. the smallest factor of h(100)+1 will be greater than 50.

so answer E
Senior Manager
Senior Manager
avatar
Joined: 23 Jun 2009
Posts: 359
Location: Turkey
Schools: UPenn, UMich, HKS, UCB, Chicago
Followers: 5

Kudos [?]: 95 [0], given: 60

Re: Tough GMAT question. Please help...! THANKS! [#permalink] New post 22 Jul 2009, 05:13
Sorry. I did not see "EVEN". But that does not change the solution.
Quote:
h(100)+1 are relatively prime

Not necessarily. For example, h(7) = 2 x 4 x 6 = 48 (not prime), h(7) + 1 = 49 (not prime)
Current Student
avatar
Affiliations: ?
Joined: 20 Jul 2009
Posts: 191
Location: Africa/Europe
Schools: Kellogg; Ross ($$); Tuck
Followers: 2

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

Re: Tough GMAT question. Please help...! THANKS! [#permalink] New post 22 Jul 2009, 05:37
maliyeci wrote:
Sorry. I did not see "EVEN". But that does not change the solution.
Quote:
h(100)+1 are relatively prime

Not necessarily. For example, h(7) = 2 x 4 x 6 = 48 (not prime), h(7) + 1 = 49 (not prime)


I was talking about "relatively prime numbers" (or coprime) not "prime numbers"
this is the definition "Two integers are relatively prime if they share no common positive factors (divisors) except 1"
so 48 and 49 are relatively prime.

check on wiki for more info. clearly I don't know if we can do this question w/o the notion of coprime.
Senior Manager
Senior Manager
avatar
Joined: 23 Jun 2009
Posts: 359
Location: Turkey
Schools: UPenn, UMich, HKS, UCB, Chicago
Followers: 5

Kudos [?]: 95 [0], given: 60

Re: Tough GMAT question. Please help...! THANKS! [#permalink] New post 22 Jul 2009, 05:44
Sorry. I do not know about relatively primes or coprimes. But my solution works for it and does not need coprimes.
Re: Tough GMAT question. Please help...! THANKS!   [#permalink] 22 Jul 2009, 05:44
    Similar topics Author Replies Last post
Similar
Topics:
For every positive even integer n, the function h(n) is defi Game 0 22 Jun 2014, 08:35
3 Experts publish their posts in the topic For every positive even integer n, the function h(n) is topmbaseeker 13 09 Feb 2008, 14:21
7 1) For every positive even integer n, function h(n) is g1m2a3t406 6 24 Nov 2006, 13:25
For every positive even integer, n, the function h(n) is ffgmat 1 22 May 2006, 03:56
For every positive even integer n, the function hn) is john2005 5 07 May 2006, 13:17
Display posts from previous: Sort by

For every positive even integer n, the function h(n) is

  Question banks Downloads My Bookmarks Reviews Important topics  

Go to page   Previous    1  ...  3   4   5   6   7   8   9   10   11   12  ...  14    Next  [ 273 posts ] 



cron

GMAT Club MBA Forum Home| About| Privacy Policy| Terms and Conditions| GMAT Club Rules| Contact| Sitemap

Powered by phpBB © phpBB Group and phpBB SEO

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®.