Results 1 to 15 of 15
Like Tree10Thanks
  • 2 Post By SlipEternal
  • 1 Post By SlipEternal
  • 1 Post By Idea
  • 1 Post By Deveno
  • 1 Post By Idea
  • 1 Post By SlipEternal
  • 2 Post By johng
  • 1 Post By Deveno

Math Help - prime numbers

  1. #1
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    292

    Exclamation prime numbers

    Hi,

    just stuck up with questions on prime numbers.

    1) is 5^50 + 5^25 + 1 prime?

    2) for how many prime p, p+8 and p+14 also prime?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: prime numbers

    1) x^{50}+x^{25}+1 is divisible by x^2+x+1 in \Bbb{Z}[x], so no, it is not prime. 5^2+5+1=31 making that number divisible by 31.

    2) haven't thought about it
    Thanks from topsquark and nikhil
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    292

    Re: prime numbers

    could you explain how you figured x^2+x+1
    will divide the expression x^50+x^25+1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: prime numbers

    It is an expression of the form x^{2k}+x^{k}+1, which is divisible by x^2+x+1 for all k.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    280
    Thanks
    131

    Re: prime numbers

    Quote Originally Posted by SlipEternal View Post
    It is an expression of the form x^{2k}+x^{k}+1, which is divisible by x^2+x+1 for all k.
    Not true

    x^6+x^3+1 is not divisible by x^2+x+1
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: prime numbers

    Quote Originally Posted by SlipEternal View Post
    It is an expression of the form x^{2k}+x^{k}+1, which is divisible by x^2+x+1 for all k.
    It seems to me this is only true when k = 1 (mod 3). Fortunately, this is the case for k = 25.

    (Essentially, this happens because $x^2 + x + 1$ has "3 terms", so we want $2k + 1$ to be divisible by 3 (a general polynomial of degree n has n+1 terms)).
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: prime numbers

    Oh, I remembered proving something about it in my algebra class years ago. That must have been it. My memory is not what it used to be.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: prime numbers

    Quote Originally Posted by SlipEternal View Post
    Oh, I remembered proving something about it in my algebra class years ago. That must have been it. My memory is not what it used to be.
    Nor mine, amigo, nor mine.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    280
    Thanks
    131

    Re: prime numbers

    Quote Originally Posted by Deveno View Post
    It seems to me this is only true when k = 1 (mod 3). Fortunately, this is the case for k = 25.

    (Essentially, this happens because $x^2 + x + 1$ has "3 terms", so we want $2k + 1$ to be divisible by 3 (a general polynomial of degree n has n+1 terms)).
    It is true if k = 1 or 2 mod 3

    If k = 0 mod 3 then the division leaves a remainder = 3
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: prime numbers

    Quote Originally Posted by Idea View Post
    It is true if k = 1 or 2 mod 3

    If k = 0 mod 3 then the division leaves a remainder = 3
    Yup. I forgot we could "go two, skip one" and still have everything cancel in the $k = 3n + 2$ case. See above.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: prime numbers

    For (2), I would think it hard to prove there are only finitely many such primes. Usually,there is a proof that there are infinitely many such primes. So, I would attempt a proof by contradiction starting with the proposition that there are only finitely many primes p such that p+8 and p+14 are both prime. Have you attempted this at all?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    709
    Thanks
    294

    Re: prime numbers

    I was puzzled by the divisibility fact mentioned above. Since others might also have been puzzled, here's a proof:

    Thanks from topsquark and Deveno
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: prime numbers

    Quote Originally Posted by SlipEternal View Post
    For (2), I would think it hard to prove there are only finitely many such primes. Usually,there is a proof that there are infinitely many such primes. So, I would attempt a proof by contradiction starting with the proposition that there are only finitely many primes p such that p+8 and p+14 are both prime. Have you attempted this at all?
    Such a prime, if it exists, must be of the form $6k + 5$. To see this, note that:

    $6k$ is divisible by 6
    $6k + 2$ and $6k + 4$ are divisible by 2
    $6k + 3$ is divisible by 3.

    That leaves only $6k + 1$ and $6k + 5$. If we have $p = 6k+1$, then $p+8 = 6k + 9$ is divisible by 3.

    (this is really just saying $p$ is of the form $3n + 2$).
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jul 2014
    From
    Waterloo, ON
    Posts
    82
    Thanks
    18

    Re: prime numbers

    Or, for question 2, with the exception of p=5, try modulus 30 to weed out the 5's later on. XD
    All candidates listed: 5, 11, 17, 23, 29.
    Clearly 11+14=25, 17+8=25, and 5|25, so the first three can be weeded out.
    Now, check p if p=23 or 29 (mod 30)
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: prime numbers

    p=3,p+8=11,p+14=17 has p=3 not congruent to 5 (mod 6). So, that should be amended p=3 or p \equiv 5\pmod{6}

    Then, you can find congruences mod other primes.
    p=5 or
    p\equiv 1,4\pmod{5}

    p=7 or
    p\equiv 1,2,3,4,5\pmod{7}

    p=11 or
    p\equiv 1,2,4,5,6,7,9,10\pmod{11}

    p=13 or
    p\equiv 1,2,3,4,6,7,8,9,10,11\pmod{13}

    For primes q>13, either p=q or p{\not \equiv}q,q-8,q-14\pmod{q}

    Not sure if that helps at all.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 26th 2012, 06:09 PM
  2. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  3. prime numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 31st 2010, 10:44 AM
  4. Prime- numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2010, 12:04 AM
  5. prime numbers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 5th 2009, 08:39 AM

Search Tags


/mathhelpforum @mathhelpforum