Megoldás. Azt állítjuk, hogy pontosan akkor léteznek a kívánt $a_i$ és $b_j$ számok, ha $n$ és $k$ relatív prímek. Ehhez elsőként igazoljuk, hogy az állítás elégséges. Tegyük fel tehát, hogy $\left(n\mathrm{,}k\right)=1$. Legyen $1\le i\le n$ és $1\le j\le k$ esetén $a_i=ik+1$, illetve $b_j=jn+1$. Az $a_i{b}_j=ijnk+ik+jn+1$ szám $n$-nel osztva $ik+1$, $k$-val osztva pedig $jn+1$ maradékot ad. Az $n$ és $k$ relatív prím volta miatt $1\le i\le n$ esetén az $ik+1$ számok páronként különböző maradékot adnak $n$-nel osztva, $1\le j\le k$ esetén pedig a $jn+1$ számok páronként különböző maradékot adnak $k$-val osztva. Ha ugyanis mondjuk $ik+1$ és $i\text{'}k+1$ ugyanazt a maradékot adják $n$-nel osztva, akkor $n\mid ik+1-\left(i\text{'}k+1\right)=\left(i-i\text{'}\right)k$, ahonnan $n\mid \left(i-i\text{'}\right)$ következik, hiszen $n$-nek és $k$-nak nincs közös prímosztója. Ez utóbbi oszthatóság és $1\le i\mathrm{,}i\text{'}\le n$ miatt $i=i\text{'}$.
Azt kaptuk tehát, hogy bárhogyan is veszünk két különböző $a_i{b}_j$ szorzatot, azok $n$-nel vagy $k$-val osztva különböző maradékot adnak. Nem lehetséges tehát, hogy két különböző szorzat $nk$-val osztva azonos maradékot adjon, nekünk pedig éppen erre van szükségünk.
A szükségesség bizonyításához azt tesszük fel, hogy az $a_i$ és $b_j$ számok rendelkeznek a feladatban leírt tulajdonsággal. Ez azt is jelenti, hogy valamelyik, mondjuk $a_1{b}_1$ szorzat $nk$-val osztva $0$ maradékot ad, azaz $nk\mid a_1{b}_1$. Legyen $a=\left(a_1\mathrm{,}nk\right)$ és $b=\left(b_1\mathrm{,}nk\right)$. Világos, hogy $nk\mid ab$, ezért $nk\le ab$.
Figyeljük meg, hogy a $k$ db $a_1{b}_j$ szorzat mindegyike osztható $a$-val. Márpedig az $nk$ szerinti osztási maradékok között pontosan $\frac{nk}{a}$ olyan van, amely $a$-val osztható. Ez azt jelenti, hogy $k\le \frac{nk}{a}$, azaz $a\le n$. Hasonló gondolatmenet igazolja a $b\le k$ becslést. Ezek szerint $ab\le nk$, amit a korábbi $nk\le ab$ megfigyeléssel összevetve azt kapjuk, hogy $ab=nk$. Ez utóbbi pedig csak úgy lehetséges, ha $a=n$ és $b=k$.
Jelölje $d$ az $n$ és $k$ legnagyobb közös osztóját. Ekkor $n$ és $k$ legkisebb közös többszöröse $M=\frac{nk}{d}$. Számoljuk meg, hány olyan osztási maradék van $nk$ szerint, amely $n$-nel vagy $k$-val osztható. Világos, hogy $k$ maradék osztható $n$-nel és $n$ maradék $k$-val, ám azokat a maradékokat, amelyek $n$-nel és $k$-val is oszthatók, kétszer számoltuk meg. Ezek éppen az $M$-mel osztható maradékok, számuk tehát $\frac{nk}{M}=d$. Ezért pontosan $n+k-d$ olyan $nk$ szerinti maradék van, amely $n$-nel vagy $k$-val osztható. Azonban $n\mid a_1$ és $k\mid b_1$ miatt az $a_1{b}_j$, illetve $a_i{b}_1$ szorzatok oszthatók $n$-nel, illetve $k$-val. Az ilyen szorzatok száma pedig $n+k-1$, ezért $n+k-1\le n+k-d$, azaz $1\ge d=\left(n\mathrm{,}k\right)$. Ezek szerint $n$ és $k$ valóban relatív prímek, ezzel pedig a feltétel szükségességét is igazoltuk.  $\square$