I'm trying to reconstruct an example I saw somewhere some years back. It goes something like this: $\gcd(n^5-5,(n+1)^5-5)=1$ is true for $n=1,2,\dots,1435389$ but fails for $n=1435390$ (when the gcd is 1968751).