Author 
Message 
TAGS:

Hide Tags

Retired Moderator
Joined: 02 Sep 2010
Posts: 775
Location: London

Re: Math: Number Theory [#permalink]
Show Tags
28 Oct 2010, 22:28
\(36=6^2=2^2*3^2\) Powers of 2 & 3 are even (2) Posted from my mobile device
_________________
Math writeups 1) Algebra101 2) Sequences 3) Set combinatorics 4) 3D geometry
My GMAT story
GMAT Club Premium Membership  big benefits and savings



Senior Manager
Status: Do and Die!!
Joined: 15 Sep 2010
Posts: 288

Re: Math: Number Theory [#permalink]
Show Tags
01 Nov 2010, 11:09
If n is a positive integer greater than 1, then there is always a prime number P with n<P<2nn<p<2n can someone please explain this with example . Thanks
_________________
I'm the Dumbest of All !!



Retired Moderator
Joined: 02 Sep 2010
Posts: 775
Location: London

Re: Math: Number Theory [#permalink]
Show Tags
01 Nov 2010, 16:16
shrive555 wrote: If n is a positive integer greater than 1, then there is always a prime number P with n<P<2n
n<p<2n can someone please explain this with example .
Thanks The result you are referring to is a weak form of what is known as Bertrand's Postulate. The proof of this result is beyond the scope of the GMAT, but it is easy to show some examples. Choose any n>1, you will always find a prime number between n & 2n. Eg. n=5, 2n=10 ... p=7 lies in between n=14, 2n=28 ... p=19 lies in between n=20, 2n=40 ... p=23 lies in between
_________________
Math writeups 1) Algebra101 2) Sequences 3) Set combinatorics 4) 3D geometry
My GMAT story
GMAT Club Premium Membership  big benefits and savings



Intern
Joined: 18 Oct 2010
Posts: 2

Re: Math: Number Theory [#permalink]
Show Tags
18 Nov 2010, 23:47
Hello Bunuel  thank you so much for this fantastic post! with regards to checking for primality: Quote: Verifying the primality (checking whether the number is a prime) of a given number can be done by trial division, that is to say dividing by all integer numbers smaller than , thereby checking whether is a multiple of . Example: Verifying the primality of : is little less than , from integers from to , is divisible by , hence is not prime.
Would it be accurate to say that a number is prime ONLY if it gives a remainder of 1 or 5 when divided by 6? i.e, for eg. 10973/6 gives a remainder of 5, so it has to be prime... i found the reasoning behind this in one of the OG solutions: prime numbers always take the form: 6n+1 or 6n+5 .... the only possible remainders when any number is divided by 6 are [0,1,2,3,4,5] ... A prime number always gives a remainder of 1 or 5, because: a) if the remainder is 2 or 4, then the number must be even b) if the remainder is 3, then it is divisible by 3 ... hence, if a number divided by 6 yields 1 or 5 as its remainder, then it must be prime ...? Raj



Math Expert
Joined: 02 Sep 2009
Posts: 46284

Re: Math: Number Theory [#permalink]
Show Tags
19 Nov 2010, 01:53
Araj wrote: Hello Bunuel  thank you so much for this fantastic post! with regards to checking for primality: Quote: Verifying the primality (checking whether the number is a prime) of a given number can be done by trial division, that is to say dividing by all integer numbers smaller than , thereby checking whether is a multiple of . Example: Verifying the primality of : is little less than , from integers from to , is divisible by , hence is not prime.
Would it be accurate to say that a number is prime ONLY if it gives a remainder of 1 or 5 when divided by 6? i.e, for eg. 10973/6 gives a remainder of 5, so it has to be prime... i found the reasoning behind this in one of the OG solutions: prime numbers always take the form: 6n+1 or 6n+5 .... the only possible remainders when any number is divided by 6 are [0,1,2,3,4,5] ... A prime number always gives a remainder of 1 or 5, because: a) if the remainder is 2 or 4, then the number must be even b) if the remainder is 3, then it is divisible by 3 ... hence, if a number divided by 6 yields 1 or 5 as its remainder, then it must be prime ...? Raj First of all there is no known formula of prime numbers.Next:Any prime number \(p>3\) when divided by 6 can only give remainder of 1 or 5 (remainder can not be 2 or 4 as in this case \(p\) would be even and remainder can not be 3 as in this case \(p\) would be divisible by 3). So any prime number \(p>3\) could be expressed as \(p=6n+1\) or\(p=6n+5\) or \(p=6n1\), where n is an integer >1. But:Not all number which yield a remainder of 1 or 5 upon division by 6 are prime, so viseversa of above property is not correct. For example 25 yields a remainder of 1 upon division be 6 and it's not a prime number. Hope it's clear.
_________________
New to the Math Forum? Please read this: Ultimate GMAT Quantitative Megathread  All You Need for Quant  PLEASE READ AND FOLLOW: 12 Rules for Posting!!! Resources: GMAT Math Book  Triangles  Polygons  Coordinate Geometry  Factorials  Circles  Number Theory  Remainders; 8. Overlapping Sets  PDF of Math Book; 10. Remainders  GMAT Prep Software Analysis  SEVEN SAMURAI OF 2012 (BEST DISCUSSIONS)  Tricky questions from previous years.
Collection of Questions: PS: 1. Tough and Tricky questions; 2. Hard questions; 3. Hard questions part 2; 4. Standard deviation; 5. Tough Problem Solving Questions With Solutions; 6. Probability and Combinations Questions With Solutions; 7 Tough and tricky exponents and roots questions; 8 12 Easy Pieces (or not?); 9 Bakers' Dozen; 10 Algebra set. ,11 Mixed Questions, 12 Fresh Meat DS: 1. DS tough questions; 2. DS tough questions part 2; 3. DS tough questions part 3; 4. DS Standard deviation; 5. Inequalities; 6. 700+ GMAT Data Sufficiency Questions With Explanations; 7 Tough and tricky exponents and roots questions; 8 The Discreet Charm of the DS; 9 Devil's Dozen!!!; 10 Number Properties set., 11 New DS set.
What are GMAT Club Tests? Extrahard Quant Tests with Brilliant Analytics



Senior Manager
Status: Do and Die!!
Joined: 15 Sep 2010
Posts: 288

Re: Math: Number Theory [#permalink]
Show Tags
05 Dec 2010, 16:36
\((a^m)^n=a^{mn}\) 1 \((2^2)^2 = 2^2*^2 =2^4\) \(a^m^n=a^{(m^n)}\) and not \((a^m)^n\) 2 \(2^2^2 = 2^(2^2) = 2^4\) If above example is correct then whats the difference 1 & 2. Please clarify thanks
_________________
I'm the Dumbest of All !!



Retired Moderator
Joined: 02 Sep 2010
Posts: 775
Location: London

Re: Math: Number Theory [#permalink]
Show Tags
05 Dec 2010, 20:36
shrive555 wrote: \((a^m)^n=a^{mn}\) 1
\((2^2)^2 = 2^2*^2 =2^4\)
\(a^m^n=a^{(m^n)}\) and not \((a^m)^n\) 2
\(2^2^2 = 2^(2^2) = 2^4\)
If above example is correct then whats the difference 1 & 2. Please clarify thanks I think its just that you have taken a bad example here. Consider a=2, m=3, b=2 \((a^m)^n=(2^3)^2=8^2=64\) \(a^{(m^n)}=2^{(3^2)}=2^9=512\)
_________________
Math writeups 1) Algebra101 2) Sequences 3) Set combinatorics 4) 3D geometry
My GMAT story
GMAT Club Premium Membership  big benefits and savings



Senior Manager
Status: Do and Die!!
Joined: 15 Sep 2010
Posts: 288

Re: Math: Number Theory [#permalink]
Show Tags
05 Dec 2010, 22:16
shrouded1 wrote: shrive555 wrote: \((a^m)^n=a^{mn}\) 1
\((2^2)^2 = 2^2*^2 =2^4\)
\(a^m^n=a^{(m^n)}\) and not \((a^m)^n\) 2
\(2^2^2 = 2^(2^2) = 2^4\)
If above example is correct then whats the difference 1 & 2. Please clarify thanks I think its just that you have taken a bad example here. Consider a=2, m=3, b=2 \((a^m)^n=(2^3)^2=8^2=64\) \(a^{(m^n)}=2^{(3^2)}=2^9=512\) In question would that be given explicitly ... i mean the Brackets ( )
_________________
I'm the Dumbest of All !!



Math Expert
Joined: 02 Sep 2009
Posts: 46284

Re: Math: Number Theory [#permalink]
Show Tags
06 Dec 2010, 01:08
shrive555 wrote: \((a^m)^n=a^{mn}\) 1
\((2^2)^2 = 2^2*^2 =2^4\)
\(a^m^n=a^{(m^n)}\) and not \((a^m)^n\) 2
\(2^2^2 = 2^(2^2) = 2^4\)
If above example is correct then whats the difference 1 & 2. Please clarify thanks If exponentiation is indicated by stacked symbols, the rule is to work from the top down, thus: \(a^m^n=a^{(m^n)}\) and not \((a^m)^n\), which on the other hand equals to \(a^{mn}\). So: \((a^m)^n=a^{mn}\); \(a^m^n=a^{(m^n)}\) and not \((a^m)^n\). Now, there are some specific values of \(a\), \(m\) and \(n\) for which \(a^m^n\) equals to \(a^{mn}\). For example: \(a=1\): \(1^{m^n}=1=1^{mn}\); \(m=0\): \(a^0^n=a^0=1\) and \(a^{0*n}=a^0=1\); \(m=2\) and \(n=2\) > \(a^{2^2}=a^4\) and \(a^{2*2}=a^4\); \(m=4\) and \(n=\frac{1}{2}\) > \(a^{4^{\frac{1}{2}}}=a^2\) and \(a^{4*{\frac{1}{2}}}=a^2\); ... So, generally \(a^m^n\) does not equal to \((a^m)^n\), but for specific values of given variables it does. shrive555 wrote: In question would that be given explicitly ... i mean the Brackets ( ) \(a^m^n\) ALWAYS means \(a^{(m^n)}\), so no brackets are needed. For example \(2^{3^4}=2^{(3^4)}=2^{81}\); If GMAT wants the order of operation to be different then the necessary brackets will be put. For example: \((2^3)^4=2^{(3*4)}=2^{12}\). Hope it's clear.
_________________
New to the Math Forum? Please read this: Ultimate GMAT Quantitative Megathread  All You Need for Quant  PLEASE READ AND FOLLOW: 12 Rules for Posting!!! Resources: GMAT Math Book  Triangles  Polygons  Coordinate Geometry  Factorials  Circles  Number Theory  Remainders; 8. Overlapping Sets  PDF of Math Book; 10. Remainders  GMAT Prep Software Analysis  SEVEN SAMURAI OF 2012 (BEST DISCUSSIONS)  Tricky questions from previous years.
Collection of Questions: PS: 1. Tough and Tricky questions; 2. Hard questions; 3. Hard questions part 2; 4. Standard deviation; 5. Tough Problem Solving Questions With Solutions; 6. Probability and Combinations Questions With Solutions; 7 Tough and tricky exponents and roots questions; 8 12 Easy Pieces (or not?); 9 Bakers' Dozen; 10 Algebra set. ,11 Mixed Questions, 12 Fresh Meat DS: 1. DS tough questions; 2. DS tough questions part 2; 3. DS tough questions part 3; 4. DS Standard deviation; 5. Inequalities; 6. 700+ GMAT Data Sufficiency Questions With Explanations; 7 Tough and tricky exponents and roots questions; 8 The Discreet Charm of the DS; 9 Devil's Dozen!!!; 10 Number Properties set., 11 New DS set.
What are GMAT Club Tests? Extrahard Quant Tests with Brilliant Analytics



Intern
Joined: 04 Dec 2010
Posts: 3

Re: Math: Number Theory [#permalink]
Show Tags
03 Jan 2011, 09:42
Bunuel,
For determining last digit of a power for numbers 0, 1, 5, and 6, I am not clear on how to determine the last digit.
Your post says: • Integer ending with 0, 1, 5 or 6, in the integer power k>0, has the same last digit as the base.
What is the last digit of 345^27 is the last digit 5? What is the last digit of 216^32is the last digit 6? What is the last digit of 111^56is the last digit 1?
Any clarification would be helpful.
Thanks for all your help.



Math Expert
Joined: 02 Sep 2009
Posts: 46284

Re: Math: Number Theory [#permalink]
Show Tags
03 Jan 2011, 09:52
resh924 wrote: Bunuel,
For determining last digit of a power for numbers 0, 1, 5, and 6, I am not clear on how to determine the last digit.
Your post says: • Integer ending with 0, 1, 5 or 6, in the integer power k>0, has the same last digit as the base.
What is the last digit of 345^27 is the last digit 5? What is the last digit of 216^32is the last digit 6? What is the last digit of 111^56is the last digit 1?
Any clarification would be helpful.
Thanks for all your help. First of all: last digit of 345^27 is the same as that of 5^27 (the same for 216^32 and 111^56); Next: 1 in any integer power is 1; 5^1= 5, 5^2=2 5, 5^3=12 5, ... 6^1= 6, 6^2=3 6, 5^3=21 6, ... So yes, integer ending with 0, 1, 5 or 6, in the integer power k>0, has the same last digit as the base: thus 0, 1, 5, and 6 respectively. Hope it's clear.
_________________
New to the Math Forum? Please read this: Ultimate GMAT Quantitative Megathread  All You Need for Quant  PLEASE READ AND FOLLOW: 12 Rules for Posting!!! Resources: GMAT Math Book  Triangles  Polygons  Coordinate Geometry  Factorials  Circles  Number Theory  Remainders; 8. Overlapping Sets  PDF of Math Book; 10. Remainders  GMAT Prep Software Analysis  SEVEN SAMURAI OF 2012 (BEST DISCUSSIONS)  Tricky questions from previous years.
Collection of Questions: PS: 1. Tough and Tricky questions; 2. Hard questions; 3. Hard questions part 2; 4. Standard deviation; 5. Tough Problem Solving Questions With Solutions; 6. Probability and Combinations Questions With Solutions; 7 Tough and tricky exponents and roots questions; 8 12 Easy Pieces (or not?); 9 Bakers' Dozen; 10 Algebra set. ,11 Mixed Questions, 12 Fresh Meat DS: 1. DS tough questions; 2. DS tough questions part 2; 3. DS tough questions part 3; 4. DS Standard deviation; 5. Inequalities; 6. 700+ GMAT Data Sufficiency Questions With Explanations; 7 Tough and tricky exponents and roots questions; 8 The Discreet Charm of the DS; 9 Devil's Dozen!!!; 10 Number Properties set., 11 New DS set.
What are GMAT Club Tests? Extrahard Quant Tests with Brilliant Analytics



Intern
Joined: 23 Jan 2011
Posts: 8

Re: Math: Number Theory [#permalink]
Show Tags
21 Feb 2011, 18:41
• Quote: If is a prime number and is a factor of then is a factor of or is a factor of . 2 is a prime number. 2 is a factor of 12*16. This implies that 2 is a factor of both 12 and 16. Am I missing something here?



Intern
Joined: 23 Jan 2011
Posts: 8

Re: Math: Number Theory [#permalink]
Show Tags
21 Feb 2011, 18:44
Quote: If p is a prime number and p is a factor of ab then p is a factor of a or p is a factor of b. Sorry did not quote the post correctly



Math Expert
Joined: 02 Sep 2009
Posts: 46284

Re: Math: Number Theory [#permalink]
Show Tags
21 Feb 2011, 19:03



Manager
Joined: 10 Nov 2010
Posts: 222
Location: India
Concentration: Strategy, Operations
GMAT 1: 520 Q42 V19 GMAT 2: 540 Q44 V21
WE: Information Technology (Computer Software)

Re: Math: Number Theory [#permalink]
Show Tags
27 Feb 2011, 10:04
Any nonzero natural number n can be factored into primes, written as a product of primes or powers of primes. Moreover, this factorization is unique except for a possible reordering of the factors.Pls give me the example of bold face text because i am not sure what does it exactly means. Thanks
_________________
The proof of understanding is the ability to explain it.



Math Expert
Joined: 02 Sep 2009
Posts: 46284

Re: Math: Number Theory [#permalink]
Show Tags
27 Feb 2011, 10:12
GMATD11 wrote: Any nonzero natural number n can be factored into primes, written as a product of primes or powers of primes. Moreover, this factorization is unique except for a possible reordering of the factors.
Pls give me the example of bold face text because i am not sure what does it exactly means.
Thanks It's called the fundamental theorem of arithmetic (or the uniqueprimefactorization theorem) which states that any integer greater than 1 can be written as a unique product of prime numbers. For example: 60=2^2*3*5 > 60 can be written as a product of primes (powers of primes) only in this unique way (you can just reorder the multiples and write 3*2^2*5 or 2^2*5*3 ...).
_________________
New to the Math Forum? Please read this: Ultimate GMAT Quantitative Megathread  All You Need for Quant  PLEASE READ AND FOLLOW: 12 Rules for Posting!!! Resources: GMAT Math Book  Triangles  Polygons  Coordinate Geometry  Factorials  Circles  Number Theory  Remainders; 8. Overlapping Sets  PDF of Math Book; 10. Remainders  GMAT Prep Software Analysis  SEVEN SAMURAI OF 2012 (BEST DISCUSSIONS)  Tricky questions from previous years.
Collection of Questions: PS: 1. Tough and Tricky questions; 2. Hard questions; 3. Hard questions part 2; 4. Standard deviation; 5. Tough Problem Solving Questions With Solutions; 6. Probability and Combinations Questions With Solutions; 7 Tough and tricky exponents and roots questions; 8 12 Easy Pieces (or not?); 9 Bakers' Dozen; 10 Algebra set. ,11 Mixed Questions, 12 Fresh Meat DS: 1. DS tough questions; 2. DS tough questions part 2; 3. DS tough questions part 3; 4. DS Standard deviation; 5. Inequalities; 6. 700+ GMAT Data Sufficiency Questions With Explanations; 7 Tough and tricky exponents and roots questions; 8 The Discreet Charm of the DS; 9 Devil's Dozen!!!; 10 Number Properties set., 11 New DS set.
What are GMAT Club Tests? Extrahard Quant Tests with Brilliant Analytics



Manager
Joined: 23 Aug 2011
Posts: 76

Re: Math: Number Theory [#permalink]
Show Tags
04 Sep 2012, 19:34
Bunuel wrote: NUMBER THEORY
Trailing zeros: Trailing zeros are a sequence of 0's in the decimal representation (or more generally, in any positional representation) of a number, after which no other digits follow.
125000 has 3 trailing zeros;
The number of trailing zeros in the decimal representation of n!, the factorial of a nonnegative integer \(n\), can be determined with this formula:
\(\frac{n}{5}+\frac{n}{5^2}+\frac{n}{5^3}+...+\frac{n}{5^k}\), where k must be chosen such that \(5^k<n\).
It's easier if you look at an example:
How many zeros are in the end (after which no other digits follow) of \(32!\)? \(\frac{32}{5}+\frac{32}{5^2}=6+1=7\) (denominator must be less than 32, \(5^2=25\) is less)
Hence, there are 7 zeros in the end of 32!
The formula actually counts the number of factors 5 in n!, but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero.
I noticed in case the number (n) is multiple of \(5^k\) and we have to find number of trailing zero zeroes, then it will be \(5^k<=n\) rather \(5^k<n\) no of trailing zeros in 25! =6 \(\frac{25}{5}+\frac{25}{5^2}= 5+1\); Please correct me, clarify if i'm wrong. Thanks
_________________
Whatever one does in life is a repetition of what one has done several times in one's life! If my post was worth it, then i deserve kudos



Intern
Joined: 18 Jan 2012
Posts: 49
Location: United States

Re: Math: Number Theory [#permalink]
Show Tags
25 Sep 2012, 10:43
conty911 wrote: Bunuel wrote: NUMBER THEORY
Trailing zeros: Trailing zeros are a sequence of 0's in the decimal representation (or more generally, in any positional representation) of a number, after which no other digits follow.
125000 has 3 trailing zeros;
The number of trailing zeros in the decimal representation of n!, the factorial of a nonnegative integer \(n\), can be determined with this formula:
\(\frac{n}{5}+\frac{n}{5^2}+\frac{n}{5^3}+...+\frac{n}{5^k}\), where k must be chosen such that \(5^k<n\).
It's easier if you look at an example:
How many zeros are in the end (after which no other digits follow) of \(32!\)? \(\frac{32}{5}+\frac{32}{5^2}=6+1=7\) (denominator must be less than 32, \(5^2=25\) is less)
Hence, there are 7 zeros in the end of 32!
The formula actually counts the number of factors 5 in n!, but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero.
I noticed in case the number (n) is multiple of \(5^k\) and we have to find number of trailing zero zeroes, then it will be \(5^k<=n\) rather \(5^k<n\) no of trailing zeros in 25! =6 \(\frac{25}{5}+\frac{25}{5^2}= 5+1\); Please correct me, clarify if i'm wrong. Thanks The highest power of a prime number "k" that divides any number "n!" is given by the formula n/K + n/k^2+n/k^3.. (until numerator becomes lesser than the denominator). Remember to truncate the remainders of each expressionE.g : The highest number of 2's in 10! is 10/2 + 10/4 + 10/8 = 5 + 2 + 1 = 8 (Truncate the reminder of each expression) As a consequence of this, the number of zeros in n! is controlled by the presence of 5s. Why ? 2 reasons a) 10 = 5 x 2, b) Also in any n!, the number of 5's are far lesser than the number of 2's. Think about this example. The number of cars that you make depends on the number of engines. You can have 100 engines and 1000 cars, but you can only make 100 cars (each car needs an engine !) 10 ! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 Lets factorize each term ... 10! = (5 x 2) x(3x3)x(2x2x2)x7x(2x3)x(5)X(2x2)x1 the number of 5s = 2 The number of 2s = 7 The number of zeros in 10! = the total number of 5s = 2 (You may use a calc to check this 10! = 3628800) hence in any n! , the number of 5's control the number of zeros.As a consequence of this, the number of 5's in any n! is n/5 + n/25 + n/125 ..until numerator becomes lesser than denominator. Again, i want to emphasize that this formuala only works for prime numbers !! So to find the number of 10's in any n!, DO NOT DIVIDE by 10 ! (10 is not prime !) i.e DONT do n/10 + n/100 + n/1000  THIS IS WRONG !!!
_________________
 IT TAKES QUITE A BIT OF TIME AND ENERGY TO POST DETAILED RESPONSES. A KUDOS IS a small but effective way to say "Thank You" 



Intern
Status: Active
Joined: 30 Jun 2012
Posts: 38
Location: India

Re: Math: Number Theory [#permalink]
Show Tags
27 Oct 2012, 02:00
I shall like to add one trick to find square of number : To find square of a number \((ab)^2\) where a is tens digit and b is units digit => 1. Multiply tens digit a by (a+1) i.e. a * (a+1) = A 2. Suffix 25 to the above derived result A and the new number will be A25 Example: what is \(35^2\)? Solution: 3 * (3+1) = 3*4 = 12 and so answer is 1225
_________________
Thanks and Regards!
P.S. +Kudos Please! in case you like my post.



Intern
Status: Active
Joined: 30 Jun 2012
Posts: 38
Location: India

Re: Math: Number Theory [#permalink]
Show Tags
27 Oct 2012, 02:34
About Exponents and divisibility: \((a + b)^2 = a^2+ 2ab + b^2\) Square of a Sum \((a  b)^2 = a^2  2ab + b^2\) Square of a Difference \(a^n  b^n\) is always divisble by ab i.e. irrespective of n being odd or even Proof: \(a^2  b^2 = (ab)(a+b)\) \(a^3  b^3 = (ab)(a^2+ab+b^2)\) Thus divisible by a b in both cases where n = 2 i.e. even and 3 i.e. odd \(a^n + b^n\) is divisble by a+b i.e. only if n = odd Proof: \(a^3  b^3 = (a+b)(a^2ab+b^2)\) Thus divisible by a + b as n = 3 i.e. odd
_________________
Thanks and Regards!
P.S. +Kudos Please! in case you like my post.




Re: Math: Number Theory
[#permalink]
27 Oct 2012, 02:34



Go to page
Previous
1 2 3 4
Next
[ 70 posts ]



