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

[Mary84]

Добрый день!

Нужно найти НОД чисел $ \frac {a^n-1}{a-1}$ и $ a-1 $

Посоветуйте, пожалуйста, как решать задачу.

[Sonic86]

Новая переменная - это бывает так удобно...

А даже проще и без переменной. Просто сделайте 3 очевидных шага. Тут просто больше нечего делать. Что здесь Вы можете сделать?

[iifat]

Может, попробовать начать с частных случаев $n=1,2,3$?

[Mary84]

Частные случаи пробовала рассматривать.

До $ n=3 $ рассмотрела.

У числа $a^n-1 $ всегда был один множитель $ (a-1) $.

$a^n-1$ можно разложить по биному ньютона $a^n-b^n$ и первой скобкой там получается $(a-1)$.

Такой ход рассуждения подходит?

[ИСН]

Подходит, только так дольше и это не бином Ньютона.

[Mary84]

Не знаю, как раскладывать начиная с n=5 : (

[ИСН]

Можно обозначить число $a-1$ какой-нибудь одной буквой и использовать настоящий бином Ньютона.

[nnosipov]

А в каком виде предполагается дать ответ? Ведь этот НОД зависит от $a$ и в случае произвольного $n$ эта зависимость не такая уж и простая.

[patzer2097]

наверно, выражение типа $\operatorname{gcd}(a-1,n)$ будет засчитываться в качестве правильного ответа

[nnosipov]

Да, пожалуй.

[Mary84]

Преподаватель переформулировал задачу.

Нужно доказать что НОД$(\frac{a^n-1}{a-1}, a-1) = $ НОД $(n, a-1)$

По прежнему не понимаю, как именно решать. Использовать замену переменной? Но как быть с $ a^n-1 $ , если заменим a-1 на переменную.

Пожалуйста, объясните немного подробнее, как действовать.

[Deggial]

Mary84 в сообщении #820007 писал(а):

a^n-1, если заменим a-1

Формулы оформляйте, иначе тему снесу в Карантин.

Mary84 в сообщении #820007 писал(а):

По прежнему не понимаю, как именно решать.

Вам дали несколько советов и рекомендаций. Выполните их и покажите результат.

[iifat]

Mary84 в сообщении #819975 писал(а):

До $ n=3 $ рассмотрела

Ну дык где? И что за проблемы с $n=5$?

[Mary84]

Рассмотрим при n=1,2...

При $n=1$

$\frac{a^1-1}{a-1}=\frac{a-1}{a-1}=1$

При $n=2$

$\frac{a^2-1}{a-1}=\frac{(a-1)(a+1)}{a-1}=a+1$

При $n=3$

$\frac{a^3-1}{a-1}=\frac{(a-1)(a^2+a+1)}{a-1}=a^2+a+1$

При $n=4$

$\frac{a^4-1}{a-1}=\frac{(a-1)(a+1)(a^2+1)}{a-1}=(a+1)(a^2+1)$

При $n=5$

$\frac{a^5-1}{a-1}=\frac{(a-1)(a^4+a^3+a^2+a+1)}{a-1}=(a^4+a^3+a^2+a+1)$

При $n=6$

$\frac{a^6-1}{a-1}=\frac{(a-1)(a^5+a^4+a^3+a^2+a+1)}{a-1}=(a^5+a^4+a^3+a^2+a+1)$

...

$ \frac{a^n-1}{a-1}=a^{n-1}+a^{n-2}+...+a+1 $

[Deggial]

Mary84 в сообщении #820076 писал(а):

$ \frac{a^n-1}{a-1}=a^{n-1}+a^{n-2}+...+a+1 $

Это правильный шаг. Чему равен остаток от деления $a^k$ на $a-1$? Если затрудняетесь, сделайте замену $b=a-1$. Можете, опять же, найти ответ для малых $k$, а потом выдвинуть гипотезу.