Processing math: 100%

Friday, January 21, 2022

2022/009) Find the gcd(19! + 19, 20! + 19)

 We have GCD(19! + 19, 20!+19) 

= GCD( 19!+ 19 , 20(19! + 19) - (20!+ 19)) using gcd(a,b) = gcd(a, na -b))

= GCD(19! + 19, 20! + 20 * 19 - 20! -19)

= GCD(19! + 19, 20 * 19 - 19)

= GCD(!9! + 19, 361)

Now 361 = 19^2

19! + 19 is 19(18! + 1)

As 19 is a prime as per wilson's theorem 18! + 1 is divisible by 19

So 19! + 19 is divisible by 19^2 = 361

so GCD = 361 

No comments: