Prime generating polynomial

[Genady]

Find a polynomial function, f(n) whose output is a prime number for any input number, n.

Edited November 9 by Genady

[joigus]

Spoiler

p(x)=2

P(x) is a polynomial

2 is prime

qed.

------------

I'm assuming you don't mean that!

I'm assuming you mean degree(p)>0, and n is integer or rational?

 

[Genady]

1 hour ago, joigus said:

  Reveal hidden contents

p(x)=2

P(x) is a polynomial

2 is prime

qed.

------------

I'm assuming you don't mean that!

I'm assuming you mean degree(p)>0, and n is integer or rational?

 

I mean that. +1. As a bonus exercise, prove that it is the only answer.

[joigus]

Oh, I'm not very good at number theory. I would have to review some related stuff, like the Euclidean algorithm, divisibility criteria, etc, and see if some of the central ideas illuminate me. But let me try to trim the statement a little bit. Is it:

Find a polynomial f(n) with 0<deg(f)<infinity, such that f(n) is prime for all n in the integers?

Of course, it'd be the integers. Sorry for mentioning the rationals.

Something doesn't seem right, unless you set a bound for n.

[Genady]

7 minutes ago, joigus said:

a polynomial f(n) with 0<deg(f)<infinity

Yes.

 

8 minutes ago, joigus said:

prime for all n in the integers

It is easy to show that such a polynomial does not exist for not integer n. So, yes, the question can be clarified: n and all coefficients of the polynomial being integers.

 

9 minutes ago, joigus said:

number theory

It is not needed for this puzzle. Here is almost complete proof:

Spoiler

Take a polynomial a₀+a₁n+...+a_qn^q. It is divisible by n=a₀. So, it is not prime for this n, if a₀ is greater than 1.

I leave it to you to prove that it is not prime when a₀=1 as well.

 

[joigus]

On 11/10/2024 at 2:11 PM, Genady said:

Yes.

 

It is easy to show that such a polynomial does not exist for not integer n. So, yes, the question can be clarified: n and all coefficients of the polynomial being integers.

 

It is not needed for this puzzle. Here is almost complete proof:

  Hide contents

Take a polynomial a₀+a₁n+...+a_qn^q. It is divisible by n=a₀. So, it is not prime for this n, if a₀ is greater than 1.

I leave it to you to prove that it is not prime when a₀=1 as well.

 

Ok. I finally really understood!! Somehow the proof I'm providing seems ugly to me. I'm sure there must be a simpler, more beautiful one.

Let me re-state the answer with some formal embellishments. I'm sorry that I'm such a stickler for formalism:

Spoiler

Prove that, for any polynomial function, \( f\left(n\right)=a_{0}+a_{1}n+\cdots+a_{q}n^{q}\ \), with \( q\geq1,\;a_{i},\;i=0,\cdots q;\;n\in\mathbb{Z} \), the only such function whose output is only a prime number is the 0-degree polynomial,

\[ f\left(n\right)=p \]

where \( p \) is a prime number.

Proof:

i) Assume \( a_{0}=0 \). Then trivially \( f\left(n\right)=n\left(a_{1}+\cdots+a_{q}n^{q-1}\right) \) and \( f\left(n\right) \) is not prime for any \( n>1 \)

ii) Assume \( \left|a_{0}\right|>1 \) 

Then,

\[ f\left(a_{0}\right)=a_{0}+a_{1}a_{0}+\cdots+a_{q}\left(a_{0}\right)^{q}=a_{0}\left(1+a_{1}+\cdots+a_{q}\left(a_{0}\right)^{q-1}\right) \]

Therefore, \( a_0 \) divides \( f\left(a_{0}\right) \) and the latter is not a prime.

iii) Assume \( a_{0}=1 \). And let \( n \) be any integer. Then,

\[ f\left(n\right)=1+a_{1}n+\cdots+a_{q}n^{q} \]

But \( f\left( n \right) = p \) with \( p \) some prime. That means p-1 is even for \( p>2 \). Therefore,

\[ 2k+a_{1}n+\cdots+a_{q}n^{q}=g\left( n \right)=0 \]

with \( k \) some integer. This means such \( n  \) must necessarily be a root of \( g\left( n \right) \) defined above. By the rational-root theorem, \( 2k \) must divide \( n \). 

Therefore, \( n \) is not prime. As the hypothesis of the theorem is that \( f\left( n \right) \) must be prime for all \( n \), this concludes the proof.

 

 

I hope I didn't make any silly mistake with the LaTeX. The possibility that p=2 is a silly one, because the theorem must be valid for all n. One can use many ideas to rule that one out.

 

Edited Friday at 01:44 PM by joigus
minor correction

[Genady]

If I'm not mistaken, there is an error in the last part:

Spoiler

52 minutes ago, joigus said:

By the rational-root theorem, 2k must divide n. 

I think that by the rational-root theorem, it is rather n must divide \(2k\).

[joigus]

28 minutes ago, Genady said:

If I'm not mistaken, there is an error in the last part:

  Hide contents

I think that by the rational-root theorem, it is rather n must divide 2k .

Aaaahh. Yes I'm sorry. So, it's either,

Got that wrong. Sorry.

Edited Friday at 03:01 PM by joigus
correction

[sethoflagos]

Curious possibility:

Spoiler

Consider F(x+y) = a₀ + a₁(x+y) + a₂(x+y)² + ... + a_q(x+y)^q

Seperate expansion terms into those that are independent of y and those which are not

 F(x+y) = a₀ + a₁x + a₂x² + ... + a_qx^q + y*[integer (q-1) order polynomial in y]

            = F(x) + y*G(x,y)

What happens if we let y = k*F(x)?     k = arbitrary positive integer

F(x) may well be a prime but this appears to disqualify F(x + k*F(x))

 

[Genady]

2 hours ago, sethoflagos said:

Curious possibility:

  Reveal hidden contents

Consider F(x+y) = a₀ + a₁(x+y) + a₂(x+y)² + ... + a_q(x+y)^q

Seperate expansion terms into those that are independent of y and those which are not

 F(x+y) = a₀ + a₁x + a₂x² + ... + a_qx^q + y*[integer (q-1) order polynomial in y]

            = F(x) + y*G(x,y)

What happens if we let y = k*F(x)?     k = arbitrary positive integer

F(x) may well be a prime but this appears to disqualify F(x + k*F(x))

 

Yes! +1.

Edited 1 hour ago by Genady