How to show that $\gcd(n! + 1, (n + 1)! + 1) \mid n$?

Allow $n$ be a favorable integer, $n!$ represents the factorial of $n$. Allow $d = \gcd(n! + 1, (n + 1)! + 1)$. Show that $d$ separates $n$. ( Hint: notification that $(n+1)(n!+1) = (n+1)!+n+1$)

0
2019-05-18 22:46:14
Source Share
Answers: 2

HINT: Use the definition of GCD and also the reality that $$(n+1)!+1 = n! \times (n+1) +1 = n! \cdot n + (n!+1)$$ We recognize that $d \mid (n!+1)$ given that $d$ is the GCD

0
2019-05-21 08:32:09
Source

The offered tip reveals that $\rm\ n\ $ is an indispensable straight mix of $\rm\ n!+1\ $ and also $\rm\ (n+1)! + 1\:,\: $ so $\rm\ n\ $ is divisible by all usual divisors, consisting of the GCD. Actually we can go better and also show that the GCD = 1. Particularly, given that the GCD separates the coprime numbers $\rm\:n\:$ and also $\rm\ n!+1\ $ it have to be 1. Below is an alternative derivation making use of specific gcd regulations, in addition to a specific Bezout straight depiction of the GCD.

Placing $\rm\ k = n!+1\ $ listed below programs that the GCD amounts to $\rm\ gcd(n!+1,n) = 1$.

$\rm\quad\quad\ \ gcd(k,(n+1)k-n)\ =\ gcd(k,n)\ \ $ using $\rm\ \ n = (n+1)k - ((n+1)k-n)$

$\quad\quad$ remembering $\rm\quad\quad\ \ gcd(k,m)\ =\ gcd(k,\:jk\pm m)\ $

$\quad\quad$ given that if $\rm\ \ d|k\ $ after that $\rm\ \: d|m\ \ \iff\ \: d\ |\ jk\pm m\quad\ \ $ Above $\rm \ j = n+1 $

In reality we can take a break the above to get a specific Bezout straight depiction of the GCD:

$\quad\quad\quad\quad\quad \rm n\ =\ n!\ ((n+1)!+1) + (n-(n+1)!)\ (n!+1) $

Dividing the above via by $\rm\:n\:$ reveals that the gcd is 1! $\ $ But, alas, I fear I've said loudly way too much ...

0
2019-05-21 08:12:13
Source