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 "results for GCD... can be checked by division".
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.$