1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problem about prime

  1. Jan 27, 2012 #1
    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. jcsd
  3. Jan 28, 2012 #2

    Bacle2

    User Avatar
    Science Advisor

    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?
     
  4. Jan 28, 2012 #3
    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...
     
  5. Jan 28, 2012 #4

    Bacle2

    User Avatar
    Science Advisor

    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.
     
  6. Jan 28, 2012 #5
    lol i can express the sum as [itex]\frac{8^n-1}{2^n-1}[/itex]
    dont know what to do next
     
  7. Jan 28, 2012 #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.
     
  8. Jan 28, 2012 #7
    [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 :(
     
  9. Jan 28, 2012 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    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:
     
  10. Jan 28, 2012 #9

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    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: Jan 28, 2012
  11. Jan 28, 2012 #10
    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
     
  12. Jan 28, 2012 #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: Jan 28, 2012
  13. Jan 28, 2012 #12

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    oh, that's brilliant! :smile:

    ok, now rewrite the RHS as something times (8n - 1)/(2n - 1) :wink:
     
  14. Jan 28, 2012 #13
    ... 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
  15. Jan 28, 2012 #14
    :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 ?
     
  16. Jan 29, 2012 #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: Jan 29, 2012
  17. Jan 30, 2012 #16

    Bacle2

    User Avatar
    Science Advisor

    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.
     
  18. Jan 31, 2012 #17

    Bacle2

    User Avatar
    Science Advisor

    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.
     
  19. Feb 1, 2012 #18
    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
  20. Feb 1, 2012 #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 dont think this is a good direction

    trying induction instead
     
    Last edited: Feb 1, 2012
  21. Feb 1, 2012 #20
    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 !
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Problem about prime
  1. Proof about primes. (Replies: 7)

  2. Proof about primes (Replies: 1)

Loading...