Author |
Topic: Polynomial and Prime Numbers (Read 1844 times) |
|
Barukh
Guest
|
Prove that there does not exist a polynomial P(x) with integer coefficients such that P(n) for every natural n is a prime number.
|
|
 IP Logged |
|
|
|
Barukh
Guest
|
 |
Re: Polynomial and Prime Numbers
« Reply #2 on: Sep 17th, 2003, 2:02am » |
 Quote  Modify
 Remove
|
on Sep 17th, 2003, 1:18am, towr wrote:
Sorry, my fault: I forgot to add that the polynomial is not a constant.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
|
Re: Polynomial and Prime Numbers
« Reply #3 on: Sep 17th, 2003, 2:11am » |
Quote Modify
|
Very sneaky, Towr; although I would add that the word polynomial, which means 'many terms', is a little inappropriate for a constant function.
I've not managed to complete the proof, but maybe someone can finish it...
::
Let P(x)=a0+a1x+a2x2+...+ anxn.
For a0=0, P(x)[equiv]0 mod x, so P(x) is composite for all composite x.
Otherwise, P(a0)[equiv]0 mod a0.
For |a0|>1, P(ka0) is divisible by |a0|.
However, for |a0|=1, special consideration is required...
* hmm? *
::
|
| « Last Edit: Sep 17th, 2003, 2:15am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Polynomial and Prime Numbers
« Reply #4 on: Sep 17th, 2003, 3:15am » |
Quote Modify
|
::
suppose
P(x) = a0+a1x+a2x2+.....
is a polynomial such that for every x=n P(n) is prime
now suppose that for x=m,P(m)=p (a prime)
then,
p = a0+a1m+a2m2+.....
now set x = m+pq,
then P(m+pq) = a0+a1(m+pq)+a2(m+pq)2+.....
=a0+a1m+a2m2+..... + some multiple of p
=p + a multiple of p
CONTRADICTION!!
QED!!
::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Polynomial and Prime Numbers
« Reply #5 on: Sep 17th, 2003, 5:15am » |
Quote Modify
|
on Sep 17th, 2003, 2:11am, Sir Col wrote:
However, for |a0|=1, special consideration is required. |
|
P(0)=a0 = [pm]1 [ne] prime
[edit]Oh wait, that only holds if you count 0 as a natural number, and you don't.. And maybe Barukh doesn't either..
But you must admit in this case it makes live easier if you accept 0[in][bbn]  [/edit]
|
| « Last Edit: Sep 17th, 2003, 5:18am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Polynomial and Prime Numbers
« Reply #6 on: Sep 17th, 2003, 6:14am » |
Quote Modify
|
You got me there, Towr! 
Nice proof, TenaliRaman! 
Not that it's needed now, but out of interest, I wonder if it is possible to extend my method for the case, |a0|=1 (without admitting 0 as natural number)?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Polynomial and Prime Numbers
« Reply #7 on: Sep 17th, 2003, 6:44am » |
Quote Modify
|
TenaliRaman, I like your approach. The only thing remained is that some multiple of p is not 0
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Polynomial and Prime Numbers
« Reply #8 on: Sep 17th, 2003, 7:00am » |
Quote Modify
|
on Sep 17th, 2003, 6:44am, Barukh wrote:| TenaliRaman, I like your approach. The only thing remained is that [hidden] |
|
hmm let q belong to [bbn] and q [ne] 0
since m and p belong to [bbn]
m+pq belong to [bbn]
is the proof complete now?
|
| « Last Edit: Sep 17th, 2003, 7:03am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Polynomial and Prime Numbers
« Reply #9 on: Sep 17th, 2003, 7:49am » |
Quote Modify
|
Even though you already contributed quite a few posts (and not the least interesting ones), on the occasion of your becoming a member:
Welcome to the forum, Barukh! 
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Polynomial and Prime Numbers
« Reply #10 on: Sep 17th, 2003, 8:48am » |
Quote Modify
|
May I echo wowbagger's words, and welcome you too, Barukh.
TenaliRaman, it seems that your proof is incomplete... 
From:
P(m+pq) = a0+a1(m+pq)+a2(m+pq)2+.....
=a0+a1m+a2m2+..... + some multiple of p
=p + a multiple of p
We cannot be sure that the multiple of p, kp[ne]0. That is, we must show that P(m+pq)=p+kp, where k[ne]0.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Polynomial and Prime Numbers
« Reply #11 on: Sep 17th, 2003, 10:36am » |
Quote Modify
|
on Sep 17th, 2003, 7:49am, wowbagger wrote:Even though you already contributed quite a few posts (and not the least interesting ones), on the occasion of your becoming a member:
Welcome to the forum, Barukh! |
|
Thank you very much, wowbagger, for the appreciation!
on Sep 17th, 2003, 8:48am, Sir Col wrote:May I echo wowbagger's words, and welcome you too, Barukh.
TenaliRaman, it seems that your proof is incomplete...
|
|
Sir Col, thank you very much too - for welcoming and for answering TenaliRaman - that's exactly what I meant.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Polynomial and Prime Numbers
« Reply #12 on: Sep 17th, 2003, 11:08am » |
Quote Modify
|
on Sep 17th, 2003, 8:48am, Sir Col wrote:| We cannot be sure that the multiple of p, kp[ne]0. That is, we must show that P(m+pq)=p+kp, where k[ne]0. |
|
Supposing we don't have an infinite order polynomial, then since P(m+pq)=p+kp for every q [in] [bbn] with some k [in] [bbn], not all those k can be 0 since there are a limited number of extreme, and thus a limited number of times any one value can be reached.
|
| « Last Edit: Sep 17th, 2003, 11:08am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Polynomial and Prime Numbers
« Reply #13 on: Sep 17th, 2003, 12:00pm » |
Quote Modify
|
Nice! I was thinking of something similar, Towr; that is, for any finite degree polynomial there is a last turning point. Hence all values beyond that (either direction) will increase to negative or positive infinity, and after exceeding the value, p, never to return.
I would still like to prove that P(x) is not prime for all x, when |a0|=1. I know we have proved it indirectly by TenaliRaman's method, as the completion of the original problem also proves this result, but I would like to prove it directly. Does anyone have any ideas how it could be done?
|
| « Last Edit: Sep 17th, 2003, 12:08pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Polynomial and Prime Numbers
« Reply #14 on: Sep 17th, 2003, 12:54pm » |
Quote Modify
|
Actually, I'm pretty sure the polynomial that could pass through a prime for all natural n would have to be infinite, and I don't see a reason to dismis it. You can define it as some sum from i=0 to [infty] and then some stuff I won't go into because I don't remember how to actually do it.
The thing is, I think you can define a(n infinite) polynomial that goes through a prime (even the same one) for all n, just not with integer coefficients, which is what you have to prove.
|
| « Last Edit: Sep 17th, 2003, 12:55pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Polynomial and Prime Numbers
« Reply #15 on: Sep 17th, 2003, 1:10pm » |
Quote Modify
|
Yeah. Without the integer coefficients part, you could just use the Taylor series for sin([pi]x)+2.
|
| « Last Edit: Sep 17th, 2003, 1:10pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Polynomial and Prime Numbers
« Reply #16 on: Sep 17th, 2003, 3:21pm » |
Quote Modify
|
Reading around it seems that this problem is by no means trivial. It took the might of Christian Goldbach, in 1752, to prove that no polynomial with integral coefficients exists that is able to generate primes for all integer values.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Polynomial and Prime Numbers
« Reply #17 on: Sep 18th, 2003, 7:13am » |
Quote Modify
|
hmm interesting comments made but i will put out some points that i was thinking ,
first i always thought of P(x) to be a hurwitz polynomial (only difference being the coefficients restricted to integers)
some points as to why i was thinking like that,
1>the polynomial doesn't hit zero at any point in the positive plane (and i don't think it should).
2>the polynomial has to be strictly monotonically increasing
maybe i am making a mistake here somewhere or am i??
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Polynomial and Prime Numbers
« Reply #18 on: Sep 18th, 2003, 8:46am » |
Quote Modify
|
The polynomial may flail wildly between its integer values. As long as P(n)=p , for r [notin] [bbn] P(r) can be -10000 , or any other value, nobody cares.
So it may hit 0, and may not be monotonicly increasing. Unless you have some convinving argument why it is not possible if you have integer coefficients and P(n)=p.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Polynomial and Prime Numbers
« Reply #19 on: Sep 18th, 2003, 9:14am » |
Quote Modify
|
TenaliRaman, there is nothing to restrict the polynomial to positive coefficients. For example, n2–79n+1601, will generate primes for n=0,1,2,...,79.
Also, by insisting that P(x) is a strictly monotonically increasing polynomial, your proof fails to consider other polynomials, for which the only required restriction is that P(x)>0 for x[in][bbn]. And as Towr, pointed out, it is quite possible for P(x) to be negative for non-integer values of x, as long as P(x) is prime for the positive integer values of x.
|
| « Last Edit: Sep 18th, 2003, 9:14am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Polynomial and Prime Numbers
« Reply #20 on: Sep 18th, 2003, 9:29am » |
Quote Modify
|
i have no real convincing arguments actually but i cannot imagine how a polynomial which follows P(1)<P(2)<P(3)<.... can behave in a different way in the interval (n,n+1) unless otherwise explicitly defined.
(Blame my poor knowledge for this discussion.Hope u don't mind)
ok just after i wrote this post i realised the err in my thoughts!!(sheesh!! why do i always have to learn things after embarassing myself)
|
| « Last Edit: Sep 18th, 2003, 9:39am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Polynomial and Prime Numbers
« Reply #21 on: Sep 18th, 2003, 1:33pm » |
Quote Modify
|
on Sep 18th, 2003, 9:29am, TenaliRaman wrote:| why do i always have to learn things after embarassing myself |
|
I don't believe there is any better way to learn. When I was a student in school, I was always the one who always put his hand up and tried to answer every question. Obviously I hoped I was right – and very occasionally I was  – but I can tell you now that the things I learned best, and I remember to this day, are the suggestions/answers I gave that were wrong. I'm sure you can see the number of times I've posted erroneous ideas on this forum, and if I could rewind time, I'd do it exactly the same.
However, it seems that some people, like most others on this forum, do seem to get it right first time. Oh well. 
|
| « Last Edit: Sep 18th, 2003, 1:37pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Polynomial and Prime Numbers
« Reply #22 on: Sep 18th, 2003, 1:37pm » |
Quote Modify
|
on Sep 18th, 2003, 9:29am, TenaliRaman wrote:i have no real convincing arguments actually but i cannot imagine how a polynomial which follows P(1)<P(2)<P(3)<.... can behave in a different way in the interval (n,n+1) unless otherwise explicitly defined.
(Blame my poor knowledge for this discussion.Hope u don't mind)
ok just after i wrote this post i realised the err in my thoughts!!(sheesh!! why do i always have to learn things after embarassing myself) |
|
So why are you leaving any evidence around? 
Don't worry-you'll get quicker at modifying your posts!
Theoretical Question: If you modify your post before anyone reads it, was it ever wrong?
|
| « Last Edit: Sep 18th, 2003, 1:38pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Polynomial and Prime Numbers
« Reply #23 on: Sep 18th, 2003, 5:03pm » |
Quote Modify
|
on Sep 18th, 2003, 1:37pm, James Fingas wrote:| Theoretical Question: If you modify your post before anyone reads it, was it ever wrong? |
|
As long as the post has that tattletale "Last edit:..." on it, everybody knows you goofed up somehow!
The real trick is when you can delete your erroneous post, then post the corrected version. Unfortunately you have to be quick, or else someone will reply to your bad post before you enter the correction - making the truth evident to all! 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Polynomial and Prime Numbers
« Reply #24 on: Sep 18th, 2003, 11:18pm » |
Quote Modify
|
Getting back to the puzzle...
on Sep 17th, 2003, 12:54pm, towr wrote:Actually, I'm pretty sure the polynomial that could pass through a prime for all natural n would have to be infinite, and I don't see a reason to dismis it. You can define it as some sum from i=0 to [infty] and then some stuff I won't go into because I don't remember how to actually do it.
|
|
That's very interesting! I would like to get a proof...
Also, let me propose a different, but related problem:
Find a (non-constant) polynomial P(x) with integer coefficients such that (n is an integer) if P(n) > 0, than P(n) is a prime. Define |P(x)| as the number of such n's. What is the maximal value of |P(x)|?
Of course, many examples may be given at once. It seems obvious that if the degree of the polynomial is finite, than it should be even. For instance, the polynomial P(x) = -2x2 + 61 satsifies the conditions of the problem, as it evaluates to prime numbers for n = -5...+5, so |P(x)| = 11.
on Sep 18th, 2003, 9:14am, Sir Col wrote: ...For example, n2–79n+1601, will generate primes for n=0,1,2,...,79.
|
|
This astounding example (which, I learnt, was discovered by L. Euler), unfortunately, does not satisfy the conditions...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print