Prove $\gcd(nn!, n!+1)=1$

For any $n \in \mathbb{N}$, find $\gcd(n!+1,(n+1)!+1)$. First come up with a conjecture, then prove it.

By testing some values, it seems like $\gcd(n!+1,(n+1)!+1) = 1$

I can simplify what's given to me to $\gcd(nn!, n!+1)=1$ but I can't find out how to get it into the form I want it. Can anybody look at what I'm doing and give me any guidance?

$\gcd(n!+1,(n+1)!+1) = 1 \implies \gcd(n!+1,(n+1)n!+1) = 1 \implies \gcd(n!+1,nn!+n!+1) = 1 \implies \gcd(nn!, n!+1) = 1$

You don’t need to use induction; you just need to prove the statement in the title. Suppose that $p$ is a prime factor of $nn!$; can $p$ divide $n!+1$?

Here is a proof that does not use induction but rather the key property of gcd: $(a,b) = (a-b,b) = (a-kb,b)$ for all $k$.

Take $a=nn!$, $b=n!+1$, $k=n$ and conclude that $(nn!, n!+1)=(nn!-n(n!+1),n!+1)=(-n,n!+1)=1$ since any divisor of $n$ is a divisor of $n!$.

Note that $$ (n-1)!\cdot \underline{n n!} - (n!-1)\underline{(n!+1)} = 1; $$ this Bézout's identity shows that the two underlined quantities must be relatively prime (anything that divides them both must divide the right-hand side). The related identity $$ (n-1)! \underline{((n+1)!+1)} - (n!+(n-1)!-1)\underline{(n!+1)} = 1 $$ similarly proves that the greatest common divisor of these two underlined terms equals 1.

Of course, discovering these identities in the first place is best done by using the Euclidean algorithm, as in lhf's answer.

Hint $\ $ Put $\rm\,k = n!\ $ in: $\rm\,\ \color{#c00}{n\mid k}\,\Rightarrow\,(1+k,nk)= 1\ $ by $\rm\, (1\!-\!k)\:(1\!+\!k) + (\color{#c00}{k/n})\: nk = 1.\ \ $ QED

Generally, $ $ the above Bezout equation implies coprimality of $\rm\, 1+k\,\ $ and $\rm\,\ nk\,$ in every ring.

Alternatively, with $\rm\,m = 1+k,\,$ we can employ Euclid's Lemma $\rm(EL)$ as follows:

$$\rm\,n\mid k,\,(m,k) =1\,\Rightarrow (m,n) = 1\,\Rightarrow\,(m,nk)=1\ \ by\ \ EL$$ i.e. $\rm\, mod\ m\!:\ x\,$ is a unit (invertible) iff $\rm\,(x,m) = 1.$ Units are closed under products and divisors, i.e. they form a saturated monoid, so since $\rm\,k\,$ is a unit so is its divisor $\rm\,n\,$ and the product $\rm\,nk.$