# Primes

• Sep 16th 2011, 06:51 AM
pkaff
Primes
How could you prove that if a^n-3^n is a positive prime number, then a=4 and n is a positive prime number? (all numbers are natural)

Am I supposed to try and factor a^n-b^n to see for which a and b the factorization is possible and for which it's not? I am having trouble with that factorization anyhow, so does anyone know how to approach this problem?

I mean it seems to work for small n, but I just can not figure out how to do it for all natural numbers n...

• Sep 16th 2011, 09:45 AM
ebaines
Re: Primes
Consider what happens if n is not a prime number, so n = pq. You can show that \$\displaystyle a^{pq} - b^{pq}\$ is divisible by \$\displaystyle a^p - b^p\$. Specifically:

\$\displaystyle a^{pq} - b^{pq} = (a^p-b^p)(a^{p(q-1)} + a^{p(q-2)}b^p + a^{p(q-3)}b^{2p} + ..+a^pb^{(q-2)p} + b^{(q-1)p}\$

Therefore \$\displaystyle a^{pq} - 3^{pq}\$ cannot be prime unless \$\displaystyle a^p-3^p = 1\$, and that can only happen if a = 4 and p=1.
• Sep 17th 2011, 12:19 AM
pkaff
Re: Primes
Thanks for such a quick answer! That helps alot, thanks.
• Sep 21st 2011, 03:39 AM
pkaff
Re: Primes
Hi again!

A follow-up question on the problem above. Is the following true:

a^(pq)-b^(pq)=(a^p)^q-(b^p)^q=(a^p-b^p)(...)

If yes: how can you know that for sure?
If no: how do you go from q^(pq)-b^(pq) to (a^p-b^p)(...)

Thanks!
• Sep 21st 2011, 04:54 AM
ebaines
Re: Primes
You can divide \$\displaystyle a^p - b^p \$ into \$\displaystyle a^{pq}-b^{pq}\$ using long division to get the result that I showed earlier. And yes, it is true that
\$\displaystyle a^{pq} - b^{pq} = (a^p)^q-(b^p)^q = (a^p-b^p)(...) \$, but you still need to use long division to find out what goes in the (...) part.
• Sep 21st 2011, 05:21 AM
pkaff
Re: Primes
Quote:

Originally Posted by ebaines
You can divide \$\displaystyle a^p - b^p \$ into \$\displaystyle a^{pq}-b^{pq}\$ using long division to get the result that I showed earlier. And yes, it is true that
\$\displaystyle a^{pq} - b^{pq} = (a^p)^q-(b^p)^q = (a^p-b^p)(...) \$, but you still need to use long division to find out what goes in the (...) part.

Sorry I was being unclear. I understand that it is true, but is it enough to say that a^{pq} - b^{pq} = (a^p)^q-(b^p)^q to clarify that (a^p-b^p) is in fact a factor? Since I'm unsure I think it's not ^^. Could you maybe explain a bit further in what way the rewriting (a^p)^q-(b^p)^q leads to the answer? Unless it's not done by that rewriting ^^

/Pkaff
• Sep 21st 2011, 05:59 AM
ebaines
Re: Primes
Quote:

Originally Posted by pkaff
Sorry I was being unclear. I understand that it is true, but is it enough to say that a^{pq} - b^{pq} = (a^p)^q-(b^p)^q to clarify that (a^p-b^p) is in fact a factor?

No - it's not automatically obvious (at least not to me).

Quote:

Originally Posted by pkaff
Since I'm unsure I think it's not ^^. Could you maybe explain a bit further in what way the rewriting (a^p)^q-(b^p)^q leads to the answer? Unless it's not done by that rewriting ^^

You can show that \$\displaystyle x^q - y^q = (x-y)(x^{q-1} +x^{q-2}y + x^{q-2}y^2 + ...+ y^{q-1})\$. So replace x by \$\displaystyle a^p\$ and y by \$\displaystyle b^p\$ to get the result.
• Sep 21st 2011, 06:48 AM
pkaff
Re: Primes
Quote:

Originally Posted by ebaines
So replace x by \$\displaystyle a^p\$ and y by \$\displaystyle b^p\$ to get the result.

Lol obviously xP... I already did the x^n-y^n thingy, and if you replace x with x^p it will look like (x^p)^n, aswell as x^p instead of "x". I'm rambeling, thanks for the help!