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:
Post a Comment