Prime Number Homework: If 1+2^n+4^n is Prime, n is Power of 3?

[Selfluminous]

Homework Statement

if 1 + 2^n + 4^n is a prime number then n is a power of 3

Homework Equations

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 I am 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 doesn't seem to work

there must be some trick here.

 

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

 

[Selfluminous]

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?

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

 

[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 a²-b², and a-b>1, then c cannot be a prime. Can you express the sum as a product? That was my idea.

 

[Selfluminous]

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 a²-b², and a-b>1, then c cannot be a prime. Can you express the sum as a product? That was my idea.

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

 

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

 

[Selfluminous]

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.

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

 

[tiny-tim]

Hi Selfluminous!

try using the X² button just above the Reply box

if 1 + 2^n + 4^n is a prime number then n is a power of 3

(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 + 2ⁿ + 4ⁿ 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?

 

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

 

[Selfluminous]

Hi Selfluminous!

try using the X² 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 + 2ⁿ + 4ⁿ 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?

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

 

[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

 

[tiny-tim]

1+2^n+4^n = \frac{7(2^{3(n-1)}+2^{3(n-2)}+...+1)}{ 2^{n -1}+...+1}
still working on it

oh, that's brilliant!

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

 

[Joffan]

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

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

 

[Selfluminous]

oh, that's brilliant!

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

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

 

[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&gt;1,<br /> 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.

 

[Bacle2]

My idea was this:

Use that (aⁿ-bⁿ)=(a-b)(a^n-1+a^n-2b+..

..+ab^n-2+b^n-1). Then

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

[(2³-1)(2^n-1+2^n-2+...+2+1)]/(2ⁿ-1)

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

2ⁿ-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.

 

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

2ⁿ=2^3k+1=([2³]^k)(2¹)==

(congruent) (1^k)2¹=2 mod7 , so 2^3k+1-1 == 1 mod7

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

2³-1 below will not cancel with a factor of 7 in 2ⁿ-1 , when

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

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

 

[Selfluminous]

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 ,

2ⁿ=2^3k+1=([2³]^k)(2¹)==

(congruent) (1^k)2¹=2 mod7 , so 2^3k+1-1 == 1 mod7

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

2³-1 below will not cancel with a factor of 7 in 2ⁿ-1 , when

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

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

errm
how about (2^m-1)|(2ⁿ-1) when m|n (also converse )
therefore if n is not divisible by 3, 2ⁿ-1 is not divisible by 2³-1=7
Also, a(n)= 7*(8^n-1+..+1)/(2ⁿ-1) is an integer so if 2ⁿ-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*3^m, k is not divisible by 3
and then...

 

[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 don't think this is a good direction

trying induction instead

 

[Selfluminous]

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&gt;1,<br /> 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.

how come i missed this post

a(n) = 4ⁿ+2ⁿ+1
we can check that :
a(n)|a(2n) (1)
a(n)|a(4n) (2)
also,
a(kn+3n)-a(kn) = 4^kn+3n+2^kn+3n-4^kn-2^kn = 4^kn(4³ⁿ-1) + 2^kn(2³ⁿ-1)
=2^kn(2³ⁿ-1)(...)
also a(n)= (2³ⁿ-1)/(2ⁿ-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 !

 

[Bacle2]

errm
how about (2^m-1)|(2ⁿ-1) when m|n (also converse )
therefore if n is not divisible by 3, 2ⁿ-1 is not divisible by 2³-1=7
Also, a(n)= 7*(8^n-1+..+1)/(2ⁿ-1) is an integer so if 2ⁿ-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*3^m, k is not divisible by 3
and then...

Sorry, I don't get your point; I tried to rewrite my post because I thought my first writing was poor/unclear.

 

[Selfluminous]

Sorry, I don't get your point; I tried to rewrite my post because I thought my first writing was poor/unclear.

at that time i proved 7|(4^n+2^n+1) when n is not divisible by 3, based on the fact that (2m-1)|(2n-1) when m|n
it doesn't matter now :D