BxMO 2022/4 wrote: A subset $A$ of the natural numbers $\mathbb{N} = \{0, 1, 2,\dots\}$ is called good if every integer $n>0$ has at most one prime divisor $p$ such that $n-p\in A$. (a) Show that the set $S = \{0, 1, 4, 9,\dots\}$ of perfect squares is good. (b) Find an infinite good set disjoint from $S$. (Two sets are disjoint if they have no common elements.) (a) Suppose otherwise, then there exists a positive integer $n > 0$, such that it has two distinct prime divisors $p$ and $q$ such that $n - p$ and $n - q$ are both squares. Let us write \[ n - p = a^2 \ \text{and} \ n - q = b^2 \]We then have $p \mid n - p \mid a^2 \implies p \mid a \implies a = pc, c \in \mathbb{N}$, and similarly, $b = q d, d \in \mathbb{N}$. We then have \[ p - q = b^2 - a^2 = q^2 d^2 - p^2 c^2 = (qd - pc)(qd + pc) \]which implies $qd + pc \mid |p - q| \implies |p - q| \ge qd + pc \ge p + q$, a contradiction. (b) Fix a prime $p$. We claim that $\mathcal{S} = \{ p^i \mid i \ \text{odd}, i \ge 1 \}$ works. First of all, it is clear that $\mathcal{S} \cap S = \varnothing$. It suffices to prove that $\mathcal{S}$ is good. Indeed, let us suppose otherwise, then there exists $n > 0$ and two distinct prime divisor of $n$: $q$ and $r$, such that \begin{align*} n - q &= p^{a} \ \text{and} \ n - r = p^{b} \end{align*}However, $q \mid n - q \mid p^{a} \implies q = p$ and $r \mid n - r = p^{b } \implies r = p$, which gives $r = q$, a contradiction. Notes on construction. We want to find an infinite set that doesn't contain any perfect square. The best way to do this, is to force each element from the desired set to have only odd powers for its prime decomposition -- which motivates the construction.

Another construction for part b: The set of all odd primes work.To prove it,FTSOC,assume that, for a integer $n$ and for 2 different prime divisior $p>q$ of $n$, $$n-p=p_1,\quad n-q=q_1$$for some odd primes $p_1,q_1$ Since $p$ devides $n-p$ and $q$ devides $n-q$ so $p|p_1$ and $q|q_1$.But then $p=p_1$ and $q=q_1$.Which gives $2p=n=2q$.A contradiction.

You can also get the part A by noticing that $$ n - p =a^2 \Rightarrow p|a^2 \Rightarrow p|a \Rightarrow p \le a$$Now if there is also $n=b^2 + q$, we get $$ \Rightarrow n = a^2+p < a^2+2a+1 \le b^2 < b^2 +q = n$$which is a contradiction.

En el caso de 4 4 solo tiene un divisor primo que es 2 Y 4-2=2 que no es un cuadrado perfecto, alguien me puede aclarar si el problema esta mal formulado o yo no lo estoy entendiendo bien

Part (a): Suppose $S$ is not good, so there exist two prime divisors of $n$, say $p,q$, with $p$ different from $q$, such that $n-p$, $n-q$ $\in$ $S$ which means both $n-p$ and $n-q$ are perfect squares $n-p=m^2$ for some $m$ $\in$ $\mathbb{N}$ From here, $p|m^2 => p|m => p^2|m^2$ Thus let's write $n-p=p^2k^2$ for some $k$ natural number . Similarly, we get $n-q=q^2l^2$ , for some $l$ positive integer. Thus the following is true: $p^2k^2+p=q^2l^2+q$ (1) $p^2k^2<p^2k^2+p=q^2l^2+q<q^2l^2+2ql+1=(ql+1)^2$ , hence $pk<ql+1$ and similarly we get $ql<pk+1$ Thus, $pk<ql+1<pk+2$ $=>$$ql=pk$ plugging it into $(1)$ we get $p=q$ , absurd Hence , $S$ is good Part (b) We will show that the set of primes, $\mathbb{P} = [{2,3,5,7,11,....]}$ is good. Indeed, suppose a prime divisor $p$ of $n$ such that $n-p$ $\in$ $\mathbb{P}$ Then, $n-p=q (prime) => p|q => p=q $ so $n=2q$ If $q=2$ then $2$ is the only prime divisor of $n$. Else if $q$ is an odd prime , the only prime divisor of $n$ except for $q$ , is $2$,..... but $n-2=2q-2=2(q-1)$ which is not prime , since $q-1>1$ Thus, the claim is proven.

Solved with starchan, AdhityaMV For part (b), we take $S$ to be the set of all primes. This works since $n-p$ cannot be prime if $p \mid n$ unless $n = 2p$, in which case it clearly has only one prime divisor such that $n-p \in S$. For part (a), suppose not, and that there exists some $n = pqk$ such that $pqk-p$ and $pqk-q$ are both perfect squares, say $a^2, b^2$. Then subtracting, we obtain that $p-q = (b+a)(b-a)$. But note $q \mid b$ and $p \mid a$ so $a+b \geqslant p+q > |p-q|$, contradiction since $b+a \mid p-q$ and $q \ne p$. So we're done. $\blacksquare$