Math: Number Theory

Hello Bunuel - thank you so much for this fantastic post!

with regards to checking for primality:



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.

\((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 ( )

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.



\(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.

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

•

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?

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

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

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.

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

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

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