Let $d=gcd(a,b)$. Also let $a=dx$ and $b=dy$ ($gcd(x,y)=1$). Next, observe that the divisibilty is equivalent to $xy|d(x^3+y^3)$ and since $gcd(x,x^3+y^3)=1$ we have $xy|d$. Now look at the difference: $|a-b|=d(x-y)$ ($WLOG$ $a>b$). Obviously since $ab|d^3$ and $ab>10^{12}$ we get $d>10000$ and we're done since $x>y$.