Доказательство:

Пусть 2^k - 1 делится на 3^n для некоторого натурального k. Тогда 2^k = 1 (mod 3^n).

Теперь рассмотрим 2^(k+1) - 1. По определению первообразного корня, это число не должно делиться на 3^n. Рассмотрим разложение 2^(k+1) - 1 по формуле (a-b)(a+b):

2^(k+1) - 1 = (2^k - 1)(2^k + 1) = (1)(2^k + 1) = 2^k + 1 (mod 3^n).

Так как 2^k = 1 (mod 3^n), то 2^k + 1 = 2(mod 3^n). Значит, 2^(k+1) - 1 не делится на 3^n.

Таким образом, мы показали, что при любом натуральном n число 2 является первообразным корнем по модулю 3^n.