Наибольший общий делитель

[Руст]

Чему равен наибольший общий делитель чисел:
$x^n+y^n,x^m+y^m$?
Числа х и у целые, m и n натуральные.

[vbn]

откуда задачка, интересно?
кажется довольно сложной

[maxal]

Если x и y взаимно просты, а m и n имеют одинаковую степень 2-ки в своем разложении (частный случай: m и n - нечетные), то ответом будет x^{gcd(m,n)} + y^{gcd(m,n)}.

[Руст]

Задача легко сводится к случаю, когда x и y взаимно просты. Пусть d наибольший общий делитель этих чисел и n>m, то выносится множитель: $(x^n+y^n,x^m+y^m)=d^m(d^{n-m}(x_1^n+y_1^n),x_1^m+y_1^m),x_1=x/d,y_1=y/d,(x_1,y_1)$.
Задача доводится до полного анализа.

[Руст]

Раз нет интереса к задаче надо её закрывать.
Я рассмотрю только случай, когда х и у взаимно просты ( в противном случае можеть появиться дополнительная степень двойки). Деля одно число на другое (n=mk+r>m) с остатком получаем:

$$x^n+y^n=(x^m+y^m)(x^{n-m}-x^{n-2m}y^m+...(-1)^kx^ry^{km})+[(-1)^{k+1}x^r+y^r]y^{km}.$$

Поэтому продолжая этот процесс вычисления остатков при делении приводит к выражению:

$$(x^n+y^n,x^m+y^m)=(x^{kd} \pm y^{kd},x^d \pm y^d), d=(n,m).$$

При этом в случае указанном maxalom оба знака будут положительны, а в противном случае один из знаков положительный, другой отрицательный. В последнем случае НОД получается равным 1, если числа х и у разной чётности и равно 2 в случае одинаковой чётности (т.е. оба нечётны). Несколько проще случай (без этих знаков) при вычислении $(x^n-y^n,x^m-y^m).$
Такие вычисления пригодны и в случае, когда х и у алгебраические целые числа и используеются при доказательстве теоремы Ферма для регулярных простых и удобно в доказательстве следующего свойства чисел Фибоначчи: $(F_n,F_m)=F_{(n,m)}.$

[zoo]

вспомнился один баян, может студенты младших курсов его еще не видели:
НОД$(x^n-1,x^m-1)$-?

[Профессор Снэйп]

И сразу хочется прям взять и написать решение...

Нет уж! Пусть, действительно, студенты младших курсов подумают

[ET]

$x^{NOD(n,m)} -1$

[maxal]

Ну тогда уж до кучи вычислите:

$$\mathop{\text{НОД}}(x^n-1,x^m+1)$$

и

$$\mathop{\text{НОД}}(x^n+1,x^m+1)$$