I want to know that how can we find the GCD of two positive huge numbers $A$ and $B$. If we know $n$ numbers whose product is $A$ and similarly $m$ numbers whose product is $B$.
Example: Let $A$ be $30$ and $B$ be $15$, and we are given $3$ numbers for $A$ $2$,$5$ and $3$ (product of $2$ ,$5$ and $3$ is $30$ which is $A$) and $2$ numbers for $B$ i.e $5$ and $3$.(product of $5$ and $3$ is $15$ which is $B$).
We basically have to find $\gcd(2\times 5\times 3,5\times 3)$. Here we can multiply as $A$ and $B$ are small to get the GCD but in general $A$ and $B$ are huge.
Here is the problem statement link
An alternative method to find the GCD is to compare each prime factor, such as $(2,3,5,7 \cdots)$, and compare which exponent has the smallest index. We can then multiply the smallest prime factors together to get the result of the GCD. The two prime factorisations should include the same primes so that each prime has a pair to correspond to in the other list.
This works because for 3 numbers which have $3^p, 3^q, 3^r$ as their indices (respectively), since in a prime factorisation $p, q,r$ are integers, if $p$ is the smallest in the group then $3^{q-p}$, and $3^{r-p}$ are also integers, so they are all multiples of $3^p$. This can be generalised easily to a group of $n$ numbers.
For example, to find the GCD of $(198, 616)$, knowing that $198 = 2*3^2*11$, and $616 = 2^3*7*11$, then:
$$2^\color{blue}1*3^2*7^\color{blue}0*11^\color{blue}1$$ $$2^3*3^\color{blue}0*7^1*11^\color{blue}1$$.
Therefore the GCD of $(198, 616)$ is $2^1 * 3^0 * 7^0 * 11^1$, or $2*1*1*11$ which is $22$.
With a prime factorisation for each number, the process becomes much easier, because we can compare each exponent directly instead of using an abstract method of quotients and remainders. However, the only problem is to factorise the given factors into primes, which can be a struggle, especially when that number can be prime or have few divisors.