Blastzit wrote: Given a list of integers $2^1+1, 2^2+1, \ldots, 2^{2019}+1$, Adam chooses two different integers from the list and computes their greatest common divisor. Find the sum of all possible values of this greatest common divisor.

Click to reveal hidden text

zhangruichong wrote: Blastzit wrote: Given a list of integers $2^1+1, 2^2+1, \ldots, 2^{2019}+1$, Adam chooses two different integers from the list and computes their greatest common divisor. Find the sum of all possible values of this greatest common divisor.

Click to reveal hidden text

Mr zhang,1 can also be one of the gcds,so the answer should be $2^{674}+672$

Sorry for the bump but how did u get that answer?

Williamgolly wrote: Sorry for the bump but how did u get that answer? To prove $\{2^1+1,2^2+1, \ldots, 2^{673}+1\}$ is the sufficient condition for the solution is rather straight forward, just use the fact that $(x+1) | (x^3 + 1)$. To show they are the necessary condition is quite tricky. I am thinking about infinite descent or maybe irreducible cyclotomic polynomial.

This thread hasn't got a full solution yet, so here it is: First notice that $2^a \mid 2^{3a}+1$, thus clearly our $\text{gcd}$ set includes $1,2^1+1,2^2+1,...,2^{673}+1$, but how can we go about proving that this is the only such set? The answer- induction. Inductive claim: For the list of $2^1+1,2^2+1,...,2^{n}+1$, the exhaustive list of $\text{gcd}s$ is $(1,2^1+1,...,2^{[\frac n3]}+1)$, where $[x]$ is the greatest integer function of $x$. Base case- obvious. Inductive proof: Say the claim works for the integer $n-1$. Now consider $\text{gcd}(2^a+1,2^n+1)$. Case 1: $n>2a$ $\text{gcd}(2^a+1,2^n+1)=(2^a+1,2^n-2^a)=(2^a+1,2^{n-a}-1)=(2^a+1,2^{n-a}+2^a)=(2^a+1,2^{n-2a}+1)$. This collapses into the inductive hypothesis unless equality holds (which inductive case doesn't cover for), and that occurs only if $n=3a$, thus if $n \equiv 0 \pmod{3}$, then $2^{\frac n3}$ is added to our list of $\text{gcd}s$, otherwise the list remains invariant. Case 2: $n<2a$ $\text{gcd}(2^a+1,2^n+1)=(2^a+1,2^n-2^a)=(2^a+1,2^{n-a}-1)=(2^a+1,2^{n-a}+2^a)=(2^a+1,2^{2a-n}+1)$. This again collapses into the inductive hypothesis, but here equality can never holds as that would imply $2a-n=a=>a=n=>$ Contradiction to distinctness of chosen integers. Induction over. Hence our required sum is $1+(2+1)+(2^2+1)+...+(2^{673}+1)=673+2^{674}-1=2^{674}+672$

What's the time table of HKTST?The first three questions are too easy in four and a half hours(Oh,the other three are easy,too).

HKTST are really easy, I think the first three questions can be finished in an hour.

In HKTST 1, there are 6 fairly easy problems for 3 hours. We are gonna get the 2020-2021 HKTST 1 today!

Here is a relatively short solution. I claim the answer is \[ \{1\}\cup \Bigl\{2^k+1:1\le k\le 673\Bigr\}. \]Let $a_i:=2^i+1$. Note that if $i,j$ are both powers of two, $a_i$ and $a_j$ are coprime: hence one is achievable. Next, let $d$ be such that $d={\rm gcd}(a_i,a_j)$ for some $i,j$. Observe that $2^{2i}\equiv 2^{2j}\equiv 1\pmod{d}$. From here, we deduce $2^{2(i,j)}\equiv 1\pmod{d}$, that is $2^{(i,j)}\equiv \pm 1\pmod{d}$. Now, in the former case, we find that $a_i= 2^i+1\equiv 2\pmod{d}$. Since $d$ is odd, this forces $d=1$. In the latter, $2^{(i,j)}\equiv -1\pmod{d}$, thus $d\mid 2^{(i,j)}+1$. Now, we again deduce $d=1$ if $i/(i,j)$ or $j/(i,j)$ is even. Finally, if both $i/(i,j)$ and $j/(i,j)$ are odd, we find both numbers to be divisible by $2^{(i,j)}+1$. Since $d\le 2^{(i,j)}+1$, we conclude that $(a_i,a_j) = 2^{(i,j)}+1$ if $i/(i,j)$ and $j/(i,j)$ are both odd. Now, $2019\ge \max\{i,j\}\ge 3(i,j)$, forcing $(i,j)\le 673$. Finally, for each $k$, $1\le k\le 673$; taking $i=k$ and $j=3k$, we find $(a_i,a_j)=2^k+1$. This concludes the proof.