Question

Правда ли, что число (2**(n-1) - 1) делится на n, когда n - простое число?

Две звездочки обозначают степень. Например, 2**3 это два в кубе.

2**(3-1) - 1 = 3 - делится на 3

2**(5-1) - 1 = 15 - делится на 5

2**(7-1) - 1 = 63 - делится на 7

2**(11-1) - 1 = 1023 - делится на 11

2**(13-1) - 1 = 4095 - делится на 13

и так далее.

Случайно это или всегда так?

Answer 1

Верна Малая теорема Ферма:

Если n — простое число и a — целое число, не делящееся на n, то aⁿ⁻¹ − 1 делится на n.

Чаще пишут так: aⁿ⁻¹ ≡ 1 (mod n).

Малая теорема Ферма — частный случай теоремы Эйлера:

Если a и n взаимно просты, то aʷ⁽ⁿ⁾ ≡ 1 (mod n), где w(n) — функция Эйлера.