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 a1=a,a2=b and ak=gcd(a1,ak−1)+lcm(a1,ak−1) for i≥3 Obviously Andrea can write on the blackboard at some point every number of the sequence (an)n∈N Note that gcd(a1,ai+1)=gcd(a1,gcd(a1,ai)+lcm(a1,ai))=gcd(a1,ai) for every i≥1 and thus if we set gcd(a,b)=c then ak+1=c+lcm(a1,ak)=c+a1akc for k≥1. It's clear that c|ai∀i∈N so let ai=cbi where (bn)n∈N is a sequence of positive integers. Clearly gcd(b1,b2)=1 Then bk+1=1+b1bk . 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.