# Integer solutions to a particular degree 2 equation

Let $$q>5$$ be an odd sum of two nonzero squares and consider the equation $$X^2-mkX+m\frac{qk+1}{4}=0$$ for some integers $$m\ge 1$$ and $$7\le k\equiv 3\pmod{4}$$ depending on $$q$$. The condition on $$k$$ of course is so that the fraction is an integer. After running some test, it seems like

The equation has integer solutions for some $$m,k$$ if and only if $$q$$ is not a square.

This equation comes from trying to write a particular continued fraction as a sum of two unitary fractions, but the background is not really important here. Does anyone have any idea of how to start attacking this problem? From the numerical tests, it doesn't look like there is an obvious way to explicitly compute $$m,k$$ from $$q$$; so (assuming the claim is true) I am expecting a non constructive approach or method.

• This claim is incorrect. – Don Thousand Aug 21 '18 at 16:00
• @RushabhMehta care to explain why? – Angelo Rendina Aug 21 '18 at 16:54

We shall prove that the claim is correct, by setting $$q$$ as a square and then showing that an integral solution will lead to contradiction on $$k$$.

# Overview

Let $$p,q$$ be primes dividing $$k$$ and $$m$$ respectively by an odd number of times. First suppose $$2$$ divides $$m$$ an even number of times. Let $$\left[\frac{a}{p}\right]$$ denote the Legendre symbol. The approach is to form simultaneous quadratic reciprocity equations for all $$p$$ and $$q$$ (pairwise) using the original equation. Then using also the Law of quadratic reciprocity $$\left[\frac{p}{q}\right]\left[\frac{q}{p}\right] = (-1)^{(p-1)(q-1)/4},$$ solving all the equations will force an even number for primes $$p\equiv 3\pmod 4$$ dividing $$k$$. This in turn will force $$k\equiv 1 \pmod 4$$, contradicting the original assumption.

When $$2$$ divides $$m$$ by an odd number of times, we need to first show that $$k\equiv 7\pmod 8$$. Then later solving of the simultaneous equations will reveal that $$k\not\equiv 7 \pmod 8$$.

Proposition 1. Let $$k=\rho^2 u$$ and $$m=\sigma^2v$$ such that $$u$$ and $$v$$ are squarefree. Then the equation may be reduced to $$z^2u^2v-1 = ux^2 + vy^2$$ for some $$x,y,z\in\mathbb Z$$. In addition, we have $$\gcd(u,v) = 1$$

Proof. Solving for $$X$$, we have $$X = \frac{1}{2} \left(k m \pm \sqrt{k^2 m^2-km q-m}\right)$$ Since $$X\in\mathbb Z$$, we conclude that $$k^2m^2-kmq-m=w^2$$ for some $$w\in\mathbb Z$$. Write $$m = \sigma^2 v$$ such that $$v$$ is squarefree, then $$\sigma^2k^2v^2-kvq-v=(w/\sigma)^2$$ Here $$w/\sigma\in\mathbb Z$$, else $$(w/\sigma)^2\not\in\mathbb Z$$ which would contradiction LHS being integral. Since $$v$$ is squarefree, this shows that $$v$$ divides $$w/\sigma$$, therefore $$\sigma^2k^2v-kq-1= v(\frac{w}{\sigma v})^2 = vy^2$$ Now setting $$k=\rho^2 u$$, $$u$$ squarefree, and by assumption $$q$$ is a square, we have $$(\sigma\rho^2)^2u^2v - u(\rho \sqrt q)^2 - 1 = vy^2 \Longleftrightarrow z^2u^2v - ux^2-1 = vy^2$$ which is what we want. Clearly $$D=\gcd(u,v)=1$$, otherwise taking $$\pmod D$$ gives us $$-1 \equiv 0 \pmod D$$ This completes the proof.
$$\tag*{\square}$$

Observe that since $$u$$ and $$v$$ are squarefree, they are product of distinct primes. For each prime $$p$$ we can take $$\pmod p$$ to get a quadratic reciprocity equation, which is first the half of our goal.

We first assume that $$2$$ divides $$m$$ and even number of times, so that $$v$$ is now odd. The other case is much more complex.

We fix a prime factorization notation since our next step requires taking mod each prime:

Definition 2. Let the factorization of $$u$$ and $$v$$ be as follows, noting that both are odd: \begin{align} u &= (r_1r_2\cdots r_a)(s_1s_2\cdots s_b)\\ v &= (t_1t_2\cdots t_c)(w_1w_2\cdots w_d)\\ r_i,t_i &\equiv 1 \pmod 4\\ s_i,w_i &\equiv 3 \pmod 4 \end{align}

For the second half of our proof, we use the simultaneous quadratic reciprocity equations to obtain an equality relating $$b$$ and $$d$$.

Proposition 3. The product of all distinct symbols $$\left[\frac{p}{q}\right]$$ where $$p$$ divides $$u$$ or $$v$$ and $$q$$ divides the other, satisfies $$(-1)^{bd} = \prod_{p|u,q|v \text{ or } p|v, q|u} \left[\frac{p}{q}\right] = (-1)^{b+d}$$

We remark that $$\gcd(u,v)=1$$ from proposition 1, so that all the symbols here are $$\pm 1$$.

Proof. From the equation in proposition 1, we obtain \begin{align} vy^2 &\equiv -1 \pmod{r_i}\\ vy^2 &\equiv -1 \pmod{s_i}\\ ux^2 &\equiv -1 \pmod{t_i}\\ ux^2 &\equiv -1 \pmod{w_i} \end{align} For $$r_i,t_i\equiv 1 \pmod 4$$, $$-1$$ is a quadratic residue and hence \begin{align} 1 &= \left[\frac{v}{r_i}\right]=\left(\prod_{j=1}^c\left[\frac{t_j}{r_i}\right]\right)\left(\prod_{k=1}^d\left[\frac{w_k}{r_i}\right]\right)\\ 1 &= \left[\frac{u}{t_i}\right]=\left(\prod_{j=1}^a\left[\frac{r_j}{t_i}\right]\right)\left(\prod_{k=1}^b\left[\frac{s_k}{t_i}\right]\right) \end{align} For $$s_i,w_i\equiv 3 \pmod 4$$, $$-1$$ is not a quadratic residue and hence \begin{align} -1 &= \left[\frac{v}{s_i}\right]=\left(\prod_{j=1}^c\left[\frac{t_j}{s_i}\right]\right)\left(\prod_{k=1}^d\left[\frac{w_k}{s_i}\right]\right)\\ -1 &= \left[\frac{u}{w_i}\right]=\left(\prod_{j=1}^a\left[\frac{r_j}{w_i}\right]\right)\left(\prod_{k=1}^b\left[\frac{s_k}{w_i}\right]\right) \end{align} Taking the products over all $$r_i,s_i,t_i,w_i$$, we have \begin{align} 1 &= \prod_{i=1}^a\left[\frac{v}{r_i}\right]=\prod_{i=1}^a\left\{\left(\prod_{j=1}^c\left[\frac{t_j}{r_i}\right]\right)\left(\prod_{k=1}^d\left[\frac{w_k}{r_i}\right]\right)\right\}\\ (-1)^b &= \prod_{i=1}^b\left[\frac{v}{s_i}\right]=\prod_{i=1}^b\left\{\left(\prod_{j=1}^c\left[\frac{t_j}{s_i}\right]\right)\left(\prod_{k=1}^d\left[\frac{w_k}{s_i}\right]\right)\right\}\\ 1 &= \prod_{i=1}^c\left[\frac{u}{t_i}\right]=\prod_{i=1}^c\left\{\left(\prod_{j=1}^a\left[\frac{r_j}{t_i}\right]\right)\left(\prod_{k=1}^b\left[\frac{s_k}{t_i}\right]\right)\right\}\\ (-1)^d &= \prod_{i=1}^d\left[\frac{u}{w_i}\right]=\prod_{i=1}^c\left\{\left(\prod_{j=1}^a\left[\frac{r_j}{w_i}\right]\right)\left(\prod_{k=1}^b\left[\frac{s_k}{w_i}\right]\right)\right\} \end{align} Finally, we combine the 4 products into one, although we do not write it down. It can be observed that on the LHS we have $$(-1)^{b+d}$$, while the RHS can be observed to be the product of all combinations of $$\left[\frac{r_i}{t_j}\right], \left[\frac{r_i}{w_j}\right], \left[\frac{s_i}{t_j}\right], \left[\frac{s_i}{w_j}\right], \left[\frac{t_i}{r_j}\right], \left[\frac{t_i}{s_j}\right], \left[\frac{w_i}{r_j}\right], \left[\frac{w_i}{s_j}\right]$$

Now, we use the Law of Quadratic Reciprocity: $$\left[\frac{p}{q}\right] \left[\frac{q}{p}\right] = (-1)^{(p-1)(q-1)/4},$$ for all the pairs involved as before. If either $$p,q\equiv 1 \pmod 4$$, then the product of symbols is $$1$$.

For the remaining case $$p,q\equiv 3 \pmod 4$$, the produt of symbols is $$-1$$. This happens between parings of $$s_i$$ and $$w_j$$, which has $$b$$ and $$d$$ elements respectively. Therefore the product of the symbols is $$(-1)^{bd}$$.

Equating the two different ways of computing the product of symbols, we obtain $$(-1)^{b+d} = \prod_{p|u,q|v \text{ or } p|v, q|u} \left[\frac{p}{q}\right] = (-1)^{bd}$$ which completes the proof. $$\tag*{\square}$$

Our final step is as follows:

Lemma 4. Let $$u,v$$ and their prime factorization be as defined in Definition 2. If $$(-1)^{bd} = (-1)^{b+d},$$ then $$u \equiv 1\pmod 4$$ Furthermore, $$k \equiv 1 \pmod 4$$

Proof. By considering the parity of $$b$$ and $$d$$, we see that $$(-1)^{bd} = (-1)^{b+d}$$ can hold if and only if $$b$$ and $$d$$ are both even. Noting that $$r_i\equiv 1\pmod 4$$ and $$s_i\equiv 3\pmod 4$$, this gives us $$u = (r_1r_2\cdots r_a)(s_1s_2\cdots s_b) \equiv (1)\cdot(1) \equiv 1\pmod 4$$ Recall that $$k = \rho^2 u$$ Since $$k$$ is odd, $$\rho$$ is also odd and hence $$\rho^2\equiv 1\pmod 4$$. Therefore $$k\equiv 1 \pmod 4,$$ completing the proof. $$\tag*{\square}$$

We ended with a contradiction on the condition of $$k$$, getting $$k\equiv 1\pmod 4$$, therefore there cannot be an integral solution.

Other case: $$2$$ divides $$m$$ an odd number of times
Proposition 1 still holds, except that now $$v$$ is even. We first show that

Proposition 5. For $$z^2u^2v - 1 = ux^2 + vy^2$$ and $$u\equiv 3\pmod 4$$,$$v\equiv 0\pmod 2$$, we have $$u\equiv 7\pmod 8$$

Proof. Taking $$\pmod 2$$, we see that $$x$$ is odd. Now taking $$\pmod 4$$, we have \begin{align} z^2v - 1 &\equiv 3 + vy^2 \pmod 4 \\ z^2v &\equiv vy^2 \pmod 4\\ z^2(v/2) &\equiv (v/2)y^2 \pmod 2\\ z &\equiv y \pmod 2 \end{align} where the last line is because $$v/2$$ is odd (since $$v$$ is squarefree). If $$z,y$$ are both even then $$-1 \equiv ux^2 \equiv u \pmod 8$$ Otherwise \begin{align} z^2u^2v -1 &\equiv ux^2 + vy^2 \pmod 8\\ v-1 &\equiv u+v\pmod 8\\ -1&\equiv u \pmod 8 \end{align} So that for both cases, $$u\equiv 7\pmod 8$$. $$\tag*{\square}$$

We need factorization of primes split into groups of $$\pmod 8$$, since their symbol $$\left[\frac{2}{p}\right]$$ differs:

Definition 6. Let the factorization of $$u,v$$ be \begin{align} u &= (r_1r_2\cdots t_a)(s_1s_2\cdots s_b)(e_1e_2\cdots e_g)(f_1f_2\cdots f_h)\\ v &= 2(t_1t_2\cdots t_c)(w_1w_2\cdots w_d)\\ r_i &\equiv 1 \pmod 8\\ s_i &\equiv 3 \pmod 8\\ e_i &\equiv 5 \pmod 8\\ f_i &\equiv 7 \pmod 8\\ t_i &\equiv 1 \pmod 4\\ w_i &\equiv 3 \pmod 4\\ \end{align}

We derive in a fashion similar to proposition 3:

Preposition 7. The product of all distinct Legendre symbols $$\left[\frac{p}{q}\right]$$ where $$p$$ divides one of $$u$$ or $$v$$ and $$q$$ divides the other satisfies $$(-1)^{b+h+d} = \prod_{p|u,q|v \text{ or } p|v,q|u} \left[\frac{p}{q}\right] = (-1)^{bd+hd+b+g}$$

Proof. As in proposition 3, the only equations that give a product as a power of $$-1$$ are the ones $$\equiv 3\pmod 4$$. These are $$s_i,f_i,w_i$$ with $$b,h,d$$ elements each, giving $$b+h+d$$ equations, hence the overall product $$(-1)^{b+h+d}$$.

For the other way of computing product of all symbols, if we ignore prime $$2$$ first then a similar derivation for $$\equiv 3\pmod 4$$ primes gives $$(-1)^{bd}\cdot (-1)^{hd} = (-1)^{bd+hd}$$ This is simply the number of ways to pair $$s_i$$ with $$w_j$$ and $$f_i$$ with $$w_j$$. For prime $$2$$, the Legendre symbol $$\left[\frac{2}{p}\right]$$ is $$-1$$ only when $$p\equiv 3,5\pmod 8$$, corresponding to primes $$s_i$$ and $$e_i$$. There are $$b$$ and $$g$$ elements respectively, giving a product of $$(-1)^{b+g}$$. Therefore putting everything together we have $$(-1)^{b+h+d} = (-1)^{bd+hd+b+g}$$ $$\tag*{\square}$$

The final part of this case:

Lemma 8. Following definition 6 and assume that $$(-1)^{b+h+d} = (-1)^{bd+hd+b+g}$$ Then $$u\not\equiv 7\pmod 8$$

Proof. We note that \begin{align} u &= (\prod_{i=1}^a r_i)(\prod_{i=1}^bs_i)(\prod_{i=1}^ge_i)(\prod_{i=1}^hf_i)\\ u &\equiv 3^b5^g7^h \pmod 8 \end{align} Equating the indices of proposition 7: \begin{align} b+h+d &\equiv bd+hd+b+g \pmod 2\\ d(b+h+1) &\equiv h+g \pmod 2 \end{align} If $$d\equiv 0\pmod 2$$, then $$h\equiv g\pmod 2$$. If $$h,g$$ even: $$u \equiv 3^b \not\equiv 7\pmod 8$$ else $$h,g$$ odd: $$u\equiv 3^b \cdot 5\cdot 7 \equiv 3^{b+1}\not\equiv 7\pmod 8$$

Alternatively, $$d\equiv 1\pmod 2$$ and $$b+h+1 \equiv h+g \pmod 2 \implies b+1 \equiv g \pmod 2$$ If $$b$$ odd and $$g$$ even: $$u \equiv 3\cdot 1\cdot 7^h \equiv 3,5 \not\equiv 7 \pmod 8$$ otherwise $$b$$ even and $$g$$ odd: $$u \equiv 1\cdot 5 \cdot 7^h \equiv 3,5 \not\equiv 7\pmod 8$$

Therefore in all cases $$u\not\equiv 7 \pmod 8$$.

$$\tag*{\square}$$

This contradicts the initial assumption of $$u\equiv 7\pmod 8$$, therefore there cannot be an integral solution.

• This looks amazing, which explains one direction of the claim. Thanks! It would be amazing to understand why a solution exists when $q$ is not a square (in particular, a prime). – Angelo Rendina Oct 16 '18 at 1:07
• @AngeloRendina The problem is that the other direction is not true and more conditions are required. Using $m=1,k=7,q=13=2^2+3^2$, we get the equation $$X^2-7X+23=0$$ which has no integer solutions. When $q$ is square, we have a nice balanced equation as in proposition $1$ which will force $m,k\equiv 1 \pmod 4$, although I failed to find a short way to show that. However when $q$ is not square it looks quite a bit trickier. – Yong Hao Ng Oct 16 '18 at 3:18
• Probably I was not clear in the statement, I will edit the question. The thing is that if $q=13$, we may take $m=2$ and $k=11$ to obtain $$X^2-22X+72=0$$ which does indeed admit integer solutions. – Angelo Rendina Oct 16 '18 at 14:18
• @AngeloRendina Thanks for the edit. Looks like it was clear before but somehow I did not get it, sorry about that. I think the same approach might yield a condition to finding the right $m$ and $k$, will give it a try when I have the time. Thanks again! – Yong Hao Ng Oct 16 '18 at 17:11
• Just as an update, if $q$ is prime then there always seem to be a pair $(k,m)$ for which the equation has solutions, with $m$ even and $q\not| m$ - at least up to $q\sim 10^5$. – Angelo Rendina Oct 24 '18 at 2:08