Теорема Безу + основная теорема алгебры -> многочлен n-ой степени представим в виде a(x-c1)*...*(x-cn), где c1..cn- его корни.
Наибольший общий делитель f и g тоже представим в таком виде, причем его корни являются одновременно корнями f и g
Корни f - корни p-ой степени из 1: cos(2Пk/p) + i*sin(2Пk/p), k = 0..p-1
Корни g - корни q-ой степени из 1: cos(2Пn/q) + i*sin(2Пn/q), n = 0..q-1
Корни НОД - cos(2Пy) + i*sin(2Пy), где y представимо в виде k/p = n/q, т.е. np = qk, n - 0..q-1, k = 0..p-1 - таких ровно d = НОД(p,q)
Пусть p = ad, q = bd, тогда ka/p = k/d = kb/q, k = 0..d-1
Т.е. корни НОД f и g - это корни d-ой степени из 1, и результат имеет вид x^d - 1
Действительно,
x^p - 1 = x^(ad) - 1 = (x^d - 1)(1 + x^d + ... + x^(d(a-1)) )
x^q - 1 = x^(bd) - 1 = (x^d - 1)(1 + x^d + ... + x^(d(b-1)) )
НОД f и g = x^d - 1, где d = НОД(p,q)