GCD of Factorials!

(I'm only a math enthusiast in my free time, and this is the first longer proof I've ever written. Sorry if anything is unclear or different from accepted standards)

I used a combination of simple division, Euclid's GCD algorithm, and Wilson's Theorem to solve the problem.

We can first see that both $19!+19$ and $20!+19$ are divisible by 19. Therefore $GCD(20! + 19, 19! + 19) = 19*GCD(18!(20) + 1, 18! + 1)$ .

To apply Euclid's GCD algorithm to these numbers, we need to find $(18!(20) + 1) mod (18! + 1). (18! + 1)*19$ is the largest multiple of $(18! + 1)$ that doesn't exceed $18!(20) + 1$ so

$(18!(20)+1) mod (18!+1)\\ =18!(20)+1-(18!+1)(19)\\ =18(20)+1-18!(19)-19\\ =18!-18$

Therefore $GCD(18!(20) + 1, 18! + 1) = GCD(18! + 1, 18! - 18)$

One more iteration of Euclid's gives us $GCD(18! - 18, 19)$

If and only if 18! - 18 is divisible by 19, then $(18! - 18 + 19) = (18! + 1)$ must be also.

A slight rearrangement of Wilson's Theorem tells us that n! + 1 is divisible by n if n is prime. 19 is prime, therefore $GCD(18! - 18, 19) = 19$

Substituting 19 into the GCD equivalence found earlier, we can see that $19*GCD(18!(20)+1,18!+1)\\ ={ 19 }^{ 2 }\\=361$

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

$20! + 19 = 19(20.18! + 1) = 19( (19 + 1)18! + 1) = 19^{2}18! + x$

By Euclid's algorithm,

$gcd( 19! + 19 , 20! + 19) = gcd( 19! + 19 , 19^{2}18!)$

$19! + 19=19(18! + 1)$ and $19|18! + 1$ . By wilson theorem , we get $19^{2}|19! + 19$

Thus

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

See the patterns

GCD(2!+2 , 3!+2) = 2

GCD (3!+3 , 4!+3) = 9 ( 3x3)

GCD (4!+4 , 5!+4) = 4

GCD (5!+5 , 6!+ 5) = 25 (5x5)

if even number we can take the same number And if odd number we can use quadratic

So

GCD (19!+19,20!+19) = 19x19 = 361

I am considering like this:

Suppose $\gcd(19!+19,20!+19)=g$ . Then we have $19!+19\equiv 0\pmod{g}$ and hence $19!\equiv -19\pmod{g}$ .

Note that $20!=20\cdot 19!$ , so $20!\equiv -380\pmod{g}$ and then $20!+19\equiv -361\pmod{g}$ .

Since $20!+19\equiv 0\pmod{g}$ , we will have $g=361$ .

Since, $(a,b)=(a-b,b)$ and $(ka,kb)=k(a,b)$

So, $(19!+19, 20!+19) = (19!+19, 20!-19!) = 19(18!+1,19!)$

From Wilson's theorem we have

$18! \equiv -1 \pmod {19}$ $\implies 19|(18!+1)$

So, the smallest non-unity divisor of $18! + 1$ is $19$ . Therefore, $(18!+1,19!)=19$ .

So, finally we have $(19!+19, 20!+19)=19*19=\boxed {361}$ .

Solution without Wilson's theorem

Using Euclid's GCD algorithm:

It's then easy to see that $GCD(20!+19,19!+19)=GCD(19·19!,19^2)=19^2$ .

GCD(19!+19, 20!+19) = 19* GCD(18!+1, 20* 18!+1) ........(A)

GCD(18!+1, 20*18!+1) = GCD(18!+1, 19!) .....(B) (why?) since GCD(a,b) = GCD(a, b-a)

now Wilson's theorem suggests 18! = -1 (mod 19) hence 18!+1 will be 0 (mod 19) and 19! also contains 19.

so GCD(18!+1, 19!) = 19 ...........................(C)

and from A, B and C ans is 19*19=361.

To generalise, for any prime $p$ , we have that $(p!+p, (p+1)!+p)=p^2$ . Why?

$p!+p=p((p-1)!+1)$ and $(p+1)!+p=(p+1)p(p-1)!+p=p((p+1)(p-1)!+1)$ . Note that $(p+1)(p-1)!+1 \equiv 1(p-1)!+1 = (p-1)!+1$ (mod $p$ ). According to Wilson's Theorem, $p \mid (p-1)!+1$ and thus $p \mid (p+1)(p-1)!+1$ as well. This means $p^2 \mid p((p-1)!+1)$ and $p^2 \mid p((p+1)(p-1)!+1)$ .

Best Ans : Let 19! + 19 = a , 20! + 19 = 19!+ 19 + 19^2x 18! = a+ 361x18! Use GCD(a , a+b) = GCD(a ,b) whichever theorem you may call to get required GCD = GCD ( 19! + 19 , 361x18!) = 19xGCD(18!+ 1 , 19x18!) = 361xGCD{(18!+1)/19 , 18!} = 361 x 1 = 361 as GCD{(18!+1) , 18!} = 1

(Note that (18!+1)/19 is an integer by Wilson's theorem

19!+19 = nq » 20(19!)= 20nq - 380

20!+19=mq » 20(19!)=mq-19

Equating the two equations and rearranging gives: (20n-m)q=361

Which implies that maximum possible q is 361 when (20n-m) =1