# 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.

• It would be nice to know where the question comes from...? Homework? – Julien Nov 8 '13 at 20:03
• Not homework. A practice question for a comprehensive exam for an undergrad degree. – User69127 Nov 8 '13 at 20:17
• Ah, well, now you know how to start on this problem, and even a bit more...;-). – Julien Nov 8 '13 at 20:20

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)$$

• The product up through 17 is the least one divisible by $10^6$ and so solves the problem. $(2^2+1)\cdots(13^2+1)=1348100000$ (this problem is well within the comfort level of desktop computers, but you can also argue by divisibility) – TBrendle Nov 8 '13 at 20:25
• @TBrendle: Thanks. I had already edited my answer to account for the only prime ($7$) which gave more than one factor of $5$. – robjohn Nov 8 '13 at 20:47

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$.)

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)

...

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$