Задача 60507

Темы:    [ Алгоритм Евклида ] [ НОД и НОК. Взаимная простота ] [ Тождественные преобразования ] [ Разложение на множители ]

Сложность: 4- Классы: 8,9,10

Условие

Докажите, что при  m ≠ n  выполняются равенства:
  а)  (a^m – 1, aⁿ – 1) = a^{(m, n)} – 1  (a > 1);
  б)  (f_n, f_m) = 1,  где  f_k = 2^2k + 1  – числа Ферма.

Решение

  а) Первый способ. Пусть  m ≥ n.  Тогда  (a^m – 1, aⁿ – 1) = (a^m – aⁿ, aⁿ – 1) = (a^m–n – 1, aⁿ – 1).  Поэтому алгоритм Евклида для чисел  a^m – 1  и  aⁿ – 1  "идёт параллельно" алгоритму Евклида для показателей m и n. Последний заканчивается на числе  (m, n),  значит, первый – на числе  a^{(m, n)} – 1.

  Второй способ. Пусть  (m, n) = d,  (a^m – 1, aⁿ – 1) = D.  Очевидно, числа  a^m – 1  и  aⁿ – 1  делятся на  a^d – 1,  поэтому и D делится на  a^d – 1.
  С другой стороны,  d = mu + nv  (где u, v – какие-то целые числа, см. задачу 60488 б или задачу 60489). Можно считать, что  u ≥ 0,  v ≥ 0.  Тогда
a^d – 1 = a^mu+nv – 1 = a^d(1 – a^–nv) + (a^mu – 1). Первое слагаемое делится на  aⁿ – 1,  второе – на  a^m – 1,  поэтому оба делятся на D. Следовательно, и
a^d – 1  делится на D, то есть  a^d – 1 = D.

  б) Пусть  m > n.  Тогда  f_n – 2 = 2²ⁿ – 1 = (2^2n–1 – 1)f_n–1 = (2^2n–2 – 1)f_n–2f_n–1 = ... = (2^2m – 1)f_m...f_n–1.  Следовательно,  (f_n, f_m) = (2, f_m) = 1.

Замечания

Задача а) фактически равносильна задаче 60491. Действительно, при решении задачи 60491 основание системы счисления не имело никакого значения. В частности, можно считать, что вычисления проводились в системе счисления с основанием a.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	2
Название	Алгоритм Евклида
Тема	Алгоритм Евклида
задача
Номер	03.055