# Problem about prime

1. Jan 27, 2012

### Selfluminous

1. The problem statement, all variables and given/known data
if 1 + 2^n + 4^n is a prime number then n is a power of 3

2. Relevant equations

3. The attempt at a solution
If n is not a power of 3, i need to show that we can factorize 1 + 2^n + 4^n
But im not really sure what should n be if it is not a power of 3 ?
is it 3^k*m where m ≥ 1, k≥0
this direction doesnt seem to work

there must be some trick here.

2. Jan 28, 2012

### Bacle2

Seems like you could express the terms as terms of a sequence, and find a pattern/standard formula for the sum. Do you see it?

3. Jan 28, 2012

### Selfluminous

i can easily find the formula for the sum of an = 1 + 2n + 4n. But i don't really see the connection of it with an being prime...

4. Jan 28, 2012

### Bacle2

Well, the general formula for the sum may tell you if there are general factors or not, e.g.,

if the general factoring of c is a2-b2, and a-b>1, then c cannot be a prime. Can you express the sum as a product? That was my idea.

5. Jan 28, 2012

### Selfluminous

lol i can express the sum as $\frac{8^n-1}{2^n-1}$
dont know what to do next

6. Jan 28, 2012

### Joffan

$m(n)=1+2^{n}+4^{n}$

If you could show that for k=1 mod 3 and for k=2 mod 3, m(n) divides m(kn), you can infer the result.

$m(2n)=(1+2^{n}+4^{n})(1-2^{n}+4^{n})$ gets things started.

7. Jan 28, 2012

### Selfluminous

$m(n)=1+2^n+4^n$
we need to show that
1. if the prime factorization of n contains any thing different from 3, m(n) would not be prime :
--> somehow we need to factorize:
m((3k+1)p) =

m((3k+2)p) =
where p is the other part in n's prime factorization.

from your suggestion, m(2p) is factorized,....
maybe i should do induction on k ?

2. Also we need to prove that when n is power of 3, m(n) is a prime :(

8. Jan 28, 2012

### tiny-tim

Hi Selfluminous!

try using the X2 button just above the Reply box
(I haven't worked out how to do this , but …)

two thing occur to me for a question like this:

i] see what you have to prove: if any number has a divisor other than 3, including itself, then 1 + 2n + 4n is not prime…

so try it first for n prime (other than 3)

ii] it often helps to calculate it for small primes first, just in case you pick up a clue

in this case, p=5 gives 1 + 32 + 1024 = 1057 = 7*151 …

what do p = 7 and 11 give?

9. Jan 28, 2012

### morphism

Consider the expression mod 7. Note that the powers of 2 and 4 cycle... Can you detect a pattern?

You should be able to prove that if n isn't divisible by 3, then 1+2^n+4^n = 0 mod 7. Now there's the issue of dealing with the case when n is divisible by 3...

A more high-level approach would be to consider the general polynomial 1+x^n+x^{2n} (here we're dealing with x=2). If n isn't divisible by 3, then x=exp(2pi i/3) is a root (because x^n and x^{2n} will be distinct 3rd roots of unity != 1, and the sum of all three 3rd roots of unity is equal to zero). It follows that the 1+x+x^2, the minimal polynomial of exp(2pi i/3), divides 1+x^n+x^{2n}. So if we write $n=3^k m$ with $3 \nmid m$ then, by our previous reasoning, $1+x^n+x^{2n}=1+(x^{3^k})^m+(x^{3^k})^{2m}$ has a nontrivial factor whenever $m\neq 1$.

Last edited: Jan 28, 2012
10. Jan 28, 2012

### Selfluminous

as you have suggested, it appears that 7 divides $1+2^n+4^n$ when n is not divisible by 3
also $1+2^n+4^n = \frac{7(2^{3(n-1)}+2^{3(n-2)}+...+1)}{ 2^{n -1}+...+1}$
still working on it

11. Jan 28, 2012

### Joffan

Yes, induction. Show that m(n) divides m((k+3)n)-m(kn)

Regarding your #2: we do NOT need to prove that when n is power of 3, m(n) is a prime. We need to prove that when n is NOT a power of 3, m(n) is composite.

Note that the above conversation is consistent with m(1)=7

Last edited: Jan 28, 2012
12. Jan 28, 2012

### tiny-tim

oh, that's brilliant!

ok, now rewrite the RHS as something times (8n - 1)/(2n - 1)

13. Jan 28, 2012

### Joffan

... although of course 27 has a divisor other than {1,3,27} - it is divisible by 9, which is not 3.

Actually what you have to prove is that if n has any factor >1 that is not a multiple of 3, m(n) is not prime. Which is why I was talking about k=(1 or 2) mod 3.

You might find this useful... my home-brewed factor-finder in Excel doesn't like bigger numbers, I'm afraid, although I'm aware that there are better facilities around. Still it gave me lots of useful clues.

\begin{array}{c | c | l l l l l }
n & m(n) & factors \\
1 & 7 & 7 \\
2 & 21 & 3 & 7 \\
3 & 73 & 73 \\
4 & 273 & 3 & 7 & 13 \\
5 & 1057 & 7 & 151 \\
6 & 4161 & 3 & 19 & 73 \\
7 & 16513 & 7 & 7 & 337 \\
8 & 65793 & 3 & 7 & 13 & 241 \\
9 & 262657 & 262657 \\
10 & 1049601 & 3 & 7 & 151 & 331 \\
11 & 4196353 & 7 & 599479 \\
12 & 16781313 & 3 & 19 & 37 & 73 & 109 \\
13 & 67117057 & 7 & 79 & 121369 \\
14 & 268451841 & 3 & 7 & 7 & 337 & 5419 \\
15 & 1073774593 & 73 & 631 & 23311 \\
\end{array}

Last edited: Jan 28, 2012
14. Jan 28, 2012

### Selfluminous

but the right hand side is (8n - 1)/(2n - 1)
i got to that point before, but couldn't do much due to my lack of math skills. Is there some trick here ?

15. Jan 29, 2012

### Joffan

Proof plan. collected:
• Show that $m(n)$ divides $m(2n)$
• Show than $m(n)$ divides $m((k+3)n) - m(kn)$
• Infer by induction that $m(n)$ divides all $m(kn)$ where $k>1, k\equiv(1 \text{ or } 2) \text{ mod } 3$
• Note that all numbers other than powers of 3 have such a factor
• Infer that $m(n)$ can only be prime when $n$ is a power of 3.

Last edited: Jan 29, 2012
16. Jan 30, 2012

### Bacle2

Use that (an-bn)=(a-b)(an-1+an-2b+..

..+abn-2+bn-1). Then

(8n-1)/(2n-1)=

[(23-1)(2n-1+2n-2+...+2+1)]/(2n-1)

And show for n=3k+1, n=3k+2 (which will happen when n≠ 3k ), that

2n-1 does not contain factors of 7 . Then the factor 7 will remain there.

That shows necessary, but not sufficient, but it is a start.

17. Jan 31, 2012

### Bacle2

Let me make the point again:

If n is not a power of 3, then n=3k+1 , or n=3k+2 .

Now, for n=3k+1 ,

2n=23k+1=([23]k)(21)==

(congruent) (1k)21=2 mod7 , so 23k+1-1 == 1 mod7

Similar argument shows 23k+2-1 == 3 mod7 . So the factor 7, i.e.,

23-1 below will not cancel with a factor of 7 in 2n-1 , when

n=3k+1 or n=3k+2 , so 7 divides 1+2n+4n when n=3k+1 or n=3k+2

, i.e., when n is not a power of 3. The other part seems harder.

18. Feb 1, 2012

### Selfluminous

errm
how about (2m-1)|(2n-1) when m|n (also converse )
therefore if n is not divisible by 3, 2n-1 is not divisible by 23-1=7
Also, a(n)= 7*(8n-1+..+1)/(2n-1) is an integer so if 2n-1 is not divisble by 7 then 7|a(n) (when n is not divisible by 3)

When n is not a power of 3 and is divisible by 3, it can be written as: k*3m, k is not divisible by 3
and then...

Last edited: Feb 1, 2012
19. Feb 1, 2012

### Selfluminous

...we need to show that a(n)|a(kn) when k is not divisible by 3
i know that this is true, maybe rewrite a(kn)/a(n) in a certain way

$\frac{(8^{kn}-1)(2^{n}-1)}{(2^{kn}-1)(8^{n}-1)}=\frac{8^{(k-1)n}+...+1}{2^{(k-1)n}+...+1}$

ok after awhile i dont think this is a good direction

Last edited: Feb 1, 2012
20. Feb 1, 2012

### Selfluminous

how come i missed this post

a(n) = 4n+2n+1
we can check that :
a(n)|a(2n) (1)
a(n)|a(4n) (2)
also,
a(kn+3n)-a(kn) = 4kn+3n+2kn+3n-4kn-2kn = 4kn(43n-1) + 2kn(23n-1)
=2kn(23n-1)(...)
also a(n)= (23n-1)/(2n-1)
therefore a(n)|a((k+3)n)-a(kn) (3)
(1)(2) and (3), by induction we have a(n)|a(kn) when k is not divisible by 3

which means if a(n) is prime then n has to be power of 3

thanks everyone in this thread
let's move on to the next problem !