Let $p$ be a prime and $n$ be a positive integer such that $p^2$ divides $\prod_{k=1}^n (k^2+1)$. Show that $p<2n$.
Problem
Source: CWMI 2017 Q1
Tags: number theory
valentinodante
14.08.2017 19:59
Since $p$ divides $\prod_{k=1}^n (k^2+1)$, there are two cases.
Case (i) $p^2$ divides one of $\{1^2+1, 2^2+1, ..., n^2+1\}$, let it be $k^2+1$. In this case, then $p^2 \leq k^2+1 \implies p < k+1 \leq 2n$.
Case (ii) $p$ divide two of $\{1^2+1, 2^2+1, ..., n^2+1\}$, let it be $k^2+1, l^2+1$. Then, since $p \mid k^2+1, l^2+1$, $p \mid (k^2+1)-(l^2+1) \implies p \mid (k-l)(k+l)$. This means p divides either $k-l$ or $k+l$, which is less than $2n$.
So in both cases, $p$ is less than $2n$.
rkm0959
17.08.2017 14:37
Of course, $p^2|k^2+1$ implies $p < k+1$, so if $p^2$ divided one of these terms, we have $p<n+1 \le 2n$. Let's say that $u,v$ are first two minimal positive integers that $p|u^2+1$ and $p|v^2+1$. Then $u<v \le n$. Meanwhile, we know that $u+v \equiv 0 \pmod {p}$, so combine this with $0< u+v < 2n$ to get the conclusion.
f6700417
10.08.2022 17:48
It's said that the original question was: Let p be a prime and n be a positive integer such that p^2 divides \prod_{k=1}^n (k^3+1). Show that p<2n. Given that it's the first question of the contest, the question was changed to make it easier.
Tyx2019
23.07.2023 13:09
Let $p$ be a prime and $n$ be a positive integer such that $p^2$ divides $\prod_{k=1}^n (k^3+1)$. Show that $p<2n$.
Assume $p>2$, $p=2$ can be dealt with easily. There are two cases.
Case 1. $p|u^3+1$, $p|v^3+1$, $u\neq v<n$. If $p|a^3+1$, $p|(a+1)(a^2-a+1)$. If either of $u,v$ are $\geq p-1$, then it is obvious that $p<2n$. So we have $p$ does not divide $a+1$, and $a^2-a+1\equiv 0\mod{p}$, $4a^2-4a+4\equiv 0 \mod{p}$, and $(2a-1)^2 \equiv 3 \mod{p}$.
Clearly if does not exist $0<k<p$ s.t. $k^2 \equiv 3 \mod{p}$, then there is no such $n$. Hence assume such $k$ exists. Hence the only solutions for $a$(and consequently $u,v$) satisfy $2a-1\equiv k \mod{p}$ or $2a-1 \equiv p-k \mod{p}$. WLOG, let $u\equiv \frac{k+1}{2} \mod{p}$, $v \equiv \frac{p-k+1}{2} \mod{p}$
Note that if $x$ is a odd number, the smallest $l>0$ such that $l \equiv \frac{x}{2} \mod{p}$ is $>\frac{p}{2}$ (If $l<\frac{p}{2}$, $x$ is even). Notice $k+1$ and $p-k+1$ are of different parity, hence one of the two must be odd, and one of $u,v>\frac{p}{2}$. Hence $n\geq max(u,v)>\frac{p}{2}$, which implies $p<2n$.
Case 2. $p^2|u^3+1$, $u\leq n$. Using a similar argument as above, $p^2|u^2-u+1$. $u^2-u+1\geq p^2 >p^2-p+1$. As the function $x^2-x+1$ is strictly increasing for positive integer $x$, we have $n\geq u>p$, hence $2n \geq 2p > p$
mathhotspot
23.03.2024 17:51
it is basically complex combinatorics , ref PFTB
Aiden-1089
04.07.2024 04:58
Assume FTSOC that $p \geq 2n$. Since $p^2 \geq 4n^2 > n^2+1$, there does not exist $k$ such that $p^2 \mid k^2+1$. So there must exist at least $2$ distinct values of $k$ such that $1 \leq k \leq n$ and $k^2+1 \equiv 0$ (mod $p$). If $a,b$ satisfies the above condition, then $a^2 \equiv -1 \equiv b^2$ (mod $p$) $\implies (a-b)(a+b) \equiv 0$ (mod $p$) $\implies p \mid a-b$ or $p \mid a+b$. If $p \mid a-b$, then $n-1 > a-b \geq p \geq 2n$, contradiction. If $p \mid a+b$, then $2n > a+b \geq p \geq 2n$, contradiction. Hence we must have $p < 2n$.
megarnie
04.07.2024 15:55
If not then we can choose a and b different from 1 to n where p divides a^2+1 and b^2+1 (since p^2 clearly cannot divide a^2+1 for a leq n) but then we have a^2 = b^2 mod p so p divides a+b or a-b, both impossible because a+b and |a-b| are both in the interval (0,p) (which is true since a+b leq n+(n-1)<p)