Results 1 to 13 of 13

Math Help - A polynomial that is always prime?

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    43

    A polynomial that is always prime?

    Does there exist an f(x) minimum first-degree polynomial with integer coefficients, such that for any x integer number, f(x) is prime?

    Any help would be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by doug View Post
    Does there exist an f(x) minimum first-degree polynomial with integer coefficients, such that for any x integer number, f(x) is prime?

    Any help would be appreciated!
    No!
    Proof by reductio ad impossibile.
    Suppose that there is exist such polynomial f(n).

    f(n)=a_kn^k+...+a_1n+a_0

    Let now n=n_0 such that f(n_0)=p, when p is prime.

    Let now be t\in\mathbb{N}, and let us look at:

    f(n_0+tp)=a_k(n_0+tp)^k+...+a_1(n_0+tp)+a_0

    =a_kn_0^k+...+a_1n_0+a_0+pQ(t)

    =f(n_0)+pQ(t)

    =p+pQ(t)=p(1+Q(t))

    Q(t) is polynomial with integer coefficients.

    So, p\mid{f(n_0+tp)}, but f(n) is generates primes only, therefor f(n_0+tp)=p for all integer t.

    Now, from the fact that polynomial can't have the same value more than k times, we get the contradiction!



    Here some interesting polynomials:

    f(n)=110,437+13,860n when n=0,1,...,10 then f(n) is prime...

    Also(famous one):

    f(n)=n^2+n+41
    Last edited by Also sprach Zarathustra; October 27th 2010 at 12:54 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by doug View Post
    Does there exist an f(x) minimum first-degree polynomial with integer coefficients, such that for any x integer number, f(x) is prime?

    Any help would be appreciated!
    If such a function existed, it would always generate prime numbers. Do some research, does that result seem reasonable?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2010
    Posts
    43
    Quote Originally Posted by Also sprach Zarathustra View Post
    No!
    Proof by reductio ad impossibile.
    Suppose that there is exist such polynomial f(n).

    f(n)=a_kn^k+...+a_1n+a_0

    Let now n=n_0 such that f(n_0)=p, when p is prime.

    Let now be t\in\mathbb{N}, and let us look at:

    f(n_0+tp)=a_k(n_0+tp)^k+...+a_1(n_0+tp)+a_0

    =a_kn_0^k+...+a_1n_0+a_0+pQ(t)

    =f(n_0)+pQ(t)

    =p+pQ(t)=p(1+Q(t))

    Q(t) is polynomial with integer coefficients.

    So, p\mid{f(n_0+tp)}, but f(n) is generates primes only, therefor f(n_0+tp)=p for all integer t.

    Now, from the fact that polynomial can't have the same value more than k times, we get the contradiction!



    Here some interesting polynomials:

    f(n)=110,437+13,860n when n=0,1,...,10 then f(n) is prime...

    Also(famous one):

    f(n)=n^2+n+41
    Thank you so much. Your answer is more than fantastic!
    Thanks again!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by doug View Post
    Thank you so much. Your answer is more than fantastic!
    Thanks again!
    You are welcome!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,453
    Thanks
    1868
    Quote Originally Posted by doug View Post
    Thank you so much. Your answer is more than fantastic!
    Thanks again!
    Was this a jab at mr fantastic??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    To OP:

    don't say "yes"!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Sep 2010
    Posts
    43
    Quote Originally Posted by HallsofIvy View Post
    Was this a jab at mr fantastic??
    No, actually it wasn't. It wasn't conscious. I just really appreciated that Also sprach Zarathustra was so kind and wrote a very clear prove.
    But it might be a jab... subconsciously
    I really hope that mr fantastic won't get sore.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by mr fantastic View Post
    If such a function existed, it would always generate prime numbers. Do some research, does that result seem reasonable?
    There are many such functions. For example, Riemann gave an explicit formula for the number of primes less than x. A prime-yielding formula can be easily constructed from this.

    There is also a positive constant A, known as Mill's constant, such that \lfloor A^{3^n}\rfloor is prime for every n. It's about 1.306... if the Riemann hypothesis is correct. It yields the sequence of primes 2, 11, 1361, 2521008887, ....

    Also, the simple recurrence relation a_1=7, a_{n+1}=a_n+\mbox{gcd}(a_n,n) generates only primes.

    There is no reason why any given kind of "formula for primes" could not exist. It is a popular belief that there is no such thing; I've even heard non-mathematicians claim it, as if it were some kind of established result. I don't believe the OP was asking a silly question at all, because there do exist many such formulae.

    Here's another proof that no non-constant polynomial with integer coefficients yields only primes. Let c=f(0) be the constant term of this polynomial. It's quite easy to see that f(mc) is divisible by c for every integer m.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by Bruno J. View Post
    Here's another proof that no non-constant polynomial with integer coefficients yields only primes. Let c=f(0) be the constant term of this polynomial. It's quite easy to see that f(mc) is divisible by c for every integer m.
    To Bruno J.,
    I think it's a hasty assersion. Indeed c divides f(mc) for every integer m . But this only shows that a non-constant polynomial that yields only primes must have c=1.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by melese View Post
    To Bruno J.,
    I think it's a hasty assersion. Indeed c divides f(mc) for every integer m . But this only show that a polynomial that yields only primes must have c=1.
    But f(0)=c is assumed to be prime!
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by Bruno J. View Post
    But f(0)=c is assumed to be prime!
    But this is a special case that rules out only non-constant polynomials for which f(0)=c is prime. The main result that Also sprach Zarathustra proved holds for any non-constant polynomial, whether c is or isn't prime.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by melese View Post
    But this is a special case that rules out only non-constant polynomials for which f(0)=c is prime. The main result that Also sprach Zarathustra proved holds for any non-constant polynomial, whether c is or isn't prime.
    Granted!
    What I wrote still solves the original question though.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. Prime polynomial
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 1st 2010, 01:07 AM
  3. Replies: 0
    Last Post: October 6th 2009, 04:52 PM
  4. Need help with prime polynomial question!
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 4th 2009, 05:07 AM
  5. Prime Degree Polynomial
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: August 2nd 2007, 01:22 PM

Search Tags


/mathhelpforum @mathhelpforum