Important Problems on Greatest Common Divisor

This section on Greatest Common Divisor features a collection of important problems designed to enhance your understanding of the topic through practice. Each problem is carefully selected to cover a variety of methods, including the Euclidean algorithm and prime factorization. Clear, step-by-step solutions are provided to help students grasp the concepts and apply them confidently in exams and real-world problem-solving. Ideal for high school, college students, and competitive exam aspirants, these Greatest Common Divisor problems build a strong foundation in Number Theory.

Show that for any natural number \( n \), the greatest common divisor of \( (n+1)! + 1 \) and \( n! + 1 \) is 1.

Answer:

Let us define:

a = (n+1)! + 1, \quad b = n! + 1

To prove

\gcd(a, b) = 1

Let \( d = \gcd(a, b) \). Then \( d \mid a \) and \( d \mid b \), which implies:

d \mid -a + (n+1)b

Therefore, we compute:

\begin{align*} -a + (n+1)b &= -(n+1)! - 1 + (n+1)(n! + 1) \\ &= -(n+1)! - 1 + (n+1)n! + n+1 \\ &= n \end{align*}

So \( d \mid n \) implies \( d \mid n! \).

Also, since \( d \mid b = n! + 1 \) and \( d \mid n! \), we have:

d \mid (n! + 1 - n!) = 1

Hence, \( d = 1 \), and so:

\gcd((n+1)! + 1,\ n! + 1) = 1