# Find the smallest prime number $p$ such that $p\, | \,n^2-n-2023$ for some integer $n$.

Find the smallest prime number $$p$$ such that $$p\, | \,n^2-n-2023$$ for some integer $$n$$.

since $$n^2-n =n(n-1)$$ is the product of two consecutive integers they must be even so the difference between an even and odd number is always odd so $$n^2-n-2023$$ is always odd which implies $$p$$ is not even and the only even prime is $$2$$ so $$p\neq 2$$ but after this I do not know what to do please help.

• but n is an integer not natural number Commented Jan 21, 2019 at 14:48
• p would divide n^2-n-2023 irrespective of positive or negative Commented Jan 21, 2019 at 14:49
• Is $n$ a positive integer? Commented Jan 21, 2019 at 14:49
• Trial and error seems to work easily enough. You've eliminated $p=2$, so what about $p=3$? Keep going. Since $7\,|\,2023$ you know the answer must be one of $3,5,7$.
– lulu
Commented Jan 21, 2019 at 14:51
• is there any way to do it without trial and error Commented Jan 21, 2019 at 14:52

Let $$f(n)=n^2-n-2023$$ and $$f_p(n)=f(n)\pmod{p}$$

$$\begin{array}{c|cc} n & 0 & 1\\ \hline f_2(n) & 1 & 1\end{array}$$ thus $$f_2(n)\neq 0$$ and $$2$$ is not a prime factor of $$f(n)$$

$$\begin{array}{c|ccc} n & 0 & 1 & 2\\ \hline f_3(n) & 2 & 2 & 1\end{array}$$ thus $$f_3(n)\neq 0$$ and $$3$$ is not a prime factor of $$f(n)$$

$$\begin{array}{c|ccccc} n & 0 & 1 & 2 & 3 & 4\\ \hline f_5(n) & 2 & 2 & 4 & 3 & 4\end{array}$$ thus $$f_5(n)\neq 0$$ and $$5$$ is not a prime factor of $$f(n)$$

And since $$f(1)=-2023=-7\times 17^2$$ then $$p=7$$ is the lowest prime dividing $$f(n)$$ for some $$n$$.

The answer is 7.

As 2023 is a multiple of 7, it follows that for any $$n$$ that is a multiple of 7, so will $$n^2-n-2023$$ be a multiple of 7. So now it remains to show that $$n^2-n-2023$$ is not a multiple of 2,3, or 5 for any integer $$n$$.

However, the prime 5 is not a multiple for any integer $$n$$: $$2023 \equiv 3 \mod 5$$ yet there is no $$j \in \mathbb{F}_5$$ such that $$j^2-j = 3$$. This implies that there is no $$n$$ that satisfies $$n^2-n \equiv 3 \mod 5$$ [make sure you see why] which implies that there is no $$n$$ s.t. $$n^2-n -2023$$ is divisible by 5.

Likewise 3 will not be a multiple for any integer $$n$$; $$2023 \equiv 1 \mod 3$$ yet there is no $$j \in \mathbb{F}_3$$ such that $$j^2-j = 1$$. This implies that there is no $$n$$ s.t. $$n^2-n -2023$$ is divisible by 3 [make sure you see why].

Meanwhile you can check that $$n^2-n-2023$$ is always odd for each integer $$n$$; if $$n$$ is even it is the sum of two evens and 1 odd, if $$n$$ is odd it is the sum of 3 odds. This implies that there is no $$n$$ s.t. $$n^2-n -2023$$ is divisible by 2.

$$n^2-n-2023$$ is odd, so for prime $$p$$ we have, modulo $$p,$$ that $$n^2-n-2023\equiv 0\iff 4n^2-4n-8092\equiv 0\iff (2n-1)^2\equiv 8093.$$

Now $$8093\equiv 2 \mod 3,$$ and $$2$$ is not the residue$$\mod 3$$ of a square, so $$p\ne 3.$$

And $$8093\equiv 3 \mod 5,$$ and $$3$$ is not the residue$$\mod 5$$ of a square, so $$p\ne 5.$$

Since $$8093\equiv 1\equiv 1^2 \mod 7,$$ we have $$n=1\implies (2n-1)^2= 1\equiv 8093 \mod 7\implies n^2-n-2023\equiv 0\mod 7.$$

Note that $$2023 = 7 \cdot 17^2$$

## $$p=3$$

\begin{align} n^2-n-2023 \equiv 0 \pmod 3 \\ n^2+2n-1 \equiv 0 \pmod 3 \\ (n+1)^2 \equiv 2 \pmod 3 \end{align}

$$\begin{array}{|c|cc|} \hline n \mod 3 & 0 & 1,2 \\ n^2 \mod 3 & 0 & 1 \\ \hline \end{array}$$ The perfect squares modulo $$3$$ are $$0$$ and $$1$$. So there is no solution.

## $$p=5$$

\begin{align} n^2-n-2023 &\equiv 0 \pmod 5 \\ n^2+4n+2 &\equiv 0 \pmod 5 \\ (n+2)^2+3 &\equiv 0 \pmod 5 \\ (n+2)^2 &\equiv 2 \pmod 5 \end{align}

$$\begin{array}{|c|ccc|} \hline n \mod 5 & 0 & 1,4 & 2,3 \\ n^2 \mod 5 & 0 & 1 & 4 \\ \hline \end{array}$$

The perfect squares modulo $$5$$ are $$0, 1, 4$$. So there is no solution.

## $$p=7$$

\begin{align} n^2-n-2023 &\equiv 0 \pmod 7 \\ n^2-n &\equiv 0 \pmod 7 \\ n(n-1) &\equiv 0 \pmod 7 \\ \end{align}

Clearly $$n \equiv 0 \pmod 7$$ and $$n \equiv 1 \pmod 7$$ are solutions.