Question

Докажите утверждение:

Answer 1

Напомню, что φ(p) - количество чисел, меньших p и взаимно простых с p. В решении l заменено на n, так как нет верхнего индекса от l.

Имеется следующее:

(2a + 1)k = 2ⁿ - 1

Пусть существует такое n, что:

2ⁿ - 1 ≡ 0 (mod 2a + 1)

Тогда подберём такое k, чтобы равенство удовлетворяло условию. Значит, осталось лишь найти такое n, что:

2ⁿ ≡ 1 (mod 2a + 1)

2a + 1 - нечётное число, следовательно, не делится на 2. Тогда воспользуемся теоремой Эйлера и найдём φ(2a + 1). Требование (взаимная простота чисел) выполняется, следовательно:

2^φ(2a + 1) Ξ 1 (mod 2a + 1)

Тогда n = φ(2a + 1).

k = (2ⁿ - 1) : (2a + 1).