1. Limited time only! Sign up for a free 30min personal 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!

I Primes and Polynomials

  1. Dec 25, 2017 #1
    Does there exist a polynomial P(x) with rational coefficients such that for every composite number x, P(x) takes an integer value and for every prime number x, P(x) does not take on an integer value?

    Can someone please guide me in the right direction? I've tried to consider the roots of the polynomial and its relation with the input but without luck.
     
    Last edited by a moderator: Dec 25, 2017
  2. jcsd
  3. Dec 25, 2017 #2

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Assume there is such a polynomial of degree n. Then there is also one where P(x)=0 for the first n primes. This fully determines the polynomial up to a constant - and I don’t see how this constant could be chosen to work.

    Edit: Wait, I reversed the integer and non integer value, but the argument works for both.
     
  4. Dec 25, 2017 #3

    Mark44

    Staff: Mentor

    Is this what you mean?
    ... for every composite number x, P(x) is an integer, and for every prime number x, P(x) is not an integer?

    Your wording of "takes an integer value" and "does not take on an integer value" was confusing to me.
     
  5. Dec 26, 2017 #4
    I am confused by what you are saying. If there exists a polynomial of degree n then yes there also exists a polynomial with the roots being the first n primes. But how does this determine the polynomial to be a constant?
     
  6. Dec 26, 2017 #5
    A positive integer is part of the set A if the digits in its decimal representation form a non-decreasing sequence from left to right. For example, 149 and 1223 are both in A but 745 is not. Does there exist a polynomial P(x) with rational coefficients such that if x is a number in A, then P(x) is an integer and if x is not a number in A, P(x) is not an integer?

    My Observations:
    - If this polynomial exists then there exists an infinite number of polynomials which satisfy the above condition.
    - The roots of P(x) are number for which it equals 0 (an integer), thus, its roots (if the are positive integers) must be of the set A.
    -

    Should I research the properties of numbers in the set A before further attempting this problem?
     
  7. Dec 26, 2017 #6

    Mark44

    Staff: Mentor

    @mfb didn't say that the polynomial was a constant -- he said "up to a constant." For example, the quadratic polynomial y = a(x - 1)(x - 2) has 1 and 2 as its roots, independent of the value of a.
     
  8. Dec 26, 2017 #7

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Or, more explicitly: Every polynomial of degree 2 with these roots can be expressed as a(x-1)(x-2).

    Edit: I merged the other thread into this one as the problem is very similar. See post #5.
     
    Last edited: Dec 26, 2017
  9. Dec 26, 2017 #8
    I still don't understand, can you be a little more detailed?
     
  10. Dec 26, 2017 #9

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Here is an example.
    Let's try find a polynomial function of degree 2 (a parabola) that has integer values exactly at x=1, 2 and 3. Assume there is such a function f(x).
    We can find a linear function g(x) such that g(1)=f(1) and g(2)=f(2), namely g(x)=(f(2)-f(1))x + 2f(1)-f(2). Note that both coefficients are integers [note*], and g(x) is an integer for every integer x.

    If f(x) has the properties we want, then h(x)=f(x)-g(x) has it as well, because we are only subtracting integers. We also know h(1)=h(2)=0. Every parabola with the last property can be expressed as h(x)=a(x-1)(x-2) for some a.

    Let's plug in x=3: h(3)=2a. We want this to be an integer. That is possible, of course, but what happens if we look at other values? h(4)=6a. No matter which a we choose, if 2a is an integer, then 6a=3*2a will be an integer as well. This contradicts our requirement that our function has integer values only for 1,2,3.

    I used three specific points here (1,2,3), but you can generalize this to any three points, e.g. 1,4,6 or 2,3,5. Similarly, you can ask for a polynomial function of degree 3 that has integer values only at 1,4,6,8 or 2,3,5,7 (see above: It doesn't matter if you take the set of primes or the set of non-primes).
    I picked the degree first here, but that doesn't matter. If there is a polynomial function that has integer values only at prime numbers, then it has some degree n, and we can look at the first n non-prime numbers (or prime numbers) to determine the polynomial up to a constant (the "a" from above). While you have some choice in the constant, I can't see how any choice would lead to the correct result for every number. This is not a strict mathematical proof, but I'm quite confident that there is no such polynomial function.

    *note: this doesn't generalize that nicely, but the coefficients stay rational with small denominators, and g(x) keeps getting integer values elsewhere
     
  11. Dec 26, 2017 #10
    Thank you for the clarification. I have a related problem:
    Suppose a Polynomial P(x) (with rational coefficients) exists such that for every input that is prime, P(x) outputs an integer. Does P(x) have to output an integer for every integer inputted or can you input some non-prime integer in P(x) so that the output is not prime?

    In other words
    Prime --> P(x) --> Integer
    Is it possible for the following to happen? (Even for one number)
    Non-prime --> P(x) --> Non-integer
     
    Last edited by a moderator: Dec 26, 2017
  12. Dec 27, 2017 #11

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    That is a weaker problem than the original one.

    1/9 (x-1)2(x-2)2(x-3) is zero for x=1, 2 and 3, it is an integer if x has remainder 1 or 2 when divided by 3 (which applies to all primes apart from 3), and it is not an integer for x=6 (where it is 400/3), x=9, x=12, and all other multiples of three that don't follow the pattern 9n+3.

    That makes a nice math puzzle.

    Edit, easier:

    1/4 (x-1)2(x-2) is zero for x=1 and x=2, an integer for all odd x and not an integer for x=4n for all integers n.
     
  13. Dec 27, 2017 #12
    A positive integer is part of the set A if the digits in its decimal representation form a non-decreasing sequence from left to right. For example, 149 and 1223 are both in A but 745 is not. Suppose a polynomial P(x) exists so that it outputs an integer for every input which is in the set A. Does P(x) have to output an integer for every integer inputted?

    Let me try this by myself:
    I think the answer is yes.
    Assume that such a polynomial exists, f(x). Now say another linear function g(x) with integral coefficients exists so that f(11) = g(11) and f(12) = g(12) (11 and 12 are the smallest numbers in the set A.) Let's say now we let h(x) = f(x) - g(x). h(x) has the same properties as f(x) since we are just subtracting integers. We know that h(11) = h(12) = 0. So h(x) = a(x-11)(x-12). For x=13, h(x) = 2a which we want to be an integer. However, if we plug in x=21 we get h(21) = 90a which will be an integer if 2a is an integer. We can repeat this for every integer not in A. Thus such a polynomial cannot exist.
     
  14. Dec 27, 2017 #13

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Your argument only rules out parabolas, not polynomials of any degree.
     
  15. Dec 28, 2017 #14
    How would you prove it for polynomials of any degree?
     
  16. Dec 28, 2017 #15

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Instead of degree 2, assume degree n and verify that all the steps can be generalized.
     
  17. Dec 28, 2017 #16
    Does g(x) have to be a linear function?
     
  18. Dec 28, 2017 #17

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    In general it cannot be a linear function. You need a polynomial of grade n-1 to get n roots of f(x)-g(x) at the places where you want them.
     
  19. Dec 29, 2017 #18
    I have h(x) = a(x-y_1)(x-y_2)...(x-y_n) where y_k is the k-th number in the set A. I can't seem to progress further.

    edit: fixed
     
    Last edited by a moderator: Dec 29, 2017
  20. Dec 29, 2017 #19

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    The prefactor is missing.

    The last step is probably difficult if you want to prove it properly.
     
  21. Dec 29, 2017 #20
    How do you suggest I approach it? It doesn't seem to be possible using the method you proved the degree 2 case
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Loading...