Bebizonyítjuk, hogy ha a sorozat mindegyik elemének legfeljebb $n$ osztója van, akkor létezik a kívánt részsorozat.
Teljes indukciót alkalmazunk. Ha $n=1$, akkor mindegyik elem $1$, és a teljes sorozat megfelelő.
Tegyük fel, hogy állításunk igaz $n=k$ esetén, és tekintsünk egy olyan pozitív egészekből álló $a_1$, $a_2$, $\text{...}$ sorozatot, amelyben mindegyik elemnek legfeljebb $k+1$ osztója van.
Két esetet fogunk vizsgálni:
1. eset: Létezik olyan $p$ prímszám, amely végtelen sok elemnek osztója. Legyenek ezek az elemek $a_{i_1}$, $a_{i_2}$, $\text{...}$ és tekintsük az $\frac{a_{i_1}}{p}$, $\frac{a_{i_2}}{p}$, $\text{...}$ sorozatot. Ebben mindegyik elemnek legfeljebb $k$ osztója van, ezért az indukciós feltevés szerint kiválasztható belőle egy olyan $\frac{a_{j_1}}{p}$, $\frac{a_{j_2}}{p}$, $\text{...}$ részsorozat, amelyben bármelyik két elem legnagyobb közös osztója ugyanaz a $d$ szám. Ekkor viszont az $a_{j_1}$, $a_{j_2}$, $\text{...}$ sorozatban bármely két elem legnagyobb közös osztója $pd$. Létezik tehát a feltételeknek megfelelő részsorozat.
2. eset: Bármelyik prímszám a sorozat elemei közül csak véges soknak osztója. Ebben az esetben rekurzívan definiálunk egy olyan részsorozatot, amelyben bármely két elem relatív prím. Legyen $i_1=1$. Ha már definiáltuk $i_1$, $i_2$, $\text{...}$, $i_m$-et, akkor legyen $i_{m+1}$ az első olyan pozitív egész, amely nagyobb $i_m$-nél, és amelyre $a_{i_{m+1}}$ relatív prím az $a_{i_1}$, $\text{...}$, $a_{i_m}$ elemek mindegyikéhez. Ilyen elem létezik, mert az $a_{i_1}$, $\text{...}$, $a_{i_m}$ elemeknek külön-külön és együttesen is csak véges sok prímosztója van, és ez a véges sok prímosztó a sorozat elemei közül összesen csak véges soknak osztója.