$a^2+b$ and $a+b^2$ prime implies $\gcd(ab+1,a+b)=1$ Let $a,b>1$ be integers such that $a^2+b$ and $a+b^2$ are prime. Prove that $\gcd(ab+1,a+b)=1$.
Clearly $a$ and $b$ are of different parities; suppose $a$ is odd and $b$ even. If a prime $p\neq 2$ divides $ab+1$ and $a+b$, then it also divides $(ab+1)+(a+b)=(a+1)(b+1)$ and $(ab+1)-(a+b)=(a-1)(b-1)$. So either $p$ divides both $a+1,b-1$ or $p$ divides both $a-1,b+1$.

Continuing where you left off, suppose without loss of generality that $p$ divides $a+1$ and $b-1$. Then
$$
a+b^2 \equiv -1 + 1^2 \equiv 0 \pmod{p}
$$
Since $a+b^2$ is prime, it follows that $p=a+b^2$. But by assumption $p$ divides $a+b$, and $b > 1$...
