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 $w_i$ be the product $p_{2i}p_{2i+1}$, where $p_{i}$ is ${i}$th prime, each $w_i$ is product of two
distinct primes and also $w_k$ and $w_t$ are coprime, now take $t^2$ such that $t^{2}equiv- kpmod{w_i}$for $k=-Ncdots 0,1,2cdots N$,and $i=1,2,cdots ,2N+1$ such that for $k=-N$,$i=1$ and,...,by chinese remainder theorem, we have such $t^2$.



Now $t^{2}+i$ has at least two primes because $t^{2}+i$ is multiple of $w_i$,since there are a prime between $t$ and $2t$ and also $t$ and $t/2$,so $t+h_1$
and $t-h_2$ are primes,so at least one of the numbers $t^{2}-N,cdots
t^{2}+1,t^{2}+2cdots ,t^{2}+N$ is exactly product
of two distinct primes.

No comments:

Post a Comment