Factorial GCD

We know that $20!=20(19!+19)-19 \cdot 20$ .

From Euclid's Algorithm, we have $\gcd(19!+19,20!+19)=\gcd(19!+19,-19 \cdot 20+19)$ , or $\gcd(19!+19,20!+19)=\gcd(19!+19,19^2)$ .

Since $19!+19=19(18!+1)$ and $19 | 18!+1$ by Wilson's Theorem, we get that $19^2 | 19!+19$ .

That means $\gcd(19!+19,19^2)=19^2$ , or $\gcd(19!+19,20!+19)=19^2=361$ , as the result.

Let $X = 18!$ , we have $19!+19 = 19X+19 = 19(X+1)$ and $20!+19 = 380X+19 = 19(20X+1)$ Now $\gcd(19(X+1),19(20X+1) = 19 \cdot \gcd(X+1,20X+1)$ and $\gcd(X+1,20X+1) = \gcd(X+1,(20X+1)-(X+1)) = \gcd(X+1,19X) = \gcd(X+1,19)$ as $\gcd(X,X+1) = 1$ .

By Wilson's Theorem (as $19$ is prime), $X = 18! \equiv -1 \mod 19$ and so $\gcd(X+1,19) = 19$ .

Hence, $\gcd(19!+19,20!+19) = 19 \cdot 19 = 361$

$gcd(19!+19,20!+19)$ $= gcd(19!+19 , 20!+19 - 20(19!+19))$ $= gcd(19!+19, 20! +19-20!-380)$ $= gcd(19!+19,-361)$ $= gcd(19!+19,361)$ $= 19gcd(18!+1,19)$ From Wilson's Theorem we know that $(19-1)! \equiv -1 \pmod{19}$ $18! + 1 \equiv 0 \pmod{19}$ It means that there exist the integer $k$ such that $18! + 1 = 19k$ So $19gcd(18!+1,19) = 19gcd(19k,19)$ $=361gcd(k,1)$ $=361$

First, we subtract the first term from the second, leaving $gcd(19!+19,20!-19!)$ . These two numbers have a common factor of 19, which we factor out to leave $19gcd(18!+1,20*18!-18!)=19gcd(18!+1,19!)$ .

Now we use Wilson's theorem, which I will prove here. The statement is: $(n-1)! \equiv -1 \pmod{n}$ if $n$ is prime.

Proof: Assume n is prime. Then every number has an inverse mod n (except for 0, which is not part of the factorial). We can pair up every element with its inverse except two: The only numbers which are their own inverses mod n are n-1, or -1, and 1. Thus we have $(n-1)! \equiv 1*1*-1 \equiv -1 \pmod{n}$ . QED

With Wilson's theorem out of the way, we can easily finish the problem: Since x and x+1 are relatively prime for any x, $18!$ is relatively prime to $18!+1$ . Thus the only possible extra common divisor is 19, and by Wilson's theorem, it does divide $18!+1$ . Thus the answer is $19*19=361$ .

We first note that both terms have a factor of 19: 19! + 19 = 19(18! + 1) 20! + 19 = 19(20 18! + 1) We now need to check if the terms 18! + 1 and 20 18! + 1 have any factors in common. Recall the fundamental idea of Euclid's algorithm: if a number divides two numbers, then it divides any linear combination of these numbers. We notice a useful linear combination: (20 18! + 1) - 20(18! + 1) = -19 We think to use this because it eliminates the 18!, which is the most troubling term. So any other common factor of these terms divides -19, which is prime, so we need only check if 19 divides both terms. Note that 20 \equiv 1 (mod 19), so 20 18! + 1 \equiv 18! + 1 (mod 19). Hence if one of these is 0 (mod 19), then both are divisible by 19. We write out the product 18! and reduce terms (mod 19): 18 * 17 * ... * 3 * 2 * 1 \equiv (-1)(-2)...(-8)(-9)(9)(8)...(2)(1) \equiv -1 Hence 18! + 1 \equiv 0 (mod 19), so 18! + 1 and 20*18! + 1 are both divisible by 19. Hence gcd(19! + 19, 20! + 19) = 19^2 = 361.

We apply the Euclidean Algorithm on the two numbers, so gcd(20!+19, 19!+19)=gcd(19!+19, 19 19!)=gcd(19(18!+1), 19^2 18!). By Wilson's Theorem, 18!+1 is divisible by 19. However, (18!+1)/19 and 18! must be relatively prime, so the gcd must be 19^2=361.

We basically need to find $gcd(19(18!+1), 19(20(18!)+1)$ . This is clearly equal to $19*gcd(18!+1, 20(18!)+1)$ . So the issue here is to find $gcd(18!+1, 20(18!)+1)=gcd(18!+1, (18!+1)+19)$ . So if $19$ does not divide $18!+1$ the $gcd$ will be $19$ . But Wilson's theorem states that if $p$ is a prime, then we have that $(p-1)! \equiv -1 \pmod p$ . So $19 | 18!+1$ . Clearly, $gcd(18!+1, (18!+1)+19)$ cannot be bigger than $19$ . So the desired $gcd$ can only be $19*19=361$ .

According to Euclid Algorithm, we can change 20! + 19 into:

20! + 19 = 19 \times (19! + 19) + (19! - 342) 19! + 19 = 1 \times (19! - 342) + 361

From this point, then we can change 19! - 342 into:

19! - 342 = 19 \times (18! - 18)

According to Wilson's Theorem, (n - 1)! \equiv -1 \pmod n if and only if n is prime. Since 18 + 1 = 19 is prime, then:

18! - 18 \equiv -1 \pmod 19 - 18 \pmod 19 18! - 18 \equiv -19 \pmod 19 18! - 18 \equiv 0 \pmod 19

Hence, 18! - 18 is divisible by 19. Then, 19 \times (18! - 18) = 19! - 342 is divisible by 19 \times 19 = 361, and so does:

• 19! - 342 + 361 = 19! + 19 is divisible by 361, and
• 19 \times (19! + 19) + (19! - 342) = 20! + 19 is divisible by 361.

Therefore, \gcd (19! + 19, 20! + 19) = 361.

19!+19 = 19(18!+1). Similarly, 20!+19 = 19( 18!*20 + 1) = 19 ( 18! + 19! + 1 ) .... ( By writing 20 = 19 + 1) Now Wilson's theorem says (p-1)! ≡ -1 mod p where p is a prime. This clearly shows that 18!+1 is a multiple of 19. Let us write 18!+1 to be of the form 19k. Now,

19!+19 = 361k.

And

20!+19 on a bit simplifying gives 361(k + 18!). If we somehow prove that there is no common factor of k + 18! and k, then we are done with the job. For the above result, 18! should not divide k. ............... eqn 1. We can write k as (18!+1)/ 19 .................. eqn 2.

By using 1 and 2, we have,

18!/k = (19!)/(18!+1) which can never be an integer. :)

Thus GCD = 361.

We use the property that gcd (k,n)=gcd(n-k,k). From this, gcd(19!+19,20!+19)=gcd(19!+19,19x19!). Subtract the second term from 19 times the first term yielding gcd(361,361x18!)=361.

19! + 19=19(18! + 1)

20! + 19=19(20 * 18! + 1)=19(19 * 18! + 18! + 1)

By Wilson's Theorem, which states that a natural number n > 1 is a prime number if and only if

(n-1)! ≡ -1 (mod n)

since 19 is a prime number, we have

18! + 1 ≡ 0 (mod 19)

we can factor another 19 out from both (19(19 * 18! + 18! + 1)) and (19(18! + 1))

we get

gcd(361(18! + (18! + 1)/19) , 361((18! + 1)/19))

It's not hard to see that (18! + (18! + 1)/19) and (18! + 1)/19 are coprime.

therefore gcd(19!+19,20!+19) = 361

Using rules of GCD, we have

$\begin{aligned} \gcd ( 19 ! + 19, 20! + 19 ) & = \gcd ( 19 ! + 19, 20! - 19! ) \\ & = \gcd ( 19 ! + 19, 19! \times 19 ) \\ & = 19 \gcd ( 18 ! + 1, 19! ) \\ & = 19 \gcd ( 18! + 1, 19) \\ \end{aligned}$

where the last step follows because no integer less than $18$ will divide $18!+1$ .

Now, by Wilson's theorem, since 19 is a prime, we know that $18! + 1 \equiv 0 \pmod{19}$ .

Hence, the answer is $19 \times 19 = 361$ .