Prove that there exists an integer $n \geq 1$, such that number of all pairs $(a, b)$ of positive integers, satisfying $$\frac{1}{a-b}-\frac{1}{a}+\frac{1}{b}=\frac{1}{n}$$exceeds $2024.$
Problem
Source: Greece National Olympiad 2024, Problem 4
Tags: number theory
24.02.2024 17:54
The problem is equivalent to n = ((a-b)ab)/(a^2+b^2 - ab). Define f(a, b) = (a-b)(ab)/(a^2+b^2 - ab). Note that f(xa, xb) = xf(a, b) for all naturals x. Btw, for positive rational numbers define their LCM as the smallest natural number that when decided by all of them gives a natural numbers. So all that’s left is to take n = LCM( f(1, 1), f(2, 1), f(3, 1),… f(2025, 1)).
24.02.2024 17:55
Rearrange it this equation to arrive at \[ n\left(a^2-ab+b^2\right) = ab(a-b). \]Set $a=da_1$ and $b=db_1$ where $d={\rm gcd}(a,b)$. We then get \[ n\left(a_1^2-a_1b_1+b_1^2\right) = da_1b_1\left(a_1-b_1\right). \]Now, it is not hard to see that ${\rm gcd}\left(a_1^2-a_1b_1+b_1^2,a_1b_1\right)=1$. Furthermore if $p$ is a prime dividing both $a_1^2-a_1b_1+b_1^2$ and $a_1-b_1$, then $a_1\equiv b_1\pmod{p}$, as such, $a_1^2-a_1b_1+b_1^2\equiv b_1^2\pmod{p}$, yielding $p\mid a_1,b_1$, a contradiction. Combining, we find that there is some $\ell$ such that \[ d=\ell\left(a_1^2-a_1b_1+b_1^2\right)\quad\text{and}\quad n=\ell a_1b_1\left(a_1-b_1\right) \]Lastly, let $p_1<p_2<\cdots<p_L$ be primes where $L\gg 2024$. Consider $n=\textstyle \prod_{1\le i\le L}p_i(p_i-1)$. Observe that taking $a_1=p_i, b_1=1$, $\ell = \left(\textstyle\prod_j p_j(p_j-1)\right) /(p_i(p_i-1))$, we can generate at least $L$ such distinct pairs. This completes the proof.
25.02.2024 02:00
It is equivalent to $\frac{a^2b - ab^2}{a^2 - ab + b^2} = n$. Let $a = kb \Rightarrow \frac{bk(k-1)}{k^2 - k + 1} = n$. Let $b = m(k^2 - k + 1)$. Then $mk(k- 1) = n$. For $n = 2026!$, $k(k - 1)| 2026!$ for $k = 2 , 3 , ... , 2026$. For each $k$ we find an integer $m$. Each pair $(k , m)$ defines a unique pair $(a , b) = (km(k^2 - k + 1) , m(k^2 - k + 1)$ , so we have at least $2025 > 2024$ solutions and we are done !
25.02.2024 20:49
JustARandomGuy__ wrote: It is equivalent to $\frac{a^2b - ab^2}{a^2 - ab + b^2} = n$. Let $a = kb \Rightarrow \frac{bk(k-1)}{k^2 - k + 1} = n$. Let $b = m(k^2 - k + 1)$. Then $mk(k- 1) = n$. For $n = 2026!$, $k(k - 1)| 2026!$ for $k = 2 , 3 , ... , 2026$. For each $k$ we find an integer $m$. Each pair $(k , m)$ defines a unique pair $(a , b) = (km(k^2 - k + 1) , m(k^2 - k + 1)$ , so we have at least $2025 > 2024$ solutions and we are done ! Whats the motivation for the technique or any other similar problem??
25.02.2024 22:27
telemathic wrote: JustARandomGuy__ wrote: It is equivalent to $\frac{a^2b - ab^2}{a^2 - ab + b^2} = n$. Let $a = kb \Rightarrow \frac{bk(k-1)}{k^2 - k + 1} = n$. Let $b = m(k^2 - k + 1)$. Then $mk(k- 1) = n$. For $n = 2026!$, $k(k - 1)| 2026!$ for $k = 2 , 3 , ... , 2026$. For each $k$ we find an integer $m$. Each pair $(k , m)$ defines a unique pair $(a , b) = (km(k^2 - k + 1) , m(k^2 - k + 1)$ , so we have at least $2025 > 2024$ solutions and we are done ! Whats the motivation for the technique or any other similar problem?? I first tried of solving for one variable using the determinant and setting it to be a perfect square , but that didn't work for me. I knew i couldn't do it this way so I then wanted to find a closed form of the pairs $(a , b)$ such that the fraction is constant (and also find that constant $n$) for many pairs $(a , b)$. So just to make it simpler i tried $a = kb$ and then after simplifying the second substitution came naturally in order to get rid of the denominator (since $k^2 - k + 1$ can't divide $k(k - 1)$, nor have any common factors anyway).
12.05.2024 18:07
Basicly the same solution as one of the above. Rearranging we get $n=\frac{ab(a-b)}{a^2+b^2-ab}$. Calculate infinitely many different values of $n$ for coprime $a$ and $b$. Now take any $2024$ values of them, say $n_1,\ldots, n_{2024}$. Then $n=lcm(n_1,\ldots,n_{2024})$ clearly satisfies the condition
12.05.2024 18:17
04.06.2024 22:39
For some $(a',b')$ with $b'<a'$ let $f(a',b')=\frac{1}{a'-b'}-\frac{1}{a'}+\frac{1}{b'}=\frac{c}{d}$ for relatively prime positive integers $c$ and $d$. Then notice that for any positive integer $x$, $f(a'xc,b'xc)=\frac{1}{dx}$. So it is sufficient to choose a $n$ such that $d|n$ for there to exist a solution $(a,b)$ in the ratio of $(a',b')$. Obviously we can then choose an $x$ such that there exists at least $2024$ distinct solutions. Remark: I did not find this to be an interesting question as the RHS could be replaced with literally any rational homogeneous function of degree $-1$.