Euclidean algorithm for dividing two products.

Question

Say I have numbers, $a$ and $b$ represented as two products

$$a = \prod_{i=0}^{N_a} a_i \hspace{1cm} b = \prod_{i=0}^{N_b}b_i$$

I do know $\{a_k\}$ and $\{b_k\}$ but can not store $a$ or $b$ in a practical way to do euclidean algorithm directly on the numbers. How can I do this efficiently, only knowing the factors and not being allowed to perform / represent multiplications resulting in numbers larger than these factors?

Answer 1

I assume you want to find the greatest common divisor. The following pseudocode algorithm works, and you can decide whether it meets your requirements:

• Initialize $g$ to be the empty product
• For $i$ from $0$ to $N_a$ do
  • For $j$ from $0$ to $N_b$ do
    • Set $temp = \gcd(a_i,b_j)$
    • Set $g = g \times temp$ (append a term onto the product representation for $g$; can be ignored if $temp=1$)
    • Set $a_i = a_i/temp$ and $b_j=b_j/temp$
  • end For
• end For
• Output $g$.