Prime-generating polynomials
 

Could someone give me the details of the proof that there is no polynomial with integer coefficients that generates only primes? I think it was Goldbach who proved it, but I can't find any details of the proof online.

I asked someone about it and he said that you use the fact that f(f(0)) is divisible by f(0), but what if f(f(0)) = f(0)?

Page 38 of Riesel, 2nd edition. It's a one-page proof, but too long for me to want to retype it here. If you're interested in number theory, it's one of the short list of books I consider must-haves.

Unfortunately, all my money is going towards studying and taking an actuarial exam and the local library doesn't have a copy, the local college has an older copy though .. hmm .. or I could drive 45 minutes to Davis ..


In the meantime, if anyone could write up the proof or point me to another resource that would have it (the local library does have Hardy and Wright if the proof is in there) I would appreciate it!

and thanks for the pointer, ewmayer

Very short proof by contradiction:
f(x) generates only primes.
n-degree of f(x), so n>0

f(x)>1 for integer x (it must be prime).
So f(0)>1, f(0) is prime.
Then f(k*f(0)) is divisible by f(0) (k and x are integers).
If there exists integer k: f(k*f(0))<>f(0) then f(k*f(0)) is not prime
else
there are more than n solutions of f(x*f(0))=f(0) so
f(x*f(0)) is constant(equal to f(0)) and f(x) is that constant too so n=0.
It's contradiction with n>0.

[quote="c00ler"]Very short proof by contradiction:
f(x) generates only primes.
n-degree of f(x), so n>0

f(x)>1 for integer x (it must be prime).
So f(0)>1, f(0) is prime.
Then f(k*f(0)) is divisible by f(0) (k and x are integers).

<snip>[/quote]

Consider f(x) = 1.5x + 2.
f(0) = 2 (prime)
f(1*2) = 5 (not divisible by 2)

[quote="toferc"][quote="c00ler"]Very short proof by contradiction:
f(x) generates only primes.
n-degree of f(x), so n>0

f(x)>1 for integer x (it must be prime).
So f(0)>1, f(0) is prime.
Then f(k*f(0)) is divisible by f(0) (k and x are integers).

<snip>[/quote]

Consider f(x) = 1.5x + 2.
f(0) = 2 (prime)
f(1*2) = 5 (not divisible by 2)[/quote]

Read up a few messages to find the phrase "with integer coefficients".


Paul

thanks cooler, the reason I wanted to know the proof is because I was wondering if it could be extended to show that there are no semiprime-generating polynomials too, and it looks to me like it does.

I've read in a book that f(x) = x[sup]2[/sup] + x + 41 is a very good prime-generating polynomial.

yes, but it only works in the interval [1;39]

greetz andi314

I was thinking about polynomials that can generate Mersenne primes and I made some interesting investigations. I used La Grange interpolations and at the end of my research i came to the matrixes and Pifagor triangle. All my mathematical researches I'll put on my site next week! It's very interesting, but need some CPU work (to calculate matrix 40*41)! Now I'm approaching only to the 15th Mersenne prime... When i'll calculate 38 Mprime, I'll be able to predict 39th and then 40th! But still need some time to accomplish calculations...

[QUOTE][i]OK, some accomplished calculations: [/B][/QUOTE]

To get all primes from 1 to 38 You only have to put natural numbers from 1 to 38 instead of X (in 1..38:). Also I place here all available (for now) polynominals for those people who are interested in searching connections between polynominals. Maybe it'll give us possibility to predict 40th Mersenne Prime!!!

Here we go:

1..1: Y=X+1
1..2: Y=X+1
1..3: Y=[1*X^2+-1*X^1+4]/6
1..4: Y=[-1*X^3+9*X^2+-14*X^1+18]/24
1..5: Y=[5*X^4+-54*X^3+211*X^2+-306*X^1+192]/120
1..6: Y=[-15*X^5+250*X^4+-1545*X^3+4430*X^2+-5640*X^1+2760]/720
1..7: Y=[31*X^6+-741*X^5+6925*X^4+-32055*X^3+76924*X^2+-88524*X^1+38880]/5040
1..8: Y=[-41*X^7+1365*X^6+-18389*X^5+128835*X^4+-501914*X^3+1076880*X^2+-1155456*X^1+478800]/40320
1..9: Y=[29*X^8+-1372*X^7+26754*X^6+-278656*X^5+1681701*X^4+-5966548*X^3+12040636*X^2+-12421584*X^1+4999680]/362880
1..10: Y=[-3*X^9+396*X^8+-14958*X^7+269136*X^6+-2697723*X^5+15943284*X^4+-55869972*X^3+111883824*X^2+-114873984*X^1+46085760]/3628800
1..11: Y=[35*X^10+-1955*X^9+50160*X^8+-784830*X^7+8213415*X^6+-58549155*X^5+279025390*X^4+-853032220*X^3+1565213400*X^2+-1520742240*X^1+587865600]/39916800
1..12: Y=[-293*X^11+19723*X^10+-585530*X^9+10124070*X^8+-113358069*X^7+863152059*X^6+-4552524460*X^5+16546028180*X^4+-40223970688*X^3+61436314368*X^2+-52047509760*X^1+18162144000]/479001600
1..13: Y=[1405*X^12+-113106*X^11+4054061*X^10+-85383210*X^9+1174484355*X^8+-11092217598*X^7+73569099263*X^6+-344158854270*X^5+1121927942740*X^4+-2469378565896*X^3+3451076942976*X^2+-2713022363520*X^1+890942976000]/6227020800
1..14: Y=[-6909*X^13+646984*X^12+-27247857*X^11+682050512*X^10+-11297115687*X^9+130438929192*X^8+-1077165820731*X^7+6421024534496*X^6+-27523309797984*X^5+83382838505824*X^4+-172449641496912*X^3+228620718398592*X^2+-172086552933120*X^1+54604745395200]/87178291200
1..15: Y=[33587*X^14+-3623361*X^13+177160711*X^12+-5195326773*X^11+101904459657*X^10+-1411367000043*X^9+14199985921693*X^8+-105142309431159*X^7+573860272665680*X^6+-2288478836539896*X^5+6531929309055696*X^4+-12859491270011568*X^3+16372060426094976*X^2+-11929972438944000*X^1+3692523702067200]/1307674368000
1..16: Y=[-144959*X^15+17898885*X^14+-1008180635*X^13+34316456265*X^12+-788174207093*X^11+12916325597175*X^10+-155706335375305*X^9+1402769336077395*X^8+-9496408550340712*X^7+48153184706947320*X^6+-180688241518308160*X^5+490355895400665840*X^4+-925949409280796736*X^3+1139371662003621120*X^2+-807950316133094400*X^1+244947024241920000]/20922789888000
1..17: Y=[541393*X^16+-75948792*X^15+4888222660*X^14+-191368976400*X^13+5093528052886*X^12+-97583735331264*X^11+1389621925122860*X^10+-14974286303262000*X^9+123118058032189649*X^8+-772866863398525896*X^7+3680180344614355400*X^6+-13102532239001150400*X^5+34030713163321773072*X^4+-61958474245665042048*X^3+73989227001160846080*X^2+-51222250406047795200*X^1+15246604373704704000]/355687428096000
1..18: Y=[-1767335*X^17+279605936*X^16+-20399555484*X^15+910530685520*X^14+-27813188347770*X^13+616173334121072*X^12+-10236193954245428*X^11+130021900892231920*X^10+-1275949761165134055*X^9+9706872270331913248*X^8+-57095619387402660792*X^7+257373692142097148800*X^6+-874912018497669603440*X^5+2185559672871473823744*X^4+-3851540267468645719296*X^3+4477198615490422517760*X^2+-3032945776329102950400*X^1+887811115087024128000]/6402373705728000
1..19: Y=[5120313*X^18+-907385553*X^17+74495073006*X^16+-3760914973860*X^15+130694508335646*X^14+-3315730598145126*X^13+63558646138185432*X^12+-939808480784525820*X^11+10848170027271900609*X^10+-98290757620475165889*X^9+699134590170032720418*X^8+-3884454787980457880280*X^7+16681463194311358903392*X^6+-54414601232457051468432*X^5+131253339562948557738144*X^4+-224582035886463490007040*X^3+254742938833322798231040*X^2+-169170206830816762368000*X^1+48762757387863687168000]/121645100408832000
1..20: Y=[-13327575*X^19+2629525197*X^18+-241343499132*X^17+13684105553364*X^16+-536815601089290*X^15+15463479376269774*X^14+-338785506288604644*X^13+5769010297911165708*X^12+-77367005635908071655*X^11+822924034480328029821*X^10+-6957619233648694679016*X^9+46653922566131054379192*X^8+-246445209477880219457520*X^7+1013458909823556283418448*X^6+-3185344344252084176222208*X^5+7443472058898599659124736*X^4+-12398426439979890991656960*X^3+13751062164684629092085760*X^2+-8965950791383605583872000*X^1+2547726589450649198592000]/2432902008176640000
1..21: Y=[31407173*X^20+-6862057830*X^19+700049375335*X^18+-44300975367690*X^17+1948562136823938*X^16+-63257925040107660*X^15+1570951368825297470*X^14+-30523024904598511380*X^13+470604032230074582073*X^12+-5805687408280341761790*X^11+57524458969205569849755*X^10+-457693351166968737211170*X^9+2912698071255669064272848*X^8+-14707013781047667140211120*X^7+58166574519871365790480240*X^6+-176772066401678787790889760*X^5+401314387633230451905283968*X^4+-652208093087160336195801600*X^3+708558313926723552211507200*X^2+-454224369078254042634240000*X^1+127365106051864131010560000]/51090942171709440000
1..22: Y=[-67229827*X^21+16189640670*X^20+-1826529635105*X^19+128303645502690*X^18+-6290003035930782*X^17+228636755358073020*X^16+-6390127837515049810*X^15+140538769268367896580*X^14+-2468869195378814879567*X^13+34966200347082759515670*X^12+-401247524321035075266765*X^11+3735891107350327596458970*X^10+-28168277339761065211899712*X^9+171086128920596232437671920*X^8+-829519058849505998871647120*X^7+3167101250172233095472422560*X^6+-9335140096828617626434250112*X^5+20640907285432846835350878720*X^4+-32795914434765501094151731200*X^3+34956695758636036756327219200*X^2+-22059918159041915161067520000*X^1+6109502430560176696688640000]/1124000727777607680000
1..23: Y=[130657103*X^22+-34535303253*X^21+4289865494761*X^20+-332896719679755*X^19+18096054704693658*X^18+-732353423782424598*X^17+22893102536393368466*X^16+-566014243103568259110*X^15+11242558731734530421683*X^14+-181215893812157617002513*X^13+2384576162272285507223061*X^12+-25683081974632444954807215*X^11+226334555237600603931472148*X^10+-1626728801029266173351659668*X^9+9475469442145828219243927936*X^8+-44292251533282727054033904720*X^7+163789612331057313993590899008*X^6+-469520897969048484546926059968*X^5+1013406808612946536415328235776*X^4+-1577142308879005699309737139200*X^3+1651785858527988697947075686400*X^2+-1027346157349662912446361600000*X^1+281267732333637735066501120000]/25852016738884976640000
1..24: Y=[-230021511*X^23+66491050405*X^22+-9058064779005*X^21+773268473324039*X^20+-46397737848523446*X^19+2080338890265633690*X^18+-72342900848651808210*X^17+1998814818737847235774*X^16+-44593958174574547635171*X^15+812021196174479362742825*X^14+-12150127511440110647233065*X^13+149926187737846135112789019*X^12+-1526986776559737513618532176*X^11+12815200005930130439227528360*X^10+-88245940665553939586863077720*X^9+495054042367889043654902963984*X^8+-2238920049533089927092142735296*X^7+8042979508444440192956714603520*X^6+-22479365454702116078954409552000*X^5+47461836841198455064336180637184*X^4+-72474115022931707440505327462400*X^3+74688672171358406452139902771200*X^2+-45835000598827313999814205440000*X^1+12415677796349282688462028800000]/620448401733239439360000
1..25: Y=[368398881*X^24+-116040180564*X^23+17271157596270*X^22+-1615467308091120*X^21+106535962488833031*X^20+-5267921866577805204*X^19+202779965567668266360*X^18+-6227463261018890777040*X^17+155133883010566096334511*X^16+-3170344618208576776868604*X^15+53545847411076010587625350*X^14+-750701771222152571963008560*X^13+8752477061608715144212354521*X^12+-84823546451385307694422325724*X^11+681469596869086566507601541940*X^10+-4515581077690094800968388715280*X^9+24487426317554152160094940102896*X^8+-107484179920952792793406072375104*X^7+376092656966656356628785698105280*X^6+-1027159561014554378784714995808000*X^5+2125473324570567683518791153116160*X^4+-3189603578664827645127632750284800*X^3+3238676234998930256448656174284800*X^2+-1963120203314248305691225128960000*X^1+526548764029146654488380047360000]/15511210043330985984000000
1..26: Y=[-559293143*X^25+190980243500*X^24+-30893626321250*X^23+3149244498458000*X^22+-227014691974338785*X^21+12309586555410197900*X^20+-521430050528630441000*X^19+17689354843792540634000*X^18+-488839220367304829481305*X^17+11133919052155677147368900*X^16+-210671010101897125142770250*X^15+3328260429319561902050570000*X^14+-44017362831063749605007565695*X^13+487577203150989451469802440900*X^12+-4516722829171021244343815439500*X^11+34868131946859050940040138946000*X^10+-223030063188573858519158096453840*X^9+1172244643563564939988794230302400*X^8+-5005071328832774864388265208040000*X^7+17090621838943299868820073643872000*X^6+-45685103660791319979142482129887232*X^5+92776256607634944289404401529446400*X^4+-136977887190015152068621488703488000*X^3+137164776829429754021545504235520000*X^2+-82182638260527428980249595412480000*X^1+21839032517596419702489808896000000]/403291461126605635584000000