Let $a$ and $b$ be positive integers such that $\text{gcd}(a, b) + \text{lcm}(a, b)$ is a multiple of $a+1$. If $b \le a$, show that $b$ is a perfect square.
Problem
Source: INAMO 2023 P5 (OSN 2023)
Tags: number theory, greatest common divisor, least common multiple, Indonesia, Indonesia MO
30.08.2023 12:07
$a=dx,b=dy \implies dx+1|d+dxy\implies dx+1|xy+1,(y \geq d)$ $\implies dx+1|xy+1-dx-1=x(y-d)$ $\implies dx+1|y-d$ If $y-d$ is not $0,$ \[dx+1 \leq y-d<y \leq x \leq dx\]Which is a contradiction So $d-y=0 \iff d=y$ So $b=dy=y^2$
30.08.2023 12:16
If $y-d\neq 0$, then it must be $dx+1\le |y-d|$ EDIT: @below Ah sorry, I misread that part
30.08.2023 12:18
Wildabandon wrote: If $y-d\neq 0$, then it must be $dx+1\le |y-d|$ We have $dx+1|xy+1 $ which means $y \geq d$
03.09.2023 15:31
Seicchi28 wrote: Let $a$ and $b$ be positive integers such that $\text{gcd}(a, b) + \text{lcm}(a, b)$ is a multiple of $a+1$. If $b \le a$, show that $b$ is a perfect square. Let $a=dx$, $b=dy$ with $x \geqslant y$ and $GCD(x,y)=1$ \begin{align*} dx+1 &\mid dxy+d \\ dx+1 &\mid dxy+d - y(dx+1) \\ dx+1 &\mid d-y \end{align*}Observe, that $$|dx+1| = dx+1 > dx \geqslant \max(d,x) \geqslant \max(d,y) > |d-y|$$So $d-y = 0 \implies b = d^2$. QED $\blacksquare$
06.09.2023 21:01
I have Idea : Case 1 : if $a = b$ , we get $(a, b) + [a, b]$ = $a + a = 2a$ so, we have $2a = 2a + 2 - 2 = 2(a + 1) - 2$. so, $(a+1) | 2$. Only solution $a = 1$ Case 2 : $a > b$ so, we get $(a, b) + [a, b]$ = $m + mnk$ for some positive integer $m, n, k$. we have $n > k$ so $m + mnk$ ≡ 0 mod (mn + 1) $m + mnk + k - k$ ≡ 0 mod (mn+1) $k(mn + 1) + (m - k)$ ≡ 0 mod (mn+1) so we get $m - k$ ≡ 0 mod $(mn+1)$ coz, $k < n$ so, $k < mn$ and $k$ ≤ $m$ < $(mn+1)$ we must have $m$ ≡ $k$ mod(mn +1) so, $m = k < (mn + 1)$ and we get $b = mk = m^2$. CMIIW..... :-(
31.05.2024 21:44
Let $a=da_0$, $b=db_0$, with $\gcd(a_0,b_0)=1$. We have $da_0+1\mid d+da_0b_0$, or that $\gcd(d+da_0b_0,da_0+1)=da_0+1$. Note that \begin{align*} \gcd(d+da_0b_0,da_0+1) &= \gcd(1+a_0b_0, da_0+1) \\ &= \gcd(a_0(b_0-d),da_0+1) \\ &= \gcd(b_0-d, da_0+1). \end{align*}Suppose, FTSOC, that $b_0\ne d$. Then, $b_0-d \ge da_0+1$, implying $b_0 \ge a_0(d+1)+1 > a_0$, absurd. Thus, $b_0=d$, and $b = d^2$, as desired. $\blacksquare$