hint

$b^{619}|a^{1000}+1$, $a^{619}|b^{1000}+1$ $\implies a^{619}b^{619}|(a^{1000}+1)(b^{1000}+1)$ $\implies a^{619}b^{619}|a^{1000}+b^{1000}+1$ $a^{1000}+b^{1000}+1\ge a^{619}b^{619}$ $\implies (a^{619}-b^{381})(b^{619}-a^{381})\le a^{381}b^{381}+1$ We have two cases: (i) If $a^{619}-b^{381}$ and $b^{619}-a^{381}$ are both positive: Then we have $a^{619}-b^{381}\le b^{381}$ or $b^{619}-a^{381}\le a^{381}$. WLOG assume the former. Then $a^{619}\le 2b^{381}$. Since $b^{619}|a^{1000}+1$, then $a^{1000}+1\ge b^{619}$. Equality cannot hold by Mihailescu's theorem, so $a^{1000}\ge b^{619}$. Combining $a^{619}\le2b^{381}$ and $a^{1000}\ge b^{619}$, we get $2b^{381}\ge b^{619^2/1000}$, so $2\ge b^{2.161}$, and hence $b=1$. So $a^{619}|b^{1000}+1=2$, which gives $a=1$. Hence we get $(a,b)=(1,1)$ which clearly satisfies the required conditions. (ii) If $a^{619}-b^{381}$ or $b^{619}-a^{381}$ is non-positive: WLOG assume $a\ge b$. Then $b^{691}-a^{381}\le0$, which gives $a\ge b^{691/381}$. As in case (i), we deduce that $b\ge a^{619/1000}$. Therefore $a\ge a^{(691/381)\cdot(619/1000)}=a^{383161/381000}\ge a$. Equality must hold, so $a=1$. We get the same solution $(a,b)=(1,1)$.