Wednesday, 22 February 2012

nt.number theory - Detecting almost-primes quickly

this is my answer, I don't know if this can complete your answer or not:



(similar to falagar's answer )



Let wi be the product p2ip2i+1, where pi is ith prime, each wi is product of two
distinct primes and also wk and wt are coprime, now take t2 such that t2equivkpmodwifor k=Ncdots0,1,2cdotsN,and i=1,2,cdots,2N+1 such that for k=N,i=1 and,...,by chinese remainder theorem, we have such t2.



Now t2+i has at least two primes because t2+i is multiple of wi,since there are a prime between t and 2t and also t and t/2,so t+h1
and th2 are primes,so at least one of the numbers t2N,cdotst2+1,t2+2cdots,t2+N is exactly product
of two distinct primes.

No comments:

Post a Comment