Last visit was: 11 Sep 2024, 10:28 It is currently 11 Sep 2024, 10:28
Toolkit
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
Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.

# Math: Number Theory

SORT BY:
Tags:
Show Tags
Hide Tags
Math Expert
Joined: 02 Sep 2009
Posts: 95451
Own Kudos [?]: 657673 [2393]
Given Kudos: 87242
Math Expert
Joined: 02 Sep 2009
Posts: 95451
Own Kudos [?]: 657673 [29]
Given Kudos: 87242
Math Expert
Joined: 02 Sep 2009
Posts: 95451
Own Kudos [?]: 657673 [22]
Given Kudos: 87242
General Discussion
Manager
Joined: 22 Dec 2009
Posts: 179
Own Kudos [?]: 967 [8]
Given Kudos: 48
8
Kudos
Bunuel wrote:

Prime Numbers

Verifying the primality 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.

Pardon my ignorance, but I am not very much aware of this term Primality. Could you please explain this in detail? Haven't heard of this before!

Bunuel wrote:
Converting Decimals to Fractions

• To convert a mixed-recurring decimal to fraction:
1. Write down the number consisting with non-repeating digits and repeating digits.
2. Subtract non-repeating number from above.
3. Divide 1-2 by the number with 9's and 0's: for every repeating digit write down a 9, and for every non-repeating digit write down a zero after 9's.

Example #2: Convert $$0.2512(12)$$ to a fraction.
1. The number consisting with non-repeating digits and repeating digits is 2512;
2. Subtract 25 (non-repeating number) from above: 2512-25=2487;
3. Divide 2487 by 9900 (two 9's as there are two digits in 12 and 2 zeros as there are two digits in 25): 2487/9900=829/3300.

What exactly do you mean by mixed recurring decimal? In the example taken, you have the number written as $$0.2512(12)$$. Does this mean the number is $$0.2512121212.....$$ ? Please clarify...!

Bunuel wrote:
EXPONENTS

Exponents are a "shortcut" method of showing a number that was multiplied by itself several times. For instance, number $$a$$ multiplied $$n$$ times can be written as $$a^n$$, where $$a$$ represents the base, the number that is multiplied by itself $$n$$ times and $$n$$ represents the exponent. The exponent indicates how many times to multiple the base, $$a$$, by itself.

Exponents one and zero:
$$a^0=1$$ Any nonzero number to the power of 0 is 1.
For example: $$5^0=1$$ and $$0^0=1$$

You say any non zero number to the power of 0 is 1.... but in the example below you show $$0^0 = 1$$.. Is it a typo or is there something more to it which I do not understand! Please clarify!

Overall it's an awesome summary of all important points needed in Maths.... Thanks Bunuel and the others!
I see that you are still working on this as of now! Any plan by when would you complete this Bible!
Intern
Joined: 30 Jun 2009
Posts: 20
Own Kudos [?]: 14 [4]
Given Kudos: 2
3
Kudos
1
Bookmarks
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
Current Student
Joined: 12 Nov 2008
Posts: 352
Own Kudos [?]: 137 [1]
Given Kudos: 45
Concentration: Corp Fin
Schools:Ross (R2), Cornell (R3) , UNC (R3) , INSEAD (R1 Jan)
Q44  V42 GMAT 2: 710  Q47  V40
GPA: 1.87
WE 2: FP &amp; Analysis (2 yrs at matriculation)
1
Kudos
Bunuel wrote:
All prime numbers except 2 and 5 end in 1, 3, 7 or 9, since numbers ending in 0, 2, 4, 6 or 8 are multiples of 2 and numbers ending in 0 or 5 are multiples of 5. Similarly, all prime numbers above 3 are of the form $$6n-1$$ or $$6n+1$$, because all other numbers are divisible by 2 or 3.

Awesome post, thank you so much! +1

What is the quickest way to figure out whether a number is prime? I usually check if it's odd or even, then sum its digits to figure out if it's divisible by 3, then look if it ends in 5 and if all else fails divide it by 7. Is this the recommended approach?

What might be a bit confusing is that while all prime numbers are of the form 6n-1 or 6n+1, not all numbers of that form are in fact prime. I think this is crucial. For instance, the number 49 is 6n+1, but is not prime.

Any insight on a quicker check (if one exists) would be much appreciated and thank you again for your efforts. They make a real difference!
SVP
Joined: 17 Nov 2007
Posts: 2404
Own Kudos [?]: 10210 [7]
Given Kudos: 361
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth) - Class of 2011
GMAT 1: 750 Q50 V40
1
Kudos
5
Bookmarks
ariel wrote:
What is the quickest way to figure out whether a number is prime?

Unfortunately, there is no such quick way to say that this number is prime. You can remember all numbers till 50 and then use rule:

Rule: To check whether a number is prime or not, we try to divide it by 2, 3, 5 and so on. You can stop at $$\sqrt{number}$$ - it is enough. Why? Because if there is prime divisor greater than $$\sqrt{number}$$, there must be another prime divisor lesser than $$\sqrt{number}$$.

Example,

n = 21 -- > $$\sqrt{21}$$~ 4-5
So, we need to check out only 2,3 because for 7, for instance, we have already checked out 3.

n = 101 --> 2,3,5 is out (the last digit is not even or 5 and sum of digits is not divisible by 3). we need to check out only 7
Current Student
Joined: 12 Nov 2008
Posts: 352
Own Kudos [?]: 137 [1]
Given Kudos: 45
Concentration: Corp Fin
Schools:Ross (R2), Cornell (R3) , UNC (R3) , INSEAD (R1 Jan)
Q44  V42 GMAT 2: 710  Q47  V40
GPA: 1.87
WE 2: FP &amp; Analysis (2 yrs at matriculation)
Appreciate the very prompt response, walker. To your point re divisibility by 7: I'm having a hard time proving this algebraically, is it a fair statement to say that the only non-prime numbers of the form 6n-1 and 6n+1 are the ones that are divisible by 7?

If so, a quick way to check whether a big number is prime would be to: 1) check whether it's of the form 6n-1 or 6n+1 2) check whether it's divisible by 7

Is this correct?
Math Expert
Joined: 02 Sep 2009
Posts: 95451
Own Kudos [?]: 657673 [10]
Given Kudos: 87242
3
Kudos
6
Bookmarks
ariel wrote:
Appreciate the very prompt response, walker. To your point re divisibility by 7: I'm having a hard time proving this algebraically, is it a fair statement to say that the only non-prime numbers of the form 6n-1 and 6n+1 are the ones that are divisible by 7?

If so, a quick way to check whether a big number is prime would be to: 1) check whether it's of the form 6n-1 or 6n+1 2) check whether it's divisible by 7

Is this correct?

Not so. Divisibility by 7 does not check whether the number is prime or not.

Actually this issue is covered in the post. First you should know that all prime numbers except 2 and 5 end in 1, 3, 7 or 9. So if it ends in some other digit it's not prime.

Next, if the above didn't help (meaning that number ends in 1, 3, 7 or 9) there is a way to check whether the number is prime or not. Walker gave an example how to do this, but here it is again:

Verifying the primality 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}$$.

Examples: Verifying the primality of $$161$$: $$\sqrt{161}$$ is little less than $$13$$. We should check $$161$$ on divisibility by numbers from 2 to 13. From integers from $$2$$ to $$13$$, $$161$$ is divisible by $$7$$, hence $$161$$ is not prime.

Verifying the primality of $$149$$: $$\sqrt{149}$$ is little more than $$12$$. We should check $$149$$ on divisibility by numbers from 2 to 12, inclusive. $$149$$ is not divisible by any of the integers from $$2$$ to $$12$$, hence $$149$$ is prime.

Verifying the primality of $$73$$: $$\sqrt{73}$$ is little less than $$9$$. We should check $$73$$ on divisibility by numbers from 2 to 9. $$73$$ is not divisible by any of the integers from $$2$$ to $$9$$, hence $$149$$ is prime.

Hope it helps.
Intern
Joined: 21 Feb 2010
Posts: 14
Own Kudos [?]: 16 [2]
Given Kudos: 9
Location: Ukraine
1
Kudos
1
Bookmarks
Thanks! It was very very helpful! Kudos!
But I have a question:

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

Why do we take just 5 from {2,3,5} and why do we need divide 12 by 2 to get the result?

Math Expert
Joined: 02 Sep 2009
Posts: 95451
Own Kudos [?]: 657673 [14]
Given Kudos: 87242
10
Kudos
4
Bookmarks
fruit wrote:
Thanks! It was very very helpful! Kudos!
But I have a question:

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

Why do we take just 5 from {2,3,5} and why do we need divide 12 by 2 to get the result?

$$50!=900^xa=(2^2*3^2*5^2)^x*a$$, where $$x$$ is the highest possible value of 900 and $$a$$ is the product of other multiples of $$50!$$.

$$50!=2^{47}*3^{22}*5^{12}*b=(2^2*3^2*5^2)^6*(2^{35}*3^{10})*b=900^{6}*(2^{35}*3^{10})*b$$, where $$b$$ is the product of other multiples of $$50!$$. So $$x=6$$.

Below is another example:

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$$.
Intern
Joined: 14 May 2010
Posts: 3
Own Kudos [?]: [0]
Given Kudos: 0
If a is a factor of bc, and gcd(a,b)=1, then a is a factor of c.

Can anyone please explain this rule??? I'm not sure what it means by gcd(a,b)=1.

Thanks a bunch and great summary !!!!!
Math Expert
Joined: 02 Sep 2009
Posts: 95451
Own Kudos [?]: 657673 [2]
Given Kudos: 87242
1
Kudos
1
Bookmarks
bely202 wrote:
If a is a factor of bc, and gcd(a,b)=1, then a is a factor of c.

Can anyone please explain this rule??? I'm not sure what it means by gcd(a,b)=1.

Thanks a bunch and great summary !!!!!

$$gcd(a,b)=1$$ means that greatest common divisor of $$a$$ and $$b$$ is 1, or in other words they are co-prime, the don't share any common factor but 1. So if we are told that $$a$$ is a factor of $$bc$$ and $$a$$ and $$b$$ don't share any common factors, then it must be true that $$a$$ is a factor of only $$c$$.

So if $$a=3$$, $$b=5$$ ($$a$$ and $$b$$ don't share any common factors but 1, $$gcd(a,b)=1$$), $$c=6$$ $$bc=30$$ --> $$a=3$$ is a factor of $$c=6$$.
Intern
Joined: 05 Nov 2009
Posts: 22
Own Kudos [?]: 7 [3]
Given Kudos: 3
2
Kudos
1
Bookmarks
Bunuel wrote:
fruit wrote:
Thanks! It was very very helpful! Kudos!
But I have a question:

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

Why do we take just 5 from {2,3,5} and why do we need divide 12 by 2 to get the result?

$$50!=900^xa=(2^2*3^2*5^2)^x*a$$, where $$x$$ is the highest possible value of 900 and $$a$$ is the product of other multiples of $$50!$$.

$$50!=2^{47}*3^{22}*5^{12}*b=(2^2*3^2*5^2)^6*(2^{35}*3^{10})*b=900^{6}*(2^{35}*3^{10})*b$$, where $$b$$ is the product of other multiples of $$50!$$. So $$x=6$$.

Below is another example:

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

Does this relationship breakdown at some point? I thought this was great and was just experimenting and looked at 21! (calculated in excel) and it ends with 5 zeros. Using the methodology you described above it should have 4 zeros. Am I missing something or did I make a mistake somewhere?
Math Expert
Joined: 02 Sep 2009
Posts: 95451
Own Kudos [?]: 657673 [4]
Given Kudos: 87242
4
Kudos
utfan2424 wrote:
Does this relationship breakdown at some point? I thought this was great and was just experimenting and looked at 21! (calculated in excel) and it ends with 5 zeros. Using the methodology you described above it should have 4 zeros. Am I missing something or did I make a mistake somewhere?

You made everything right 21! ends with 21/5=4 zeros. It's excel: it makes rounding with such a huge numbers thus giving incorrect result.
VP
Joined: 24 Aug 2010
Status:Current Student
Posts: 1332
Own Kudos [?]: 448 [2]
Given Kudos: 74
Location: United States
GMAT 1: 710 Q48 V40
WE:Sales (Consumer Products)
2
Bookmarks
Bunuel wrote:
NUMBER THEORY
Consecutive Integers

Consecutive integers are integers that follow one another, without skipping any integers. 7, 8, 9, and -2, -1, 0, 1, are consecutive integers.

• Sum of $$n$$ consecutive integers equals the mean multiplied by the number of terms, $$n$$. Given consecutive integers $$\{-3, -2, -1, 0, 1,2\}$$, $$mean=\frac{-3+2}{2}=-\frac{1}{2}$$, (mean equals to the average of the first and last terms), so the sum equals to $$-\frac{1}{2}*6=-3$$.

• If n is odd, the sum of consecutive integers is always divisible by n. Given $$\{9,10,11\}$$, we have $$n=3$$ consecutive integers. The sum of 9+10+11=30, therefore, is divisible by 3.

• If n is even, the sum of consecutive integers is never divisible by n. Given $$\{9,10,11,12\}$$, we have $$n=4$$ consecutive integers. The sum of 9+10+11+12=42, therefore, is not divisible by 4.

• The product of $$n$$ consecutive integers is always divisible by $$n!$$.
Given $$n=4$$ consecutive integers: $$\{3,4,5,6\}$$. The product of 3*4*5*6 is 360, which is divisible by 4!=24.

Evenly Spaced Set

Evenly spaced set or an arithmetic progression is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. The set of integers $$\{9,13,17,21\}$$ is an example of evenly spaced set. Set of consecutive integers is also an example of evenly spaced set.

• If the first term is $$a_1$$ and the common difference of successive members is $$d$$, then the $$n_{th}$$ term of the sequence is given by:
$$a_ n=a_1+d(n-1)$$

• In any evenly spaced set the arithmetic mean (average) is equal to the median and can be calculated by the formula $$mean=median=\frac{a_1+a_n}{2}$$, where $$a_1$$ is the first term and $$a_n$$ is the last term. Given the set $$\{7,11,15,19\}$$, $$mean=median=\frac{7+19}{2}=13$$.

• The sum of the elements in any evenly spaced set is given by:
$$Sum=\frac{a_1+a_n}{2}*n$$, the mean multiplied by the number of terms. OR, $$Sum=\frac{2a_1+d(n-1)}{2}*n$$

• Special cases:
Sum of n first integers: $$1+2+...+n=\frac{1+n}{2}*n$$

Sum of n first odd numbers: $$a_1+a_2+...+a_n=1+3+...+a_n=n^2$$, where $$a_n$$ is the last, $$n_{th}$$ term and given by: $$a_n=2n-1$$. Given $$n=5$$ first odd integers, then their sum equals to $$1+3+5+7+9=5^2=25$$.

Sum of n first positive even numbers: $$a_1+a_2+...+a_n=2+4+...+a_n=n(n+1)$$, where $$a_n$$ is the last, $$n_{th}$$ term and given by: $$a_n=2n$$. Given $$n=4$$ first positive even integers, then their sum equals to $$2+4+6+8=4(4+1)=20$$.

• If the evenly spaced set contains odd number of elements, the mean is the middle term, so the sum is middle term multiplied by number of terms. There are five terms in the set {1, 7, 13, 19, 25}, middle term is 13, so the sum is 13*5 =65.

There seems to be a discrepancy in what some study guides consider consecutive integers. In Kaplan Premier 2011 consecutive integers are defined as numbers that occur at a fixed interval or exhibit a fixed pattern. However, on the Kaplan Free Practice Test I got a DS question wrong because it didn't consider evenly spaced numbers to necessarily be consecutive. Your definition also separates the two. Could anyone clarify which is correct so I know for the actual GMAT. Thanks!
Math Expert
Joined: 02 Sep 2009
Posts: 95451
Own Kudos [?]: 657673 [3]
Given Kudos: 87242
3
Kudos
cheetarah1980 wrote:
There seems to be a discrepancy in what some study guides consider consecutive integers. In Kaplan Premier 2011 consecutive integers are defined as numbers that occur at a fixed interval or exhibit a fixed pattern. However, on the Kaplan Free Practice Test I got a DS question wrong because it didn't consider evenly spaced numbers to necessarily be consecutive. Your definition also separates the two. Could anyone clarify which is correct so I know for the actual GMAT. Thanks!

When we see "consecutive integers" it ALWAYS means integers that follow each other in order with common difference of 1: ... x-3, x-2, x-1, x, x+1, x+2, ...

-7, -6, -5 are consecutive integers.

2, 4, 6 ARE NOT consecutive integers, they are consecutive even integers.

3, 5, 7 ARE NOT consecutive integers, they are consecutive odd integers.

2, 5, 8, 11 ARE NOT consecutive integers, they are terms of arithmetic progression with common difference of 3.

All sets of consecutive integers represent arithmetic progression but not vise-versa.

Hope it's clear.
Intern
Joined: 27 Aug 2010
Posts: 13
Own Kudos [?]: 28 [1]
Given Kudos: 2
1
Kudos
7 - Take the last digit, double it, and subtract it from the rest of the number, if the answer is divisible by 7 (including 0), then the number is divisible by 7.

Is this the only way to check divisibility by 7? For huge numbers there is no big difference to divide the number directly by 7 or to use the algorithm above.
Math Expert
Joined: 02 Sep 2009
Posts: 95451
Own Kudos [?]: 657673 [1]
Given Kudos: 87242
1
Bookmarks
Kronax wrote:
7 - Take the last digit, double it, and subtract it from the rest of the number, if the answer is divisible by 7 (including 0), then the number is divisible by 7.

Is this the only way to check divisibility by 7? For huge numbers there is no big difference to divide the number directly by 7 or to use the algorithm above.

Note that you can perform this operation number of times. Also you won't need to check divisibility by 7 for huge numbers on GMAT.
Manager
Joined: 15 Sep 2010
Status:Do and Die!!
Posts: 203
Own Kudos [?]: 2225 [4]
Given Kudos: 193
Q29  V6 GMAT 3: 430  Q31  V19
4
Bookmarks
Quote:
Perfect Square

A perfect square, is an integer that can be written as the square of some other integer. For example 16=4^2, is an perfect square.

There are some tips about the perfect square:.
Perfect square always has even number of powers of prime factors.

Bunuel : can you please give an example of bold statement

Thanks