Is the product of two consecutive integers $1$ $\pmod n$?

First we rewrite the congruence: $$4x(x+1)=4\pmod{4n}\quad\Leftrightarrow\quad (2x+1)^2=5\pmod{4n}\ .$$ Now write $y=2x+1$ and consider various cases.

  • If $n$ is even then the above implies $y^2=5\pmod8$, which has no solution.

  • If $5^2\mid n$ then we get $$\eqalign{y^2=5\pmod{25}\quad &\Rightarrow\quad 5\mid y^2\cr &\Rightarrow\quad 25\mid y^2\cr &\Rightarrow\quad 25\mid 5\cr}$$ and again there is no solution.

  • So for solutions to exist, $n$ is a product of $5$ (possibly) and prime powers $p^\alpha$ where $p$ is not $2$ or $5$. There is a solution iff $$y^2=5\pmod{p^\alpha}$$ has a solution for every such prime power, which can be proved to be equivalent to $$y^2=5\pmod p$$ having a solution for every $p\mid n$ (except $p=2,5$). Using the Legendre symbol one can show that this comes down to the following.

The congruence $x(x+1)=1\pmod n$ has a solution if and only if $n$ is a product of primes in which $5$ occurs only once (or not at all), and every other prime is congruent to $1$ or $4$ modulo $5$.


Here is a table of some low values of $n$. I have listed "ok" if the congruence has a solution, otherwise I have given a "bad" prime factor of $n$. $$\def\ok{{\rm ok}} \matrix{3&5&7&9&11&13&15&17&19&21&23&25&27&29&31&\cdots&55\cr 3&\ok&7&3&\ok&13&3&17&\ok&3&23&5&3&\ok&\ok&\cdots&\ok\cr}$$ Note that $p=5$ is "bad" for $n=25$ because it occurs twice, but it is "ok" for $n=5$ and $n=55$ because it only occurs once.


You are asking when the polynomial $x^2+x-1$ has a root mod $n$. Since $x(x+1)$ is always even, clearly $n$ must be odd for such an $x$ to exist. In that case $2$ is invertible mod $n$, and so by the quadratic formula $x^2+x-1$ has a root mod $n$ iff the discriminant $5$ has a square root mod $n$.

So you are asking for what odd integers $n$ is $5$ a square mod $n$. By the Chinese remainder theorem, $5$ is a square mod $n$ iff it is a square mod $p^k$ for each prime power $p^k$ appearing in the prime factorization of $n$. For $p\neq 2,5$, $n$ is a square mod $p^k$ iff $5$ is a square mod $p$ (for instance, by Hensel's lemma). By quadratic reciprocity, $5$ is a square mod $p$ for odd $p$ iff $p$ is a square mod $5$, i.e. iff $p$ is $0,1,$ or $4$ mod $5$. The case $p=2$ does not matter since $n$ must be odd, and $5$ is a square mod $5^k$ iff $k\leq 1$.

Putting it all together, we find that $x^2+x-1$ has a root mod $n$ iff every prime factor of $n$ is $0,1,$ or $4$ mod $5$ and $25$ does not divide $n$.