It is currently 20 Aug 2017, 06:38

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

# Math: Number Theory

Author Message
TAGS:

### Hide Tags

Math Expert
Joined: 02 Sep 2009
Posts: 40959

Kudos [?]: 118889 [0], given: 12010

### Show Tags

11 Feb 2015, 09:15
Lucky2783 wrote:
Bunuel

Finding the Number of Factors of an Integer

First make prime factorization of an integer n=a^p*b^q*c^r, where a, b, and c are prime factors of n and p, q, and r are their powers.

The number of factors of n will be expressed by the formula (p+1)(q+1)(r+1). NOTE: this will include 1 and n itself.

Example: Finding the number of all factors of 450: 450=2^1*3^2*5^2

Total number of factors of 450 including 1 and 450 itself is (1+1)*(2+1)*(2+1)=2*3*3=18 factors.

On GMAT do we count -ive factors as well , in which case the total factors will be 18*2 ?

No, for the GMAT we are only concerned about positive divisors/factors.
_________________

Kudos [?]: 118889 [0], given: 12010

Intern
Joined: 01 Feb 2015
Posts: 1

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

### Show Tags

14 Feb 2015, 23:10
First of all, great post! Thanks a ton for creating this resource.

I had a very quick question.

In some DS questions, I have come accross the term - "Range of n integers"

I first assumed, range would mean the number of terms.

I was able to get some of the questions correct, using this but I think I got very lucky. Primarily because when I use different methods to check and practice the question, it leads me to a different answer.

Any chance you can let me know if my assumption was correct? If so, any suggestions how best to tackle these questions in the least amount of time.

Many thanks!

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

Math Expert
Joined: 02 Sep 2009
Posts: 40959

Kudos [?]: 118889 [0], given: 12010

### Show Tags

16 Feb 2015, 03:25
ud19 wrote:
First of all, great post! Thanks a ton for creating this resource.

I had a very quick question.

In some DS questions, I have come accross the term - "Range of n integers"

I first assumed, range would mean the number of terms.

I was able to get some of the questions correct, using this but I think I got very lucky. Primarily because when I use different methods to check and practice the question, it leads me to a different answer.

Any chance you can let me know if my assumption was correct? If so, any suggestions how best to tackle these questions in the least amount of time.

Many thanks!

The range of a set is the difference between the largest and the smallest numbers of a set. For example, the range of {1, 10, 12} is 12 - 1 = 11 and the range of {-7, 0, 2, 9} is 9 - (-7) = 16.

DS Statistics and Sets problems to practice: search.php?search_id=tag&tag_id=34
PS Statistics and Sets problems to practice: search.php?search_id=tag&tag_id=55

Hope it helps.
_________________

Kudos [?]: 118889 [0], given: 12010

Manager
Joined: 16 Jan 2013
Posts: 90

Kudos [?]: 2 [0], given: 1117

GMAT 1: 490 Q41 V18
GPA: 2.75

### Show Tags

06 May 2015, 02:09
Can't express in words how much helpful this post is!!

Thanks a million.
_________________

Kudos [?]: 2 [0], given: 1117

GMAT Tutor
Joined: 24 Jun 2008
Posts: 1338

Kudos [?]: 1846 [2] , given: 6

### Show Tags

12 Jun 2015, 11:27
2
KUDOS
Expert's post
Bunuel wrote:

Verifying the primality (checking whether the number is a prime) of a given number $$n$$ can be done by trial division, that is to say dividing $$n$$ by all integer numbers smaller than $$\sqrt{n}$$, thereby checking whether $$n$$ is a multiple of $$m<\sqrt{n}$$.
Example: Verifying the primality of $$161$$: $$\sqrt{161}$$ is little less than $$13$$, from integers from $$2$$ to $$13$$, $$161$$ is divisible by $$7$$, hence $$161$$ is not prime.

A minor point, but the inequalities here should not be strict. If you want to test if some large integer n is prime, then you need to try dividing by numbers up to and including $$\sqrt{n}$$. We must include $$\sqrt{n}$$, in case our number is equal to the square of a prime.

And it might be worth mentioning that it is only necessary to try dividing by prime numbers up to $$\sqrt{n}$$, since if n has any divisors at all (besides 1 and n), then it must have a prime divisor.

It's very rare, though, that one needs to test if a number is prime on the GMAT. It is, computationally, extremely time-consuming to test if a large number is prime, so the GMAT cannot ask you to do that. If a GMAT question asks if a large number is prime, the answer really must be 'no', because while you can often quickly prove a large number is not prime (for example, 1,000,011 is not prime because it is divisible by 3, as we see by summing digits), you cannot quickly prove that a large number is prime.
_________________

GMAT Tutor in Toronto

If you are looking for online GMAT math tutoring, or if you are interested in buying my advanced Quant books and problem sets, please contact me at ianstewartgmat at gmail.com

Kudos [?]: 1846 [2] , given: 6

Math Expert
Joined: 02 Sep 2009
Posts: 40959

Kudos [?]: 118889 [0], given: 12010

### Show Tags

12 Jun 2015, 11:52
IanStewart wrote:
Bunuel wrote:

Verifying the primality (checking whether the number is a prime) of a given number $$n$$ can be done by trial division, that is to say dividing $$n$$ by all integer numbers smaller than $$\sqrt{n}$$, thereby checking whether $$n$$ is a multiple of $$m<\sqrt{n}$$.
Example: Verifying the primality of $$161$$: $$\sqrt{161}$$ is little less than $$13$$, from integers from $$2$$ to $$13$$, $$161$$ is divisible by $$7$$, hence $$161$$ is not prime.

A minor point, but the inequalities here should not be strict. If you want to test if some large integer n is prime, then you need to try dividing by numbers up to and including $$\sqrt{n}$$. We must include $$\sqrt{n}$$, in case our number is equal to the square of a prime.

And it might be worth mentioning that it is only necessary to try dividing by prime numbers up to $$\sqrt{n}$$, since if n has any divisors at all (besides 1 and n), then it must have a prime divisor.

It's very rare, though, that one needs to test if a number is prime on the GMAT. It is, computationally, extremely time-consuming to test if a large number is prime, so the GMAT cannot ask you to do that. If a GMAT question asks if a large number is prime, the answer really must be 'no', because while you can often quickly prove a large number is not prime (for example, 1,000,011 is not prime because it is divisible by 3, as we see by summing digits), you cannot quickly prove that a large number is prime.

Than you Ian. Edited the typo.
_________________

Kudos [?]: 118889 [0], given: 12010

Intern
Joined: 10 Mar 2014
Posts: 26

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

### Show Tags

02 Aug 2015, 23:16
Bunuel wrote:
defoue wrote:
Hi buddies,
going through this awesome contribution, I got some issues to understand the following : would you please help to understand by giving some extra examples?

1. Finding the power of non-prime in n!:

How many powers of 900 are in 50!

Make the prime factorization of the number: 900=2^2*3^2*5^2, then find the powers of these prime numbers in the n!.

Find the power of 2:
\frac{50}{2}+\frac{50}{4}+\frac{50}{8}+\frac{50}{16}+\frac{50}{32}=25+12+6+3+1=47

= 2^{47}

Find the power of 3:
\frac{50}{3}+\frac{50}{9}+\frac{50}{27}=16+5+1=22

=3^{22}

Find the power of 5:
\frac{50}{5}+\frac{50}{25}=10+2=12

=5^{12}

We need all the prime {2,3,5} to be represented twice in 900, 5 can provide us with only 6 pairs, thus there is 900 in the power of 6 in 50!.

2. I did not get the tips 3 or 4 regarding the pefect square whare it says a perfect square has an odd nbr of odd powers and an even nbr of even power
what aboute 36 which is 2^{2} x 3^{2}
I am sure I am missing something here..

Thx guys

Hi Bunuel, Firstly Thanks a ton for such an amazing resource.

I had a similar doubt ( like the one posted above) But i am not sure whether i still got the hang of it.
With reference to the example you provided in the theory - say instead of 900, if it were 2700 :
Then we could factorize 2700 to 2^2 * 3^3 * 5^2, then how would you proceed with answer. Would you consider that all these prime factors will have to occur thrice (because the highest exponent in the factorization was 3) ? I know that you have already given an example of 12 (where the powers weren't identical ) , but I still require a further understanding of concept

Thanks

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

Intern
Joined: 10 Mar 2014
Posts: 26

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

### Show Tags

02 Aug 2015, 23:38
Bunuel wrote:
defoue wrote:
Hi buddies,
going through this awesome contribution, I got some issues to understand the following : would you please help to understand by giving some extra examples?

1. Finding the power of non-prime in n!:

How many powers of 900 are in 50!

Make the prime factorization of the number: 900=2^2*3^2*5^2, then find the powers of these prime numbers in the n!.

Find the power of 2:
\frac{50}{2}+\frac{50}{4}+\frac{50}{8}+\frac{50}{16}+\frac{50}{32}=25+12+6+3+1=47

= 2^{47}

Find the power of 3:
\frac{50}{3}+\frac{50}{9}+\frac{50}{27}=16+5+1=22

=3^{22}

Find the power of 5:
\frac{50}{5}+\frac{50}{25}=10+2=12

=5^{12}

We need all the prime {2,3,5} to be represented twice in 900, 5 can provide us with only 6 pairs, thus there is 900 in the power of 6 in 50!.

2. I did not get the tips 3 or 4 regarding the pefect square whare it says a perfect square has an odd nbr of odd powers and an even nbr of even power
what aboute 36 which is 2^{2} x 3^{2}
I am sure I am missing something here..

Thx guys

1. It's highly unlikely that this concept will be tested in GMAT. But still:

Suppose we have the number $$18!$$ and we are asked to to determine the power of $$12$$ in this number. Which means to determine the highest value of $$x$$ in $$18!=12^x*a$$, where $$a$$ is the product of other multiples of $$18!$$.

$$12=2^2*3$$, so we should calculate how many 2-s and 3-s are in $$18!$$.

Calculating 2-s: $$\frac{18}{2}+\frac{18}{2^2}+\frac{18}{2^3}+\frac{18}{2^4}=9+4+2+1=16$$. So the power of $$2$$ (the highest power) in prime factorization of $$18!$$ is $$16$$.

Calculating 3-s: $$\frac{18}{3}+\frac{18}{3^2}=6+2=8$$. So the power of $$3$$ (the highest power) in prime factorization of $$18!$$ is $$8$$.

Now as $$12=2^2*3$$ we need twice as many 2-s as 3-s. $$18!=2^{16}*3^8*a=(2^2)^8*3^8*a=(2^2*3)^8*a=12^8*a$$. So $$18!=12^8*a$$ --> $$x=8$$.

2. A perfect square ALWAYS has an ODD number of Odd-factors, and EVEN number of Even-factors.
Let's take your example $$36$$. $$36=2^2*3^2$$, the number of factors of $$36$$ is $$(2+1)(2+1)=9$$: 1, 2, 3, 4, 6, 9, 12, 18, 36.

1, 3, 9 - THREE ODD factors - "ODD number of Odd-factors";
2, 4, 6, 12, 18, 36 - SIX EVEN factors - "EVEN number of Even-factors".

Perfect square always has even number of powers of prime factors

Lets take again $$36$$. $$36=6^2=2^2*3^2$$, the prime factors of $$36$$ are 2 and 3, their powers are 2 and 2, which are even.

OR $$144=12^2=2^4*3^2$$, here again the powers (4 and 2) are even.

Hope it's clear.

Hi bunuel !
Firstly thanks a ton for providing a great resource for quant!

Even though u have explained the concept of power of a no. in factorial, i am not sure whether i still got the hang of it.

Say instead of 900 if it were 2700, then we can factorize it to 2^2 * 3^3 * 5^2 ; Would you consider that the factors will occur thrice (since the greatest exponent is 3) or Am I missing something ?

I know you have given an example of 12 (where powers were not identical) but i am not sure whether i got the concept

Thanks.

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

Intern
Status: Current Student
Joined: 27 Mar 2014
Posts: 15

Kudos [?]: 13 [0], given: 9

### Show Tags

08 Aug 2015, 23:27
In Roots section you wrote:

$$\sqrt{x^2}$$=|x|, when x0, then, $$\sqrt{x^2}$$=-x and when x≥0, then $$\sqrt{x^2}$$=x.

Here, won't it be "when x<0, then $$\sqrt{x^2}$$=−x"?

Kudos [?]: 13 [0], given: 9

Math Expert
Joined: 02 Sep 2009
Posts: 40959

Kudos [?]: 118889 [0], given: 12010

### Show Tags

16 Aug 2015, 10:11
zmtalha wrote:
In Roots section you wrote:

$$\sqrt{x^2}$$=|x|, when x0, then, $$\sqrt{x^2}$$=-x and when x≥0, then $$\sqrt{x^2}$$=x.

Here, won't it be "when x<0, then $$\sqrt{x^2}$$=−x"?

No. For x = 0, we'd get $$\sqrt{0^2}=0=-0$$.
_________________

Kudos [?]: 118889 [0], given: 12010

Intern
Joined: 13 May 2015
Posts: 18

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

Concentration: Finance, General Management
GMAT 1: 330 Q17 V12
GPA: 3.39

### Show Tags

18 Aug 2015, 13:58
how do you get the 13 and the 11 in the question?
If the sum of two positive integers is 24 and the difference of their squares is 48, what is the product of the two integers?

x+y=24
and
x2−y2=48 --> (x+y)(x−y)=48, as x+y=24 --> 24(x−y)=48 --> x−y=2 --> solving for x and y --> x=13 and y=11 --> xy=143.

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

Math Expert
Joined: 02 Sep 2009
Posts: 40959

Kudos [?]: 118889 [0], given: 12010

### Show Tags

18 Aug 2015, 14:03
SQUINGEL wrote:
how do you get the 13 and the 11 in the question?
If the sum of two positive integers is 24 and the difference of their squares is 48, what is the product of the two integers?

x+y=24
and
x2−y2=48 --> (x+y)(x−y)=48, as x+y=24 --> 24(x−y)=48 --> x−y=2 --> solving for x and y --> x=13 and y=11 --> xy=143.

We have two equations:
x + y = 24;
x - y = 2.

Sum those two:
(x + y) + (x - y) = 24 + 2
2x = 26
x = 13

Substitute x = 13 into any of the equations:
13 - y = 2
y = 11.
_________________

Kudos [?]: 118889 [0], given: 12010

Intern
Joined: 29 Apr 2015
Posts: 23

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

GPA: 3.89

### Show Tags

23 Aug 2015, 21:40
I have a theory-related question regarding the definition of intersecting lines. If a line overlaps (colinear) a line segment (more than one point, of course) are they still considered to be "intersecting"? I was under the impression that this would not constitute an intersection however a question I worked seemed to suggest the opposite.

Example: line segment (1,5),(3,3) and line y=-x+6

The line overlaps the line segment; are they "intersecting"?

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

Math Expert
Joined: 02 Sep 2009
Posts: 40959

Kudos [?]: 118889 [0], given: 12010

### Show Tags

24 Aug 2015, 08:42
ar500 wrote:
I have a theory-related question regarding the definition of intersecting lines. If a line overlaps (colinear) a line segment (more than one point, of course) are they still considered to be "intersecting"? I was under the impression that this would not constitute an intersection however a question I worked seemed to suggest the opposite.

Example: line segment (1,5),(3,3) and line y=-x+6

The line overlaps the line segment; are they "intersecting"?

Technically intersect means share one or more points in common. So, if two lines overlap they do intersect.

Having said that, I must add that GMAT would never test you on such technicalities, you can ignore this question and move on.

Hope it helps.
_________________

Kudos [?]: 118889 [0], given: 12010

Intern
Joined: 08 Dec 2015
Posts: 29

Kudos [?]: 2 [0], given: 57

### Show Tags

10 Dec 2015, 15:17
Super helpful, I'll be referring to this early and often.

the sqrt(n) to verify prime numbers is a new concept for me and I would always miss the weird factors like 11, 13, 7, 17 etc.

Kudos [?]: 2 [0], given: 57

Intern
Joined: 03 Jan 2016
Posts: 3

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

### Show Tags

10 Jan 2016, 22:33
thank u very very much~!!!

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

Intern
Joined: 05 May 2016
Posts: 8

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

Location: India

### Show Tags

19 May 2016, 04:16
plzBunuel explain in simple language how to find Find The Last three digits of 2003^2002^2001?

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

Math Expert
Joined: 02 Sep 2009
Posts: 40959

Kudos [?]: 118889 [0], given: 12010

### Show Tags

19 May 2016, 07:00
VICKY69 wrote:
plzBunuel explain in simple language how to find Find The Last three digits of 2003^2002^2001?

You'll never need this for the GMAT.
_________________

Kudos [?]: 118889 [0], given: 12010

Intern
Joined: 05 May 2016
Posts: 8

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

Location: India

### Show Tags

26 May 2016, 11:48
HOW TO SOLVE THIS QNS PLZ HELP../

IF P,Q AND R ARE THREE PRIMES(NOT NECESSARILY DISTINCT) AND P+Q+R LEAVES A REMAINDER OF 2 WHEN DIVIDED BY 6,WHICH OF FOLLOWING STATEMENT IS/ARE DEFINITELY TRUE?
1. P-Q IS ODD
2. P+Q IS A MULTIPLE OF 6
3. PQR(P+Q+R) IS EVEN
4.P+3Q+5R IS EVEN

PLZ HELP

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

Intern
Joined: 18 May 2016
Posts: 1

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

### Show Tags

09 Jun 2016, 06:39
Hi Bunuel,
Thank you very much for your help. I just have one point that I seem to not get in here. May I know how the below term is correct? I tried to insert numbers for a and b but I haven't gotten -b?

• If a is a factor of b and b is a factor of a, then a=b or a=−b.

Mary

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

Re: Math: Number Theory   [#permalink] 09 Jun 2016, 06:39

Go to page   Previous    1   2   3   4   5   6   7   8   9   10    Next  [ 198 posts ]

Similar topics Replies Last post
Similar
Topics:
3 A number theory curiosity 6 24 May 2017, 09:32
24 If a and b are different positive integers and a+b=a(a+b) 14 07 May 2017, 05:08
1 Qs about Number Theory 3 21 May 2010, 02:08
71 Math: Number Theory - Percents 51 03 Apr 2017, 08:00
12 Math: Number Theory (broken into smaller topics) 11 03 Oct 2015, 04:43
Display posts from previous: Sort by