Найти наибольший общий делитель многочленов

Теорема Безу + основная теорема алгебры - > многочлен 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)