# How to find GCD and LCM of a factorial and a large number?

So I was given this question:

$$n = 2^{16}3^{19}17^{12}$$

Find $$\gcd(n, 40!)$$ and $$\operatorname{lcm}(n, 40!)$$.

I understand how to find the GCD and LCM when its two really large numbers (given their prime factorization), But I'm not sure how Id do something like this. Given we're not allowed to use calculators, I assume there is a way to find this.

EDIT

So I did

(floor of each by the way)

v2(40!) = 40/2 + 40/4 + 40/8 + 40/16 + 40/32 = 38

v3(40!) = 40/3 + 40/9 + 40/27 = 18

v17(40!) = 40/17 = 2

So what do I do from here?

• – 1ENİGMA1 Sep 25 '18 at 13:16

Hint: Find the highest power of $$2$$ that divides $$40!$$. Do the same for $$3$$ and $$17$$.

Solution:

$$n = 2^{16}\cdot 3^{19}\cdot 17^{12}$$

$$40! = 2^{38} \cdot 3^{18} \cdot 17^2\cdot m$$

$$gcd(n,40!) = 2^{16} \cdot 3^{18} \cdot 17^2$$

$$lcm(n,40!) = \dfrac{n\cdot 40!}{gcd(n,40!) } = \dfrac{2^{16}\cdot 3^{19}\cdot 17^{12} \cdot 40!}{2^{16} \cdot 3^{18} \cdot 17^2} = 3\cdot 17^{10}\cdot 40!$$

• – lhf Sep 25 '18 at 12:13

I'm going to attempt to answer my own question:

So based off of what I got (the most recent edit) I have:

(floor of each by the way)

E2(40!) = 40/2 + 40/4 + 40/8 + 40/16 + 40/32 = 38, 38 >= 16 so we use 16

E3(40!) = 40/3 + 40/9 + 40/27 = 18, 18 <= 19 so we use 18

E17(40!) = 40/17 = 2, 2 <= 12 so we use 2

From my understanding, those results are the Exponents of each of the prime numbers. Therefore GCD(n, 40!) = 2^16 * 3^18 * 17^2

and since ab = gcd(a,b)*lcm(a,b) (when a and b are positive ints) that means that LCM(n, 40!)= (40!*n)/(2^16 * 3^18 * 17^2)

That look right?

• No, gcd uses the min exponent for each common prime. So it's $2^{16}$ not $2^{38}$. The others are fine. – lhf Sep 25 '18 at 12:53
• Not sure I understand what you mean by that. – DevAllanPer Sep 25 '18 at 12:54
• I would have an easier time understanding, if you edited my answer and so I could see what i did wrong to be honest. – DevAllanPer Sep 25 '18 at 12:55
• where did you get 2^16 from? – DevAllanPer Sep 25 '18 at 12:56
• @DevAllanPer: $2^{16}$ comes from your statement of the problem. It's the highest power of $2$ that divides your $n$. – Henning Makholm Sep 25 '18 at 12:57