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

  • Thread starter Selfluminous
  • Start date
  • Tags
    Prime
In summary: & 3 \times 7 \\3 & 71... & 71 \\4 & 213... & 3 \times 71 \\5 & 639... & 3^2 \times 71 \\6 & 1917... & 3^3 \times 71 \\7 & 5751... & 3^3 \times 7 \times 71 \\8 & 17253... & 3^3 \times 71 \times 71 \\9 & 51759... & 3^4 \times 71 \times 71 \\10 & 155277... & 3^4 \times 71 \times 71 \\11 & 465831... & 3
  • #1
Selfluminous
18
0

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.
 
Physics news on Phys.org
  • #2
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
Bacle2 said:
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 an = 1 + 2n + 4n. But i don't really see the connection of it with an being prime...
 
  • #4
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
Bacle2 said:
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.

lol i can express the sum as [itex]\frac{8^n-1}{2^n-1}[/itex]
dont know what to do next
 
  • #6
[itex]m(n)=1+2^{n}+4^{n}[/itex]

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.

[itex]m(2n)=(1+2^{n}+4^{n})(1-2^{n}+4^{n})[/itex] gets things started.
 
  • #7
Joffan said:
[itex]m(n)=1+2^{n}+4^{n}[/itex]

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.

[itex]m(2n)=(1+2^{n}+4^{n})(1-2^{n}+4^{n})[/itex] gets things started.

[itex]m(n)=1+2^n+4^n[/itex]
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
Hi Selfluminous! :smile:

try using the X2 button just above the Reply box :wink:
Selfluminous said:
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 :redface:, 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 :wink:

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

what do p = 7 and 11 give? :smile:
 
  • #9
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 [itex]n=3^k m[/itex] with [itex]3 \nmid m[/itex] then, by our previous reasoning, [itex]1+x^n+x^{2n}=1+(x^{3^k})^m+(x^{3^k})^{2m}[/itex] has a nontrivial factor whenever [itex]m\neq 1[/itex].
 
Last edited:
  • #10
tiny-tim said:
Hi Selfluminous! :smile:

try using the X2 button just above the Reply box :wink:


(I haven't worked out how to do this :redface:, 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 :wink:

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

what do p = 7 and 11 give? :smile:
as you have suggested, it appears that 7 divides [itex]1+2^n+4^n[/itex] when n is not divisible by 3
also [itex] 1+2^n+4^n = \frac{7(2^{3(n-1)}+2^{3(n-2)}+...+1)}{ 2^{n -1}+...+1} [/itex]
still working on it
 
  • #11
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:
  • #12
Selfluminous said:
[itex] 1+2^n+4^n = \frac{7(2^{3(n-1)}+2^{3(n-2)}+...+1)}{ 2^{n -1}+...+1} [/itex]
still working on it

oh, that's brilliant! :smile:

ok, now rewrite the RHS as something times (8n - 1)/(2n - 1) :wink:
 
  • #13
tiny-tim said:
see what you have to prove: if any number has a divisor other than 3, including itself, then 1 + 2n + 4n 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}
 
Last edited:
  • #14
tiny-tim said:
oh, that's brilliant! :smile:

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

:confused: 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
Proof plan. collected:
  • Show that [itex]m(n)[/itex] divides [itex]m(2n)[/itex]
  • Show than [itex]m(n)[/itex] divides [itex]m((k+3)n) - m(kn)[/itex]
  • Infer by induction that [itex]m(n)[/itex] divides all [itex]m(kn)[/itex] where [itex]k>1,
    k\equiv(1 \text{ or } 2) \text{ mod } 3[/itex]
  • Note that all numbers other than powers of 3 have such a factor
  • Infer that [itex]m(n)[/itex] can only be prime when [itex]n[/itex] is a power of 3.
 
Last edited:
  • #16
My idea was this:

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
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
Bacle2 said:
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.
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:
  • #19
...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

[itex]\frac{(8^{kn}-1)(2^{n}-1)}{(2^{kn}-1)(8^{n}-1)}=\frac{8^{(k-1)n}+...+1}{2^{(k-1)n}+...+1}[/itex]ok after awhile i don't think this is a good direction

trying induction instead
 
Last edited:
  • #20
Joffan said:
Proof plan. collected:
  • Show that [itex]m(n)[/itex] divides [itex]m(2n)[/itex]
  • Show than [itex]m(n)[/itex] divides [itex]m((k+3)n) - m(kn)[/itex]
  • Infer by induction that [itex]m(n)[/itex] divides all [itex]m(kn)[/itex] where [itex]k>1,
    k\equiv(1 \text{ or } 2) \text{ mod } 3[/itex]
  • Note that all numbers other than powers of 3 have such a factor
  • Infer that [itex]m(n)[/itex] can only be prime when [itex]n[/itex] is a power of 3.
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 !
 
  • #21
Selfluminous said:
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...

Sorry, I don't get your point; I tried to rewrite my post because I thought my first writing was poor/unclear.
 
  • #22
Bacle2 said:
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
 

1. What is a prime number?

A prime number is a positive integer that is only divisible by 1 and itself. Examples of prime numbers include 2, 3, 5, 7, 11, and so on.

2. How do you determine if a number is prime?

One way to determine if a number is prime is by checking if it is only divisible by 1 and itself. Another way is by using the Sieve of Eratosthenes, a method of finding all prime numbers up to a given number by eliminating all the multiples of each prime number.

3. What does the equation 1+2^n+4^n represent?

The equation 1+2^n+4^n represents a form of the Lucas-Lehmer sequence, which is a sequence of numbers that can generate prime numbers. In this case, n is the power of 3, meaning that the formula will only generate prime numbers when n is a power of 3.

4. Why is it important for n to be a power of 3 in the equation 1+2^n+4^n?

It is important for n to be a power of 3 because this ensures that the resulting number is a prime number. When n is not a power of 3, the resulting number may be composite (divisible by more than 2 numbers) and therefore not a prime number.

5. How can this equation be useful in mathematics or other fields?

This equation can be useful in mathematics for generating prime numbers and studying their patterns and properties. It can also be used in cryptography for creating secure algorithms. Additionally, it can be applied in computer science for optimizing algorithms and in statistics for analyzing data sets.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
Replies
18
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
1K
Back
Top