How to test if a polynomial GCD is correct I'm studying the Zippel algorithm for computing multivariate polynomial GCDs, which is probabilistic in the sense that it uses some random numbers, and assumes that if a polynomial coefficient is zero, then it is actually zero (as opposed to only zero at the randomly chosen values).
In [Zi79], the author makes the following claim:

Since the results for GCD and factorization can be checked by
division, one is guaranteed to obtain the correct answer, if need be,
by performing the calculation twice.

I can certainly see how we can check if a polynomial is a common divisor, but how can we be sure it is a greatest common division?
I just don't understand how &quot;results for GCD... can be checked by division&quot;.
Can anybody help me?
[Zi79] Richard Zippel, PROBABILISTIC ALGORITHMS FOR SPARSE POLYNOMIALS, Laboratory for Computer Science, Massachusetts Institute of Technology
If $d$ divides both $a$ and $b$, then $d=\gcd(a.b)$ iff $\gcd ({a\over d}, {b\over d})=1.$
If $d$ divides both $a$ and $b$, then $d=\gcd(a.b)$ iff $\gcd ({a\over d}, {b\over d})=1.$