ГЛАВНАЯ » РЕШЕБНИК

2014-03-08   
Найдите все такие натуральные числа #n#, что: число #2^{n} - 9# делится на 7;


Решение:


Число #2^{n}-9# делится на 7 тогда и только тогда, когда имеет место сравнение #2^{n} \equiv 9 (\mod 7),# которое равносильно сравнению #2^{n} \equiv 2 (\mod 7).# По малой теореме Ферма имеем сравнение #2^{6} \equiv 1 (\mod 7).# Поэтому, если число #n# представить в виде #n = 6q + r,# где #0 \leq r \leq 6,# то выполняется сравнение #2^{n} = (2^{6})^{q} \cdot 2^{r} \equiv 2^{r} (\mod 7),# откуда следует, что сравнение #2^{n} \equiv 2 (\mod 7)# справедливо тогда и только тогда, когда справедливо сравнение #2^{r} \equiv 2 (\mod 7).# Непосредственная проверка показывает, что среди чисел, удовлетворяющих двойному неравенству #0 \leq r \leq 6,# последнему сравнению удовлетворяют лишь 1 и 4. Таким образом, исходное сравнение имеет место тогда и только тогда, когда число #n# имеет вид #n = 6q + 1# или #n = 6q + 4.# Так как в первом случае #n = 3 \cdot (2q) + 1#, а во втором #n = 3 \cdot (2q + 1) + 1,# окончательно имеем #n = 3k + 1.#