Show the existence of infinitely many natural numbers $x$, $y$ such that $x(x+1)\mid y(y+1)$ but $x,x+1\not\mid y,y+1:$ how could we guess the hint?

Question

Question

Show the existence of infinitely many natural numbers $x$, $y$ such that $$x(x+1)\mid y(y+1)\tag1$$ but $$x\not\mid y,\text{ and }(x+1)\not\mid|y\tag2$$ and also $$x\not\mid(y+1),\text{ and }(x+1)\not\mid(y+1)\tag3$$

Answer

I used a hint which was to take $x=36k+14$ and $y=(12k+5)(18k+7):$

$$\begin{align}x(x+1)&=(36k+14)(36k+15)\\&=2\cdot3\cdot(18k+7)(12k+5)\end{align}$$ $$\begin{align}y(y+1)&=(12k+5)(18k+7)[(12k+5)(18k+7)+1]\\&=(12k+5)(18k+7)(216k^2+174k+36)\\&=2\cdot3\cdot(12k+5)(18k+7)(36k^2+29k+6)\end{align}$$

So $(1)$ is proved. I also managed to prove $(2)$ and $(3),$ thereby proving the claim using the hint.

However, now I'm confused on how you are supposed to get $x=36k+14$ and $y=(12k+5)(18k+7)$.
Can someone kindly help me in this?
Is it just trusting your instincts or is there a specific way on how to get this?
Or are there any other methods to prove it other than this?

Answer 1

We will never know what the originator of the hint actually thought, but this is one way how they could have been reasoning:

$x$ and $x+1$ are coprime, and so are $y$ and $y+1$. Thus, every prime factor of either $x$ or $x+1$ must be a prime factor of either $y$ or $y+1$ but not both. Let's start with some small primes to the first degree, hoping that this will simplify things. So, take the primes $2$ and $3$. If we make, say, $x=2u$ and $x+1=3v$ then $x(x+1)=6uv$. Then we make $y=uv$ and, if we can make $6\mid y+1$, that would obviously make $x(x+1)\mid y(y+1)$.

Now, what should $u$ and $v$ be like in order to prevent $x\mid y, x\mid y+1, x+1\mid y, x+1\mid y+1$? Let's say it is very useful that none of $u,v$ is divisible by either $2$ or $3$. Why? Because then you can immediately claim that neither $x$ nor $x+1$ divide $y$. Also, if $x\mid y+1$ then $u\mid y+1$ and with $u\mid y=uv$ this would mean that $u=1$. Similarly, if $x+1\mid y+1$ then $v\mid y+1$ and with $v\mid y$ you get $v=1$. So the additional condition is just that $u,v>1$.

To recap: we want to generate $u,v$ such that:

• $3v=2u+1$,
• $u,v$ are both bigger than $1$,
• $u,v$ are not divisible by either $2$ or $3$, i.e. $u,v\equiv\pm 1\pmod 6$, and
• $6\mid uv+1$ i.e. $uv\equiv -1\pmod 6$.

Of course, $u=12k+5$ and $v=18k+7$ for $k\ge 0$ satisfies all the conditions above. Let's see how to reconstruct this: from the conditions above we know that $u,v\equiv\pm 1\pmod 6$, and to make their product $\equiv -1\pmod 6$ we want:

• Either $u\equiv 1\pmod 6$ and $v\equiv -1\pmod 6$
• Or $u\equiv -1\pmod 6$ and $v\equiv 1\pmod 6$.

Right! - Now let's try to construct the solution of the first type, and I guess you can just as easily construct a solution of the second type.

So $u=6m+1, v=6n-1$ for $m,n\in\mathbb Z$. This already makes $2,3\not\mid u,v$. To make $u,v>1$ you only need $m,n\ge 1$. Now, what about $3v=2u+1$? This implies:

$$3(6n-1)=2(6m+1)+1$$

i.e.

$$18n-6=12m$$

i.e.

$$3n-1=2m$$

This is a linear Diophantine equation which has as solutions $m=3k+1, n=2k+1, k\in\mathbb Z$, which then makes for the solution:

$$x=2u=2(6m+1)=2(6(3k+1)+1)=36k+14$$ $$y=uv=(6m+1)(6n-1)=(6(3k+1)+1)(6(2k+1)-1)=(18k+7)(12k+5)$$

(and, to make $m,n\ge 1$ we then restrict to $k\ge 0$).

---

You can vary this construction by:

• Choosing other (mutually coprime) factors, rather than $2$ and $3$,
• Swapping the role of $2$ and $3$,
• Swapping the role of $y$ and $y+1$: we could've insisted that $6\mid y$ and $uv=y+1$,
• Swapping the remainder $\pmod 6$ for $u$ and $v$.

Answer 2

Not sure it helps but you can think in this way: try to solve $$\frac{y(y+1)}{x(x+1)} = 2$$ which is equivalent to

$$(2y+1)^2 - 2 ( 2x+1)^2= -1$$

with infinitely many solutions

$$(2y+1) + (2x+1)\sqrt{2}= ( 1+\sqrt{2})^{2n+1}$$

For instance take $2n+1= 11$ and get $$y = 4059 \\ x = 2870$$

Now, notice that $\frac{y}{x}\simeq \sqrt{2}$ so between $1$, and $2$, thus not an integer.

$\bf{Added:}$

One can consider the equation $$y(y+1) = k x(x+1)$$ equivalent to $$(2y+1)^2 - k (2x+1)^2 = -(k-1)$$

We can look for solutions

$$(2y+1) + (2x+1) \sqrt{k} =b + a\sqrt{k} =(1+ \sqrt{k})(v + u\sqrt{k})^m$$

where $v^2 - k u^2 = 1$ gives a fundamental solution to the Pell equation. For instance if $k=3$ we get

$$(2y+1) + (2x+1) \sqrt{3} = (1+ \sqrt{3})(2 + \sqrt{3})^m$$ with $m\ge 1$ arbitrary. Again $\frac{y}{x}$ and all of the similar fractions are $\simeq \sqrt{3}$ so not integers.