# solutions for modular arithmetic equation

what are the solutions for $$x$$ and $$y$$ where $$x,y$$ are positive integers and

please can you give me examples of solutions or the set of all solution or even better instructions on how I can compute this by myself

This was a question given to me by my math teacher before the holiday began, I've calculated values based on modular congruences before but most of those have been linear congruences so i'm not sure how to approach this

• $x$ can't be a divisor of $y$, likewise $y$ can't be a divisor of $x$
– user645636
Commented Dec 16, 2019 at 18:22
• @RoddyMacPhee Seems not true. For example, you can have $x=y=2$. Commented Dec 16, 2019 at 18:32
• yeah but that's because $-1\equiv 1\bmod 2$
– user645636
Commented Dec 16, 2019 at 18:34
• polynomial remainder theorem is what I applied. but reallt it's a question of quadratic residues.
– user645636
Commented Dec 16, 2019 at 18:57
• This is an interesting question. It would be a shame if it started attracting negative attention, so please take a look at our guide for new askers, and add a bit of background material to it. Commented Dec 16, 2019 at 20:15

This looks like a (multiple) Vieta jumping exercise.

Below are some guides which may help, the last part is not complete yet. The gist is to reduce the simultaneous equation into a Hyperbola $$(x,y)=(2u,2v)$$ and
$$H: 2u^2-2u+2v^2-2v+1-kuv =0$$ and then use Vieta jump to determine the possible values of $$k$$.

Then, it looks like there are infinitely many solutions and the Vieta jumping procedure can generate them, for each $$k$$. Here's a sample big solution I've found for $$k=13$$: $$(x,y) = (2u,2v) = (846531455562415407816752925060250, 5368981185596626268534239136521058)$$

Clearly $$(x,y)=(1,1)$$ is a solution. We exclude it to make our arguments easier.

Lemma 1. If $$(x,y)\neq (1,1)$$ is a solution then \begin{align} (x,y) &=(2u,2v), & \gcd(u,v)&=1 \end{align}

Proof. Let $$d=\gcd(x,y)$$. Taking modulo $$d$$, first equation becomes $$(x-1)^2\equiv-1\pmod y \implies (-1)^2\equiv -1 \pmod d$$ This shows that $$d=1$$ or $$2$$. Hence if we can show that $$d=2$$ then we are done.

Suppose instead that $$x,y$$ are odd in which case $$\gcd(x,y)=1$$. The equations thus becomes \begin{align*} (x-1)^2 &\equiv -1 \pmod y \implies x^2-2x+y^2-2y+2\equiv 0 \pmod y\\ (y-1)^2 &\equiv -1 \pmod x \implies x^2-2x+y^2-2y+2\equiv 0 \pmod x \end{align*} Since $$\gcd(x,y)=1$$, by Chinese Remainder Theorem we get $$x^2-2x+y^2-2y+2 \equiv 0 \pmod{xy}$$ Therefore $$x^2-2x+y^2-2y+2-kxy=0$$ for some integer $$k$$. We shall use Vieta jumping to show that this has no solutions.

WLOG we may assume that $$x \geq y$$. Among all solution pairs, we also choose $$(x,y)$$ such that $$x$$ is minimal. Since $$(x,y)\neq (1,1)$$, $$\gcd(x,y)=1$$ forces $$x\neq y$$, hence $$x \geq y+1$$. This gives an inequality $$x^2 \geq y^2+2y+1\implies x \geq (y^2+2y+1)/x > (y^2-2y+2)/x$$ Now we see that $$x$$ is a solution to the integer quadratic equation $$X^2-(2+ky)X+(y^2-2y+2)=0$$ Let $$r$$ be the other root, then Vieta's formula says \begin{align} x+r &= 2+ky, & xr &=y^2-2y+2 \end{align} The first equation says $$r$$ is integral and the second says $$r$$ is positive. The second equation also gives $$r = (y^2-2y+2)/x < x$$ This means that we have a new solution $$(r,y)$$, since $$r$$ is a positive integer, such that $$r,y$$ are both less than $$x$$. It contradicting the minimality of $$x$$, therefore there are no solutions and the initial assumption of $$d=\gcd(x,y)=1$$ is wrong.

Hence $$d=2$$ and we are done. $$\tag*{\square}$$

Now (still ignoring $$(x,y)=(1,1)$$) letting $$(x,y)=(2u,2v)$$ the equations become \begin{align*} 4u^2-4u+2 &\equiv 0\pmod {2v} &\implies 2u^2-2u+2v^2-2v+1 \equiv 0\pmod{v}\\ 4v^2-4v+2 &\equiv 0\pmod {2u} &\implies 2u^2-2u+2v^2-2v+1 \equiv 0\pmod{u} \end{align*} Once again from $$\gcd(u,v)=1$$ and CRT it becomes $$2u^2-2u+2v^2-2v+1 -kuv = 0$$ for some integer $$k$$. This part is incomplete, but what I suspect is

Conjecture 2. The Hyperbola $$H: 2u^2-2u+2v^2-2v+1 -kuv=0$$ has positive integeral points $$(u,v)\in H$$ if and only if $$k=9,13,25$$.

The reasoning is from computational results (i.e. what @lhf has shown), which will yield these 3 values. What I suspect is more Vieta jumping will lead to the solution, yet to try.

Some computation examples: for $$k=13$$ $$(u,v) = (62127330605,394031984209) \in H: 2u^2-2u+2v^2-2v+1-13uv=0$$ Indeed, setting $$(x,y) = (2u,2v)$$ we can check that \begin{align*} (x-1)^2 &\equiv -1 \pmod y\\ (y-1)^2 &\equiv -1 \pmod x \end{align*}

Here are the solutions $$x \le y < 10^6$$, found with a computer search: $$\begin{array}{r} x & 34 & 58 & 6554 & 22642 & 42986 \\ y & 218 & 250 & 41570 & 961754 & 533866 \end{array}$$

• $y$ is never divisible by 3 you might note as -1 is never a quadratic residue mod 3 ( meaning no multiple of it can).
– user645636
Commented Dec 17, 2019 at 0:53
• @RoddyMacPhee For the same reason all the odd prime factors of both $x$ and $y$ must be $\equiv1\pmod4$. Commented Dec 17, 2019 at 11:26
• @JyrkiLahtonen and by $1\not\equiv -1\bmod x$ for $x>2$ it can be shown the only factor they can have in common is 2.
– user645636
Commented Dec 17, 2019 at 11:34