Mivel az $1$-hez minden szám relatív prím, azért $A_1$ az üres halmaz, így $x$, $y\in A_1$-ből $x+y\in A_1$ nyilvánvalóan teljesül.
Legyen most $n>1$. Ha $n=p^k$ prímhatvány, akkor egy szám vagy relatív prím $n$-hez, vagy osztható $p$-vel. Ha tehát $x$, $y\in A_n$, akkor $x$ és $y$ osztható $p$-vel, így az összegük is, tehát $x+y\in A_n$ következik. Ezek a számok tehát megfelelőek.
Megmutatjuk, hogy ha $n$ prímosztóinak száma legalább 2, akkor vannak olyan $x$ és $y$ számok, amelyek nem relatív prímek $n$-hez, míg az összegük az.
Legyenek $n$ prímosztói $p_1$, $p_2$, $\text{...}$, $p_m$, $m\ge 2$. Legyen $x=p_1$ és $y=p_2{p}_3\text{...}{p}_m$. Ekkor $x$ és $y$ nyilván nem relatív prím $n$-hez. Az $x+y$ számnak viszont nincs 1-nél nagyobb közös osztója $n$-nel, hiszen nem osztható az $n$ egyetlen prímosztójával sem. Tehát $x$, $y\in A_n$, $x+y\notin A_n$; a megoldást pontosan a prímhatványok jelentik.