<s>[INST] $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$.
 [/INST] Suppose a prime $p$ divides both $ab+1$ and $a+b$. Then, writing $b\equiv -a \pmod p$, and plugging this in $ab+1$, we get $p| 1-a^2$, which (since $p$ is prime) implies $a\equiv 1$ or $-1$ modulo $p$.
i) $a\equiv 1 \pmod p$: Then, $b\equiv -1 \pmod p$, which implies $a^2+b\equiv 0 \pmod p$, so $a^2+b=p$, but since they're positive integers, $b$ is at least $p-1$, so $a$ can be at most $1$, which contradicts to the given assumption.
ii) $a\equiv -1 \pmod p$: Now, $b\equiv 1 \pmod p$. Similarly $a+b^2=p$ in this case, and again similarly since $a$ is at least $p-1$, $b$ can be at most $1$, which gives a contradiction.
So, there is no such a prime $p$, and $\gcd(ab+1,a+b)=1$.
</s>