# 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$?

-
@ArturoMagidin Isn't this just restating the problem? It's the same as 2k+1 dividing 2n^2-k, but I am trying to find a systematic way to find solutions that don't require trial and error –  MyNameIsKhan Jun 24 '12 at 5:20
@ArturoMagidin That is what I meant by "under what situations does x+1 divide." I know that x being even is the same as replacing it with 2k, but this doesn't address the question at hand –  MyNameIsKhan Jun 24 '12 at 5:24
I need to explicitly mention that I am aware that even numbers are divisible by 2? You're assuming I am clueless and unaware of this? Honestly, I find that a little condescending. I would also appreciate you not deleting your posts, as it makes my earlier posts look odd and out of context. –  MyNameIsKhan Jun 24 '12 at 5:32
@AgainstAsicilian: Take a look around questions in this site. We get everything from retired, highly accomplished researchers, to people who would be utterly clueless as to how to proceed with the problem you pose, even to the point of not being able to reduce it even that simple step. I erred in trying to divine your level of competence from your plain post that contained no indication of what that level might be. Should I have guessed higher? Perhaps. Should you consider it an insult to your intelligence or an attempt at getting a rise from you? No. –  Arturo Magidin Jun 24 '12 at 5:46
@anon: If $p|2k+1$, then $2k\equiv -1\pmod{p}$, hence $\left(\frac{2k}{p}\right) = 1$ if and only if $\left(\frac{-1}{p}\right)=1$ if and only if $p=2$ or $p\equiv 1\pmod{4}$. So your implication is equivalent to $p|2k+1 \implies p\equiv 1\pmod{4}$. Hence, $2k+1$ cannot be divisible by any prime that is congruent to $3$ modulo $4$. –  Arturo Magidin Jun 24 '12 at 6:12

(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:

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).

1. 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.

2. 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$.

3. 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.

-
I'm CWing 'cause AM finished typing way before me. Technically there's a distinction between $(A\iff B)\iff C$ and the 'casual' interpretation of $A\iff B\iff C$, which is to split into $A\iff B$ and $B\iff C$. I'm following the latter route. –  anon Jun 24 '12 at 6:50
Once I get k, is there a way to solve for y and generate a family of n values? –  MyNameIsKhan Jun 24 '12 at 6:51
@AgainstASicilian: You need to have the solutions to $m^2\equiv -1\pmod{2k+1}$. This requires you to solve the congruence modulo the prime powers that divide $2k+1$. I don't know of a formula, but you can write down an expression for $y$ in terms of the solutions to that congruence. Note that the number of solutions to the congruence will be $2^t$, where $t$ is the number of distinct prime factors of $2k+1$ (all of which must be congruent to $1$ modulo $4$). It is fairly straightforward to generate solutions given $k$, but it seems pretty hard to write them down in terms of $k$. –  Arturo Magidin Jun 24 '12 at 6:54
To compute square roots in modular arithmetic, there are e.g. the Cipolli or Tonelli-Shanks algorithms (I know nothing about these), but I don't believe there is a straightforward formula. Note that computing the square root of $-1$ modulo primes, needs to be taken up to modulo prime powers vie Hensel, and then glued together to find a solution modulo the composite number $m$ via CRT. | Also, I guess it would have been more sensible to write $2k^3\equiv-1$ before localizing to prime power moduli, but it works either way. –  anon Jun 24 '12 at 6:57
marking this as answer regardless –  MyNameIsKhan Jun 25 '12 at 4:09

To elucidate anon's comments. Writing $x=2k$, we have $$\frac{4n^2-x}{x+1} = \frac{4n^2-2k}{2k+1} = \frac{2(2n^2-k)}{2k+1}.$$ Thus, the left hand side is an integer if and only if $2n^2\equiv k\pmod{2k+1}$.

Now, as anon noted, since $4k^2\equiv 1\pmod{2k+1}$, we can rewrite $2n^2\equiv k\pmod{2k+1}$ as $2n^2\equiv 1k \equiv 4k^3\pmod{2k+1}$. Since $2k+1$ is odd, we can cancel $2$ to get $n^2\equiv 2k^3\pmod{2k+1}$. That means that $2k^3$ must be a square modulo $2k+1$. And this occurs if and only if $2k$ is a square modulo $2k+1$. Since $2k\equiv -1\pmod{2k+1}$, this occurs if and only if $-1$ is a square modulo $2k+1$.

Now, if this occurs, and $p$ is a prime that divides $2k+1$, then $-1$ will also be a square modulo $p$. It is well known that the only odd primes for which $-1$ is a square are the primes that are congruent to $1$ modulo $4$. Thus, if $2n^2\equiv k\pmod{2k+1}$, then every prime that divides $2k+1=x+1$ must be congruent to $1$ modulo $4$. Conversely, suppose that every prime that divides $2k+1$ is congruent to $1$ modulo $4$. Then $-1$ is a square modulo all prime powers that divides $2k+1$, and so we can find $n$ such that $n^2 \equiv 2k^3 \pmod{2k+1}$. Hence, we can find $n$ such that $2n^2\equiv k\pmod{2k+1}$, hence $x+1$ will divide $2n^2-x$.

Thus, there exists $n$ such that $x+1$ divides $2n^2-x$ if and only if $x+1$ is a product of primes that are congruent to $1$ modulo $4$.

For example, with $x+1=5$ (so $k=2$), we need an $n$ such that $n^2\equiv 16\equiv 1\pmod{5}$. Thus, each value of $n\equiv 1\pmod{5}$ and each value of $n\equiv43\pmod{5}$ gives a solution $(x,y,n)$: e.g., if $n=11$, then $$\frac{4n^2-x}{x+1} = \frac{4(121)-4}{5} = 4(24).$$ So for $k=2$, we get families of solutions $(5r+1,4,y)$ and $(5r+4,4,y)$, with $y$ being given by the formula you have.

Or say $x+1=169 = 13^2$ (so $k=84$). We need to find the $n$ such that $n^2\equiv 2(84)^3 \pmod{169}$. This is equivalent to finding $m$ such that $m^2\equiv 168\equiv -1\pmod{169}$, and then multiplying by $k=84$ to get the right answer. One such solution is $m\equiv 70\pmod{169}$, the other being $m\equiv 99\pmod{169}$. So the solutions to $n^2\equiv 2(84)^3\pmod{169}$ are $n\equiv 70(84)\equiv 134\pmod{169}$ and $n\equiv 99(84)\equiv 35\pmod{169}$.

Thus, one solution has $n=35$, $x=168$, and $y=28$. Another is $n=169+134=303$, $x=168$, and then $y=2172$.

Etc.

It all comes down to having the solutions to $m^2\equiv -1\pmod{2k+1}$. There are exactly $2^t$ solutions, where $t$ is the number of distinct prime factors of $2k+1$ (all of which are required to be congruent to $1$ modulo $4$). Each solution generates an infinite family of values of $n$ and $y$ that solve the equation and that can be written down explicitly in terms of the solution. However, writing down the solutions to the congruence in terms of $k$, even when $2k+1$ is prime, seems pretty difficult (if it can be done at all, and I suspect there are no known efficient algorithms; added: $((p-1)/2)!$ and $p-((p-1)/2)!$ are solutions modulo $p$, but they are computationally expensive to calculate; using Hensel's Lemma to lift them for prime powers is relatively simple, and using the Chinese Remainder Theorem to glue them for a solution modulo $2k+1$ is fairly straightforward as well. The last one is relatively cheap, computationally, but difficult to write out explicitly in terms of $k$ alone).

So, given a $k$ such that $2k+1$ is the product only of primes congruent to $1$ modulo $4$, to find all $n$ and $y$ for which $(n,2k,y)$ is a solution we proceed as follows:

1. Find all solutions to the congruence $m^2\equiv -1\pmod{2k+1}$. This congruence has $2^t$ solutions modulo $2k+1$, where $t$ is the number of distinct prime factors of $2k+1$.

2. For each solution $m\equiv a\pmod{2k+1}$, and each integer $r$, let $n=ak+(2k+1)r$. Then $y = \frac{4n^2-x}{x+1}$ will be an integer.

3. Thus, each of the $2^t$ solutions to $m^2\equiv -1\pmod{2k+1}$ gives rise to an infinite family of solutions: if $m\equiv a\pmod{2k+1}$ is a solution to the congruence, then $$\left(ak+(2k+1)r, 2k, \frac{4(ak+(2k+1)r)^2 - 2k}{2k+1}\right),\qquad r\in\mathbb{Z}$$ is an integer solution to the original equation.

-

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$.

-

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$.

-