Initially, two distinct positive integers $a$ and $b$ are written on a blackboard. At each step, Andrea picks two distinct numbers $x$ and $y$ on the blackboard and writes the number $gcd(x, y) + lcm(x, y)$ on the blackboard as well. Let $n$ be a positive integer. Prove that, regardless of the values of $a$ and $b$, Andrea can perform a finite number of steps such that a multiple of $n$ appears on the blackboard.
Problem
Source: MEMO 2022 I4
Tags: number theory
11.09.2022 08:23
First i will prove that Andrea can perform a finite number of steps such in the end blackboard contains two numbers $x,y$ such that $x|y$ Let $a_1=a,a_2=b$ and $a_k=gcd(a_1,a_{k-1})+lcm(a_1,a_{k-1})$ for $i\geq 3$ Obviously Andrea can write on the blackboard at some point every number of the sequence $(a_n)_{n\in \mathbb{N}}$ Note that $gcd(a_1,a_{i+1})=gcd(a_1,gcd(a_1,a_i)+lcm(a_1,a_i))=gcd(a_1,a_i)$ for every $i\geq 1$ and thus if we set $gcd(a,b)=c$ then $a_{k+1}=c+lcm(a_1,a_k)=c+\dfrac{a_1a_k}{c}$ for $k\geq 1$. It's clear that $c|a_i \forall i\in \mathbb{N}$ so let $a_i=cb_i$ where $(b_n)_{n\in \mathbb{N}}$ is a sequence of positive integers. Clearly $gcd(b_1,b_2)=1$ Then $b_{k+1}=1+b_1b_k$ . Observe that $b_3=b_1b_2+1\equiv 1 \pmod {b_2},b_4=b_1b_3+1\equiv b+1 \pmod {b_2}$ and inductively we get $b_k=1+b_1+b_1^2+..+b_1^{k-3} \pmod {b_2}$. Since $gcd(b_1,b_2)=1$ we know that $b_1^{\varphi(b_2)}\equiv 1 \pmod {b_2}$ and thus $b_{b_2\varphi(b_2)+2}\equiv 1+b_1+b_1^2+..+b_1^{b_2\varphi(b_2)-1}=b_2( 1+b_1+b_1^2+..+b_1^{\varphi(b_2)-1})\equiv 0 \pmod {b_2}$ Hence $b_2|b_{b_2\varphi(b_2)+2}\Rightarrow a_2|a_{b_2\varphi(b_2)+2}$ and thus we found $x,y$ on the blackboard such that $x|y$. Now focus on that $x,y$. Write $y=mx$ and note that $gcd(x,y)+lcm(x,y)=x+y$ and $gcd(x,x+y)+lcm(x,x+y)=2x+y$ and inductively we get that Andrea can write on the blackboard every number of the form $kx+y,k\in \mathbb{N}$. So Andrea can write both $p=(2mn+1-m)+b=a(2mn+1)$ and $q=a(2mn-1-m)+b=a(2mn+1)$. Now observe that $gcd(p,q)=gcd(a(2mn-1),a(2mn+1))=a\cdot gcd(2mn-1,2mn+1)=a$ so Andrea can write on the blackboard the number $z=gcd(p,q)+lcm(p,q)=a+\dfrac{pq}{a}=a+a(2mn+1)(2mn-1)=a(1+4m^2n^2-1)=0\pmod n$ so $n|z$ and we are done.
13.09.2022 00:28
One can simplify the argument slightly by iterating with $b_3$ instead of $b_1$: First of all, we can w.l.o.g. assume that $(a;b)=1$ as otherwise we can divide everything through by the gcd, noting that \[\text{gcd}(dx,dy)+\text{lcm}(dx,dy)=d \cdot \left(\text{gcd}(x,y)+\text{lcm}(x,y)\right).\]Now we can begin by writing $c=ab+1$ on the blackboard. Note that $c \equiv 1 \pmod{a}$ and $(b;c)=1$. Next we can write $bc+1 \equiv b+1 \pmod{a}$ which is still coprime to $c$. Then we can write $c(bc+1)+1 \equiv b+2 \pmod{a}$ which is still coprime to $c$. Iterating, we get numbers coprime to $c$ that are $b+1,b+2,b+3,\dots \pmod{a}$ and hence eventually get a multiple of $a$, say $ka$. Now we can write $a(k+1)$, then $a(k+2)$ etc. and hence clearly eventually reach a multiple of any given number $n$.
14.08.2024 11:13
初始时,我们在黑板上写下两个正整数$a,b$.在每一步中,老边选取在黑板上的两个不同的正整数$x,y$然后写下$gcd(x, y) + lcm(x, y)$。设$n$是一个正整数。证明:无论$a,b$的值是什么,老边可以在有限步中写下一个$n$的倍数。 It is just a translation for chinese student.