GMAT Question of the Day: Daily via email | Daily via Instagram New to GMAT Club? Watch this Video

 It is currently 24 Feb 2020, 02:08

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

# Math: Number Theory

Author Message
TAGS:

### Hide Tags

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

### Show Tags

28 Oct 2010, 21:28
2
$$36=6^2=2^2*3^2$$

Powers of 2 & 3 are even (2)

Posted from my mobile device
_________________
Manager
Status: Do and Die!!
Joined: 15 Sep 2010
Posts: 242

### Show Tags

01 Nov 2010, 10:09
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
_________________
I'm the Dumbest of All !!
Retired Moderator
Joined: 02 Sep 2010
Posts: 709
Location: London

### Show Tags

01 Nov 2010, 15:16
2
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
_________________
Intern
Joined: 18 Oct 2010
Posts: 1

### Show Tags

18 Nov 2010, 22: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: 61417

### Show Tags

19 Nov 2010, 00:53
1
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=6n-1$$, 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 vise-versa 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.
_________________
Manager
Status: Do and Die!!
Joined: 15 Sep 2010
Posts: 242

### Show Tags

05 Dec 2010, 15: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: 709
Location: London

### Show Tags

05 Dec 2010, 19: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$$
_________________
Manager
Status: Do and Die!!
Joined: 15 Sep 2010
Posts: 242

### Show Tags

05 Dec 2010, 21: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: 61417

### Show Tags

06 Dec 2010, 00:08
1
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.
_________________
Intern
Joined: 04 Dec 2010
Posts: 3

### Show Tags

03 Jan 2011, 08: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.

• 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^32----is the last digit 6?
What is the last digit of 111^56---is the last digit 1?

Math Expert
Joined: 02 Sep 2009
Posts: 61417

### Show Tags

03 Jan 2011, 08:52
1
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.

• 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^32----is the last digit 6?
What is the last digit of 111^56---is the last digit 1?

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=25, 5^3=125, ...
6^1=6, 6^2=36, 5^3=216, ...

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.
_________________
Intern
Joined: 23 Jan 2011
Posts: 7

### Show Tags

21 Feb 2011, 17: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: 7

### Show Tags

21 Feb 2011, 17: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: 61417

### Show Tags

21 Feb 2011, 18:03
bugSniper wrote:
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

This is inclusive *or* (as almost always on the GMAT): p is a factor of a or p is a factor of b (or both).
_________________
Manager
Joined: 10 Nov 2010
Posts: 161
Location: India
Concentration: Strategy, Operations
GMAT 1: 520 Q42 V19
GMAT 2: 540 Q44 V21
WE: Information Technology (Computer Software)

### Show Tags

27 Feb 2011, 09: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
Math Expert
Joined: 02 Sep 2009
Posts: 61417

### Show Tags

27 Feb 2011, 09: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 unique-prime-factorization 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 ...).
_________________
Manager
Joined: 23 Aug 2011
Posts: 61

### Show Tags

04 Sep 2012, 18: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 non-negative 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
Intern
Joined: 18 Jan 2012
Posts: 43
Location: United States
Schools: IIM A '15 (A)

### Show Tags

25 Sep 2012, 09:43
2
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 non-negative 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 expression

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

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 this10! = 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 !!!
Intern
Status: Active
Joined: 30 Jun 2012
Posts: 36
Location: India

### Show Tags

27 Oct 2012, 01:00
2
1
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
Intern
Status: Active
Joined: 30 Jun 2012
Posts: 36
Location: India

### Show Tags

27 Oct 2012, 01:34
2

$$(a + b)^2 = a^2+ 2ab + b^2$$ Square of a Sum
$$(a - b)^2 = a^2 - 2ab + b^2$$ Square of a Diffe rence

$$a^n - b^n$$ is always divisble by a-b i.e. irrespective of n being odd or even
Proof:
$$a^2 - b^2 = (a-b)(a+b)$$
$$a^3 - b^3 = (a-b)(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^2-ab+b^2)$$
Thus divisible by a + b as n = 3 i.e. odd
Re: Math: Number Theory   [#permalink] 27 Oct 2012, 01:34

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

Display posts from previous: Sort by