Genady Posted November 9 Posted November 9 (edited) Find a polynomial function, f(n) whose output is a prime number for any input number, n. Edited November 9 by Genady
joigus Posted November 9 Posted November 9 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? 1
Genady Posted November 10 Author Posted November 10 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 Posted November 10 Posted November 10 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 Posted November 10 Author Posted November 10 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 a0+a1n+...+aqnq. It is divisible by n=a0. So, it is not prime for this n, if a0 is greater than 1. I leave it to you to prove that it is not prime when a0=1 as well. 1
joigus Posted November 15 Posted November 15 (edited) 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 a0+a1n+...+aqnq. It is divisible by n=a0. So, it is not prime for this n, if a0 is greater than 1. I leave it to you to prove that it is not prime when a0=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 November 15 by joigus minor correction
Genady Posted November 15 Author Posted November 15 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\). 1
joigus Posted November 15 Posted November 15 (edited) 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 November 15 by joigus correction
sethoflagos Posted November 17 Posted November 17 Curious possibility: Spoiler Consider F(x+y) = a0 + a1(x+y) + a2(x+y)2 + ... + aq(x+y)q Seperate expansion terms into those that are independent of y and those which are not F(x+y) = a0 + a1x + a2x2 + ... + aqxq + 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)) 1
Genady Posted November 17 Author Posted November 17 (edited) 2 hours ago, sethoflagos said: Curious possibility: Reveal hidden contents Consider F(x+y) = a0 + a1(x+y) + a2(x+y)2 + ... + aq(x+y)q Seperate expansion terms into those that are independent of y and those which are not F(x+y) = a0 + a1x + a2x2 + ... + aqxq + 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 November 17 by Genady
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now