For every natural number $a$, consider the set $S(a)=\{a^n+a+1|n=2,3,\ldots\}$. Does there exist an infinite set $A\subset\mathbb N$ with the property that for any two distinct elements $x,y\in A$, $x$ and $y$ are coprime and $S(x)\cap S(y)=\emptyset$?
Problem
Source: Serbia MO 2006 2nd Grade P3
Tags: number theory
anthonyshinex
11.04.2021 15:28
let $A=(2,2^2,2^3,2^4,....)$ Let us suppose that $2^{ka}+2^k+1=2^{tb}+2^t+1$ then $2^{ka}+2^k=2^{tb}+2^t$, WLOG k>t let us look at this $(mod 2^k)$ $0=2^{tb}+2^t (mod 2^k)$ when $tb<k$, $2^{ka}+2^k>2^{tb}+2^t$, when $tb\ge k$, we have $2^{tb}+2^t=2^t(mod 2^k)$ and so there is a contradiction. Therefore this set A satisfies the question
hakN
11.04.2021 16:46
@above All elements of $A$ must be coprime. We claim that there exist an infinite set $A$ satisfying the conditions. Let $x\geq 3$ be any odd integer. Now we will construct a set $A$. Take $y\equiv 1 \pmod{x}$ such that $y$ is odd. Then take $z\equiv 1 \pmod{xy}$ which is odd and continue on. By the Chinese Remainder Theorem we know that such numbers exist. It is clear that all elements of $A$ are coprime. Also assume for contradiction that for some $m,n\in \mathbb{N}$ and for some $a,b\in A$ we have $a^n + a + 1 = b^m + b + 1$. Then $a(a^{n-1} + 1) = b(b^{m-1} + 1)$. Assume wlog that $a<b$. $(a,b)=1$ so we must have $a\mid b^{m-1} + 1$ but this is impossible since $a$ is odd and $b^{m-1} + 1 \equiv 2 \pmod{a}$. Contradiction. So this set $A$ satisfies the conditions and we are done.