5
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – TBrendle Nov 8 '13 at 20:25
  • $\begingroup$ @TBrendle: Thanks. I had already edited my answer to account for the only prime ($7$) which gave more than one factor of $5$. $\endgroup$ – robjohn Nov 8 '13 at 20:47
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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)

...

$\endgroup$
-2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.