Divisibility by $10^6$? Let $p_k$ be the $k^{th}$ prime number. 
Find the least $n$ for which $(p_1^2+1)(p_2^2+1) \cdots (p_n^2+1)$ is divisible by $10^6$.
I have no idea where to start on this problem. Any help would be appreciated.
 A: For each prime above $2$, $p^2+1$ is even. For $2^2+1=5$ so we only need to look for the first $5$ odd primes so that $5\mid p^2+1$.
$p^2\equiv-1\pmod{5}\iff p\in\{2,3\}\pmod{5}$. Scanning the primes: $3,7,13,17,23$ are the first $5$ so that $p\in\{2,3\}\pmod{5}$. Therefore, the product
$$
(2^2+1)(3^2+1)(5^2+1)\dots(23^2+1)
$$
will be divisible by $10^6$. If some $p^2+1$ is divisible by $25$, you may need fewer terms. Indeed, $7^2+1=50$, so we only need 
$$
(2^2+1)(3^2+1)(5^2+1)\dots(17^2+1)
$$
A: Let's evaluate each $(p^2 + 1)$ expression, counting up the factors of $2$ and $5$, stopping when they both are at least $6$:
$n = 1$
$p = 2$, and $(p^2 + 1) = 5$.  2s so far = $0$, 5s so far = $1$.
$n = 2$
$p = 3$, and $(p^2 + 1) = 10$.  2s so far = $1$, 5s so far = $2$.
$n = 3$
$p = 5$, and $(p^2 + 1) = 26$.  2s so far = $2$, 5s so far = $2$.
$n = 4$
$p = 7$, and $(p^2 + 1) = 50$.  2s so far = $3$, 5s so far = $4$.
$n = 5$
$p = 11$, and $(p^2 + 1) = 122$.  2s so far = $4$, 5s so far = $4$.
$n = 6$
$p = 13$, and $(p^2 + 1) = 170$.  2s so far = $5$, 5s so far = $5$.
$n = 7$
$p = 17$, and $(p^2 + 1) = 290$.  2s so far = $6$, 5s so far = $6$.
We have 6 $2$s and 6 $5$s, enough for the product to be divisible by $1000000$.  $n = 7$.  (The actual product here is $390,949,000,000$.)
A: I think find 6 prime number such that pk^2+1 (mod 5)=0
because p^2+1 for all the prime(except 2 ) is odd+1=even 
so p^+1=2k 
now find the numbers such that 5|pk^2+1
like that p=3 3^2+1=10 (ok)
p=7 7^2+1=50 (ok)
...
A: if you want to solve $p_k^2+1\pmod 5=0$
$p_k^2+1-5\pmod 5=0$
$p_k^2-4\pmod 5=0$
$p_k^2-4=5q$
find the prime such that 
$(p_k-2)(p_k+2)=5q$
so $p_k=5k+2$
or $p_k=5k-2$
