Under what situations does $x+1$ divide $4n^2-x$? I am looking at the equation 
$$\frac{4n^2-x}{x+1} = y$$
for even $x$ and $y$, both positive. Under what situations does $x+1$ divide $4n^2-x$?
 A: (This answer has been seriously updated to be more comprehensive.) As noted, the condition
$$(x+1)\mid(4n^2-x),~~~x\text{ even} \tag{$\bullet$}$$
implies that $x$ can be written $2k$, and subsequently is equivalent to $2n^2\equiv k\bmod 2k+1$.
For the moment, fix $k$. Congruences will be modulo $m:=2k+1$ unless otherwise stated. Suppose the prime factorization of $m$ is $\prod p^r$ (we abusively leave indices out for brevity). Since 
$$2(2k^2)\equiv(2k+1)^2+1\equiv1,$$
it follows that there is an explicit inverse $2^{-1}\equiv 2k^2$. Now there is a chain of equivalences:
$$\exists n: 2n^2\equiv k ~~~\iff~ \exists n: n^2\equiv 2k^3 \tag{1}$$
$$\hskip -0.5in \iff \exists n: (n k^{-1})^2\equiv 2k\equiv-1 \tag{2}$$
$$\hskip 0.22in \iff \exists n: n^2 \equiv -1\bmod p^r\;\text{ for each }p|m \tag{3}$$
$$\hskip 0.23in \iff \exists n: n^2\equiv -1\bmod p ~~\text{ for each }p|m \tag{4}$$
$$\hskip -0.25in \iff p\equiv1\bmod 4 ~~\text{ for each }p|m. \tag{5}$$
Note that these are equivalences, not just implications, so $(5)$ is both necessary and sufficient for the existence of a a valid $n$ for a given $k$ (remember $m:=2k+1$ here). Explanations:


*

*$(1)$ follows from simply multiplying both sides by $2^{-1}\equiv2k^2$;

*$(1)\iff(2)$ follows from dividing by $k^2$;

*$(2)\iff(3)$ follows from the Chinese Remainder Theorem (CRT);

*$(3)\iff(4)$ follows from Hensel's lemma (HL);

*$(4)\iff(5)$ follows from Quadratic Reciprocity (QR).


Technical note. In propositional logic, something like $A\iff B\iff C$ would be ambiguous for lack of parentheses. However, in outside and more casual contexts, it may in fact stand for the formula $(A\iff B)~\&~(B\iff C)$ (logical and); this works with chains of equivalences too. Also, the symbols "$\exists n:$" stand for "there exists an $n$ such that."
Working "backwards" from $(5)$: arbitrarily pick a set of prime powers $p^r$, each prime congruent to one modulo four, multiply them together and call the result $m$. QR guarantees the existence of at least two distinct solutions $\pm n_p$ to the equations $u^2\equiv-1\bmod p$ (in fact basic field theory says there will be precisely two solutions, since $p\ne2$). HL guarantees that these lift up uniquely to the two solutions $\pm\,\hat{n}_p$ to the congruences $u^2\equiv-1\bmod p^r$. CRT guarantees there is a unique solution $n$ that satisfies $u^2\equiv-1\bmod p^r$ for each $p^r$, which is equivalent to $u^2\equiv-1\bmod m$ (unique modulo $m$ for a specific choice of roots, that is: note the $\pm$ signs).


*

*To compute $n_p$ (for each prime $p|m$), we use this fact: $$\begin{array}{c l} (p-1)! & \equiv 1\cdot 2\cdots\frac{p-1}{2}\frac{p+1}{2}\cdots (p-1) \\ 
& \equiv 1\cdot 2\cdots\frac{p-1}{2}\left(p-\frac{p-1}{2}\right)\cdots\big(p-(1)\big) \\ 
& \equiv \left(\frac{p-1}{2}\;!\right)^2(-1)^{(p-1)/2} \mod p. \end{array} \tag{$\bigcirc$}$$ When $p\equiv1\mod 4$, $(-1)^{(p-1)/2}=-1$, thus (applying Wilson's theorem to the LHS):
$$n_p\equiv \left(\frac{p-1}{2}\right)!\mod p \tag{$\times$}$$ is a square root of $-1$ modulo $p$. Note that computing factorials can be expensive, so you want to do it via repeated modular multiplication, which is more efficient.

*To compute $\hat{n}_p$, the solution to $f(u):= u^2+1\equiv0\mod p^r$, we apply HL. First we evaluate $f\,'$ (the derivative) at the argument $n_p$, getting $2n_p$, and compute the multiplicative inverse of $2n_p$ modulo $p^{r-1}$ and multiply by the integer $-f(n_p)/p$; in other words $$\hat{n}_p\equiv-\left(\frac{n_p^2+1}{p}\right)\left[\frac{1}{2n_p}\bmod p^{r-1}\right] \mod p^r \tag{$\square$}$$ Note that since $p|(n_p^2+1)$, the division in parentheses is integer division, and the reciprocal in brackets is computed via modular arithmetic $\bmod p^{r-1}$, but then viewed $\bmod p^r$ afterwards. Furthermore, we may multiply $\hat{n}_p$ by $-1\bmod p^r$ to get a second square root of $-1\bmod p^r$; call these two roots $n_p^+$ and $n_p^-$ respectively. An arbitrary choice of $\pm$ is available for each $p$.

*Using the general case formula for CRT, we glue all of the "localized" solutions together: $$n\equiv \sum_{p}n_p^{\pm}\left(\frac{m}{p^r}\right)\left[\left(\frac{m}{p^r}\right)^{-1}\bmod p^r \right] \mod m \tag{$\triangle$}$$ Again, a choice of $+$ or $-$ is made for each $p$. Counterintuitively, these do not designate the notions of "positive" or "negative"; they designate an initially computed root versus an optional, auxiliary root. Above, division in parentheses is done in the integers (so not in modular arithmetic), whereas the reciprocals in brackets are computed $\bmod p^r$ (for various values of $p$), and then the results are reinterpreted as integers $\bmod m$.
After the $2^{\omega(m)}$ solutions $n$ to $u^2\equiv-1\bmod m$ are collected (here $\omega(m)$ stands for the number of primes in $m$'s prime factorization, which was the number of $\pm$ choices that occurred), we may characterize the full set of solutions to our original condition $(\bullet)$ by, for each $m$ we created, moving backwards by setting $k=(m-1)/2$ and adding arbitrary multiples of $m$ to any of the solutions $n$ to the congruence $u^2\equiv-1\bmod m$ we've formed.
A: I will throw another wooden nickel on the fire.
Since $\dfrac{4n^2-x}{x+1}+1=\dfrac{4n^2+1}{x+1}$, we get that the question is equivalent to asking when
$$
x+1\,|\,4n^2+1\tag{1}
$$
Trivially, $x=0$ and $x=4n^2$ satisfy $(1)$, and these are the only solutions when $4n^2+1$ is prime. Let's look for less trivial solutions. That is, let us look at when $4n^2+1$ is composite.
Suppose there is a prime $p$ so that
$$
p\,|\,4n^2+1\tag{2}
$$
$4n^2+1$ is odd, so $p$ must be odd. Furthermore, condition $(2)$ says that $-1\equiv(2n)^2\pmod{p}$; that is, $-1$ is the square of some number $\bmod{p}$ (usually said as "$-1$ is a quadratic residue $\bmod{p}$").

Intro to Quadratic Residues
Suppose that $p$ is an odd prime and $a\not\equiv0\pmod{p}$ is a quadratic residue $\bmod{p}$. There is an $x$ so that $x^2\equiv a\pmod{p}$. First, note that $x\not\equiv0\pmod{p}$. Therefore, by Fermat's Little Theorem,
$$
a^{\frac{p-1}{2}}\equiv x^{p-1}\equiv1\pmod{p}\tag{3}
$$
Consider the equation
$$
(x^{\frac{p-1}{2}}+1)(x^{\frac{p-1}{2}}-1)=x^{p-1}-1\equiv0\pmod{p}\tag{4}
$$
Since $\mathbb{Z}_p$ is a field, there are at most $\frac{p-1}{2}$ solutions to each of
$$
x^{\frac{p-1}{2}}+1\equiv0\pmod{p}\quad\text{and}\quad x^{\frac{p-1}{2}}-1\equiv0\pmod{p}\tag{5}
$$ 
However, Fermat's Little Theorem says there are $p-1$ solutions to $(4)$. Therefore, there are exactly $\frac{p-1}{2}$ solutions to each relation in $(5)$.
Consider the set of non-zero, quadratic residue classes, $Q$. For each $a\in Q$, there are exactly two solutions for $x^2=a$ ($x$ and $-x$). Thus, $|Q|=\frac{p-1}{2}$. For each $a\in Q$, we showed in $(3)$ that $a^{\frac{p-1}{2}}\equiv1$. The pigeonhole principle and $(5)$ say that for the $\frac{p-1}{2}$ non-zero, non-quadratic residue classes $\bmod{p}$, we have $a^{\frac{p-1}{2}}\equiv-1\pmod{p}$.
Thus, we have shown that for an odd prime $p$,
$$
a^{\frac{p-1}{2}}\equiv\left\{\begin{array}{}+1\pmod{p}&\text{if }a\text{ is a quadratic residue }\bmod{p}\\-1\pmod{p}&\text{if }a\text{ is not a quadratic residue }\bmod{p}\end{array}\right.\tag{6}
$$
For example, $-1$ is a quadratic residue $\bmod{p}$ if and only if $(-1)^{\frac{p-1}{2}}\equiv1\pmod{p}$; that is, if and only if $p\equiv1\pmod{4}$.

Therefore, if $x+1$ is divisible by any prime $p\not\equiv1\pmod{4}$, then $\dfrac{4n^2-x}{x+1}$ cannot be an integer.
If $4n^2+1$ is prime, there are only trivial solutions, and if $4n^2+1$ is composite, then $x+1$ can be any factor of $4n^2+1$.
A: I feel like the existing answers make the problem far too complicated. Let $u=x+1$ and $v=y+1$; then by easy algebra, the given equation is the same as $4n^2+1 = uv$. Since $x$ and $y$ are both even and positive, $u$ and $v$ must be odd (no problem, since $4n^2+1$ is odd) and at least $3$. Therefore the solutions are in 1-to-1 correspondence with the nontrivial factorizations (if any) of $4n^2+1$.
