Question

Можно ли найти такую натуральную степень числа 3, которая оканчивается на …0001?

Answer 1

вообще то это можно доказать для любого конечного число нулей, 01 001 0001 итд

то есть нам надо найти что существует число n∈N , при котором существует некая степень k, при которой 3^k - 1 делится на 10^n (в данном случае на 10000)

Смотрим на три в степени 3^1 3^2 3^3 ...таких чисел бесконечно много

Рассмотрим набор из 10000 степеней тройки и рассмотрим остатки от деления на 10000(в общем случае на 10^n)

Нацело ни одно из чисел на 10000 не делится но по принципу Дирихле существуют как минимум 2 числа имеющие одинаковые остатки

обозначим эти числа m > n, тогда

раз они имеют одинаковые остатки при делении на 10000 то разность их делится на 10000

3^m - 3^n = 3^n*(3^(m-n) - 1)

3^n не делится нацело на 10000

значит нацело целится 3^(m-n) - 1

и значит число 3^(m-n) оканчивается на 0001

Да такое число 10000 = 10^4 (в общем случае также доказывается)  

Answer 2

Для того чтобы найти натуральную степень числа 3, которая оканчивается на ...0001, нужно решить уравнение:

3^n ≡ 1 (mod 10000)

Заметим, что 10000 = 2^4 * 5^4, поэтому решения уравнения будут связаны с решениями двух уравнений:

3^n ≡ 1 (mod 16) 3^n ≡ 1 (mod 625)

Первое уравнение имеет решение n = 4k, где k - любое натуральное число.

Второе уравнение имеет более сложные решения, но можно заметить, что 3^4 ≡ 81 ≡ -1 (mod 625). Значит, если n имеет вид n = 4k + r, где r = 0, 1, 2 или 3, то

3^n ≡ (3^4)^k * 3^r ≡ (-1)^k * 3^r (mod 625)

Из уравнения 3^n ≡ 1 (mod 10000) следует, что 3^n ≡ 1 (mod 16) и 3^n ≡ 1 (mod 625), поэтому нужно рассмотреть все возможные значения r и найти такие k и r, что (-1)^k * 3^r ≡ 1 (mod 625).

Если r = 0, то 3^r ≡ 1 (mod 625), поэтому нужно решить уравнение (-1)^k ≡ 1 (mod 625). Это уравнение имеет решение k = 0, поэтому n = 4k = 0.

Если r = 1, то 3^r ≡ 3 (mod 625), поэтому нужно решить уравнение (-1)^k * 3 ≡ 1 (mod 625). Это уравнение не имеет целочисленных решений.

Если r = 2, то 3^r ≡ 9 (mod 625), поэтому нужно решить уравнение (-1)^k * 9 ≡ 1 (mod 625). Это уравнение имеет решение k = 2, поэтому n = 4k + 2 = 10.

Если r = 3, то 3^r ≡ 27 (mod 625), поэтому нужно решить уравнение (-1)^k * 27 ≡ 1 (mod 625). Это уравнение не имеет целочисленных решений.

Таким образом, существует единственное натуральное число n, которое удовлетворяет условию: 3^n оканчивается на ...0001. Это число равно 10.