# I Primes and Polynomials

Tags:
1. Dec 25, 2017

### JimBob81345

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. Dec 25, 2017

### 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.

3. Dec 25, 2017

### 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.

4. Dec 26, 2017

### JimBob81345

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?

5. Dec 26, 2017

### JimBob81345

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?

6. Dec 26, 2017

### 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.

7. Dec 26, 2017

### 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
8. Dec 26, 2017

### JimBob81345

I still don't understand, can you be a little more detailed?

9. Dec 26, 2017

### 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

10. Dec 26, 2017

### JimBob81345

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
11. Dec 27, 2017

### 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.

12. Dec 27, 2017

### JimBob81345

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.

13. Dec 27, 2017

### Staff: Mentor

Your argument only rules out parabolas, not polynomials of any degree.

14. Dec 28, 2017

### JimBob81345

How would you prove it for polynomials of any degree?

15. Dec 28, 2017

### Staff: Mentor

Instead of degree 2, assume degree n and verify that all the steps can be generalized.

16. Dec 28, 2017

### JimBob81345

Does g(x) have to be a linear function?

17. Dec 28, 2017

### 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.

18. Dec 29, 2017

### JimBob81345

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
19. Dec 29, 2017

### Staff: Mentor

The prefactor is missing.

The last step is probably difficult if you want to prove it properly.

20. Dec 29, 2017

### JimBob81345

How do you suggest I approach it? It doesn't seem to be possible using the method you proved the degree 2 case