<s>[INST] Is the product of two consecutive integers $1$ $\pmod n$? Is there a simple test for $n$ to determine if there exists an integer $x$ such that $x$($x+1$) $=$ $1$ $\pmod n$. For example, $n$ $=$ $3$ and $n$ $=$ $7$, there are no integers $x$ such that $x$($x+1$) $=$ $1$ $\pmod n$. But for $n$ $=$ $5$ and $n$ $=$ $11$, there are integers $x$ such that $x$($x+1$) $=$ $1$ $\pmod n$. There are namely,
$x = 2$, 
$2*3$ $=$ $1$ $\pmod 5$
$x = 7$, 
$7*8$ $=$ $1$ $\pmod {11}$
It is confusing to find out which integers $n$ have this property. Maybe there is a special (mathematical) property these numbers have. Help is appreciated. Thanks.
 [/INST] 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.
</s>