Proving coprimes

Question

I understand that it is necessary to prove that the GCD = 1, and so the Euclidean Algorithm can be applied in some way, but I'm having trouble actually applying it. Any help would be appreciated. Thank you very much!

Answer 1

The previous part of the question had us proving for all integers n, if d is an integer such that d|n+1 and d|n2+8 then d|9

THen you are done!

Let $d = \gcd(n+1, n^2 +8)$. Then by the previous part of the question $d|9$ so $d = 1, 3, 9$. But if $9|n$ then $3|n$ and $3\not \mid n+1, 9\not \mid n+1, 3\not \mid n^2 + 8$ and $9\not \mid n^2+ 8$.

So $d$ divides both $n+1$ and $n^2 + 8$ the $d$ can not be equal to either $3$ or $9$.

That only leave $d = 1$.

So $\gcd(n+1, n^2 +8) =1$.

That's all there is to it.