NEW HERE? LEARN MORE
closeclose
Last visit was: 27 Apr 2024, 06:21 It is currently 27 Apr 2024, 06:21
Decision Tracker
My Rewards
New posts
New comers' posts

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.
Go to My Error Log Learn more
Close
Request Expert Reply
Confirm Cancel

prime number

SORT BY:
Date
Kudos
User avatar
B
arbre
Intern
Intern
Joined: 19 Aug 2021
Posts: 44
Own Kudos [?]: 0 [0]
Given Kudos: 3
Send PM
prime number [#permalink] New post   07 Jun 2022, 23:36
Hi,
If a number less than 100 is not divisible by any prime divisor less than 10, then the number has to be prime. And, of course, the only prime divisors less than 10 are 2, 3, 5, and 7. So those are the only divisors we have to check. It's not divisible by any of those numbers, it is a prime number. So for example, here's a practice problem.

Then what about those bigger than 100, and why?

Thanks a lot in advance
User avatar
L
EMPOWERgmatRichC
GMAT Club Legend
GMAT Club Legend
Joined: 19 Dec 2014
Status:GMAT Assassin/Co-Founder
Affiliations: EMPOWERgmat
Posts: 21846
Own Kudos [?]: 11669 [0]
Given Kudos: 450
Location: United States (CA)
GMAT 1: 800 Q51 V49
GRE 1: Q170 V170
Send PM
Re: prime number [#permalink] New post   08 Jun 2022, 15:24
Expert Reply
arbre wrote:
Hi,
If a number less than 100 is not divisible by any prime divisor less than 10, then the number has to be prime. And, of course, the only prime divisors less than 10 are 2, 3, 5, and 7. So those are the only divisors we have to check. It's not divisible by any of those numbers, it is a prime number. So for example, here's a practice problem.

Then what about those bigger than 100, and why?

Thanks a lot in advance


Hi arbre,

When multiplying two positive integers together to get a larger, third number, there are a number of relationships that will exist. If the two numbers are EQUAL, then you have a 'perfect square' - for example (10)(10) = 100. In all other cases though, with that same result (in this case, 100), ONE of the two starting numbers will be LESS than 10 and ONE will be GREATER than 10 (for example (5)(20) or (4)(25)).

The pattern that you're asking about is in regards to Prime Factorization (re: the idea that every positive integer greater than 1 is either a Prime number or the product of some Primes). Since 10^2 = 100, with any number LESS than 100, if we're looking to see whether the number is Prime or not, we'll only need to divide by 2, 3, 5 and/or 7 - since the next prime is 11 and 11^2 = 121 (which is too big - and if 11 is one of the Prime Factors in the number, then we'll find it by dividing by one of the smaller primes).

For any number that is GREATER than 100, we may need to consider larger primes, but we can use perfect squares - along with this concept - to determine which, if any, additional calculations are required. For example, with 143 - and the knowledge that 11^2 = 121, we need to consider dividing by 11 (along with 2, 3, 5 and 7) to determine whether 143 is prime or not.

GMAT assassins aren't born, they're made,
Rich

Contact Rich at: Rich.C@empowergmat.com
User avatar
L
KarishmaB
Tutor
Joined: 16 Oct 2010
Posts: 14831
Own Kudos [?]: 64945 [0]
Given Kudos: 427
Location: Pune, India
Send PM
Re: prime number [#permalink] New post   08 Jun 2022, 22:53
Expert Reply
arbre wrote:
Hi,
If a number less than 100 is not divisible by any prime divisor less than 10, then the number has to be prime. And, of course, the only prime divisors less than 10 are 2, 3, 5, and 7. So those are the only divisors we have to check. It's not divisible by any of those numbers, it is a prime number. So for example, here's a practice problem.

Then what about those bigger than 100, and why?

Thanks a lot in advance


To understand this concept, check out these two blog posts:

https://anglesandarguments.com/blog-details/23
https://anglesandarguments.com/blog-details/31
User avatar
L
ScottTargetTestPrep
Target Test Prep Representative
Joined: 14 Oct 2015
Status:Founder & CEO
Affiliations: Target Test Prep
Posts: 18767
Own Kudos [?]: 22069 [0]
Given Kudos: 283
Location: United States (CA)
Send PM
Re: prime number [#permalink] New post   01 Aug 2022, 19:23
Expert Reply
arbre wrote:
Hi,
If a number less than 100 is not divisible by any prime divisor less than 10, then the number has to be prime. And, of course, the only prime divisors less than 10 are 2, 3, 5, and 7. So those are the only divisors we have to check. It's not divisible by any of those numbers, it is a prime number. So for example, here's a practice problem.

Then what about those bigger than 100, and why?

Thanks a lot in advance


Let's say the number is 101. The square root of 101 is roughly 10, so again we only need to check prime numbers less than 10. You can verify that 101 is not divisible by 2, 3, 5, and 7. Had 101 not been prime, it would have at least two prime factors. Since we know it is not divisible by 2, 3, 5, or 7, the smallest possible prime decomposition of 101 would be 11 * 11, which is already greater than 101. We know 101 cannot have a prime factor greater than 11 because that assumption would lead to a product which is even greater than 11 * 11. Similarly, 101 cannot have more than two prime factors, again we would have a product which is greater than 11 * 11. We see that the smallest possible prime decomposition of 101 is greater than 101, which means that 101 itself must be a prime number.

In general, if you know that x is not divisible by primes that are less than √x, then x itself must be prime. You can use the above reasoning to see this. If x were not prime, then it would have at least two prime factors and both of those factors would be greater than √x. Since the product of two numbers greater than √x is greater than x, x cannot have two prime factors, which means that x must be a prime number.
GMAT Club Bot
gmatclubot
Re: prime number [#permalink]
01 Aug 2022, 19:23

Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne
Main navigation
GMAT Resources
Partners
MBA Resources
www.gmac.com|www.mba.com | | GMAT Club Rules | Terms and Conditions