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

[Mary84]

Я решила пойти от малых k, получилось следующее:

$n=1 $ остаток равен единице

при $ n=2$

$ a+1 = (a-1)\cdot 1+2$

при $ n=3$

$ a^2+a+1 = (a-1)(a+2)+3$

при $ n=4$

$ a^3+a^2+a+1 = (a-1)(a^2+2a+3)+4$

$при n=5$

$ a^4+a^3+a^2+a+1 = (a-1)(a^3+2a^2+3a+4)+5$

Видна закономерность: делитель $q_{i}$ с каждым шагом увеличивается на множитель $a+1$, a остаток $r_{i}$ возрастает на 1 с каждым шагом и совпадает с номером шага.

Запишем формулы: $q_{i}=(a+1)^{i}$, $ r_{i}=i$

[provincialka]

Сложно! Все-таки, сделайте замену $a-1=b$ и рассмотрите каждую степень отдельно.

[patzer2097]

теперь, когда задача формулируется как "доказать, что $\operatorname{gcd}\left(\frac{a^n-1}{a-1}, a-1\right)=\operatorname{gcd}\left(n, a-1\right)$", достаточно (как еще один вариант решения) проверить, что $\frac{a^n-1}{a-1}-n=a^{n-1}+\ldots+a-(n-1)$ делится на $a-1$.

[ИСН]

кстати да

[iifat]

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

Рассмотрим при

Ну дык рассматривать так рассматривать. Чему равен НОД $a+1$ и $a-1$? $a^2a+1$ и $a-1$?

[Mary84]

Насколько я понимаю, НОД$(a+1),(a-1)$ $ = $ НОД $(2, a-1)$

Мы выяснили, что остаток увеличивается на 1 и равен номеру шага. Следовательно:

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

Значит НОД$(\frac{a^n-1}{a-1}, a-1) = $НОД $(n, a-1)$

[ИСН]

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

Мы выяснили, что остаток увеличивается на 1

Что-то не помню, как мы это обосновали.

[Mary84]

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

Я решила пойти от малых k, получилось следующее:

$n=1 $ остаток равен единице

при $ n=2$

$ a+1 = (a-1)\cdot 1+2$

при $ n=3$

$ a^2+a+1 = (a-1)(a+2)+3$

при $ n=4$

$ a^3+a^2+a+1 = (a-1)(a^2+2a+3)+4$

$при n=5$

$ a^4+a^3+a^2+a+1 = (a-1)(a^3+2a^2+3a+4)+5$

Видна закономерность: делитель $q_{i}$ с каждым шагом увеличивается на множитель $a+1$, a остаток $r_{i}$ возрастает на 1 с каждым шагом и совпадает с номером шага.

Запишем формулы: $q_{i}=(a+1)^{i}$, $ r_{i}=i$

Вот здесь увидели закономерность. Но этого мало, наверное. Надо доказать её, по ММИ.

[Sonic86]

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

Вот здесь увидели закономерность. Но этого мало, наверное. Надо доказать её, по ММИ.

Ой, ужас-то какой!
$a=(a-1)+1$
$a^k=(a-1)A+B, B=?$

Ну или: Вы знаете, что $a-1$ делит $a^k-1$. Тогда

$$(a^0-1)+(a^1-1)+(a^2-1)+(a^3-1)+...$$

.

Хотя, по идее, тут тоже надо все обосновывать через ММИ...