Математическое и загадочное

[E.K.]

Отлично! Тогда всего три задачки осталось. Раз:

 

Существует ли такое натуральное n, что 3^n заканчивается на 0001? Если да - то какое из них минимальное?

[ska79]

не существует такого натурального числа n, при котором 3^n заканчивается на 0001.

Рассмотрим последние цифры степеней числа 3: 3^1 = 3 3^2 = 9 3^3 = 27 3^4 = 81 3^5 = 243 3^6 = 729 3^7 = 2187

Мы видим, что последние цифры степеней числа 3 циклично повторяются: 3, 9, 7, 1, 3, 9, 7, 1, и так далее.

Таким образом, последняя цифра любой степени числа 3 будет одной из цифр 3, 9, 7 или 1, но никогда не будет равна 0. Следовательно, нет натурального числа n, при котором 3^n заканчивается на 0001.

[E.K.]

57 minutes ago, ska79 said:

Таким образом, последняя цифра любой степени числа 3 будет одной из цифр 3, 9, 7 или 1, но никогда не будет равна 0.

Так требуется найти число, которое оканчивается не на 0, а на 0001.

[Xandr_5890]

Здравствуйте!

Существует - по теореме Эйлера-Ферма 3^4000=1(mod 10000), 4000 - функция Эйлера от 10000.

Минимальным является n=500, поскольку порядок мультипликативной группы кольца Z/10000 равен 500, и тройка не является квадратичным вычетом по модулю 10000.

 

Как считаем порядок группы:

Z*/10000 изоморфна прямой сумме Z*/625 и Z*/16, порядок прямой суммы равен НОК порядков слагаемых.

Порядок Z*/625 равен 625-125=500, порядок Z*/16 равен 4.

НОК(500,4)=500.

 

Причем здесь вычеты:

Если бы тройка была квадратичным вычетом, то существовало бы некоторое a, для которого а^2=3(mod 10000), из чего бы следовало а^500=1=3^250(mod 10000).

[E.K.]

Попроще без Эйлера ведь тоже можно?...

[Xandr_5890]

Можно, отчего же нельзя)

Заметим, что 3^4 - 1 делится на 10.

Обозначим t=3^4.

Перед нами стоит задача найти минимальную степень k, при которой t^k - 1 делится на 10000. А так как                            S=(t^k - 1)/(t - 1) = t^(k-1) +t^(k-2)+...+t+1, то задача сводится к нахождению минимального k, при котором S делится на 125 ("восьмерка" у нас уже есть в множителе t - 1, и новую "двойку" в S мы не получим - S нечетно).

В силу того, что каждое слагаемое в S взаимно просто с 5 и заканчивается на 1, искомое условие реализуется в том случае, когда количество слагаемых в S равно 125.

Таким образом, t^125 - 1 делится на 10000. Что равносильно тому, что 3^500 - 1 делится на 10000.

Изменено 24 декабря, 2023 пользователем Xandr_5890

[E.K.]

1. Почему 500 - минимальное?

2. А можно еще проще, без многочленов? А то народ уже к Новому году готовится...

[Xandr_5890]

2. Существование такого числа можно доказать совсем просто: рассмотрим последовательность остатков от деления степеней тройки на 10000. В силу принципа Дирихле в ней найдутся два одинаковых члена: 3^a < 3^b.

Тогда 3^b - 3^a = 3^a * (3^b-a - 1) делится на 10000. А так как 3 и 10000 взаимно просты, то 3^b-a - 1 делится на 10000.

 

1. Мои рассуждения выше по поводу минимальности не полные.

Как доказать то, что t^125 - 1 является минимальным решением, не прибегая к группам, я не знаю...

Можно "в лоб" проверить, что t^5 - 1 и t^25 - 1 не подходят, других кандитов нет.

[Fireman]

32 минуты назад, Xandr_5890 сказал:

1. Мои рассуждения выше по поводу минимальности не полные.

А если попробовать так:

 

очевидно, что надо рассматривать вариант (3⁴)ⁿ поскольку только он заканчивается на 1

 

итак рассмотрим задачу нахождения такого n, чтобы (3⁴)ⁿ = 81ⁿ заканчивалось на 0001.

81ⁿ = (80 + 1)ⁿ

 

имеем Бином Ньютона и как результат

81ⁿ = (1 + 80)ⁿ=sum(C(n, k)80^n-k)

 

существует ли такое 81ⁿ которое заканчивается на 0001:

 

да, достаточно посмотреть второй член бинома - n * 80, чтобы он был кратен 10000

 

n * 80 = 10000

n = 125

 

легко увидеть, что все остальные члены бинома кроме 1 при n = 125 также будут кратны 10000 - 

 

рассмотрим каждый член бинома - 80^k * 125! / k! / (125 - k)!

 

при k > 3 уже только 80^k кратно 10000, а значит и сам k-ый член кратен 10000

125! / 2! / 123! кратно 25
125! / 3! / 122! кратно 5
что легко видно поскольку ни 2! ни 3! не имеют в качестве множителей 5-ки и у нас всегда остается множитель 125

 

 

[E.K.]

У меня без Дирихле и Ньютона просто Калькулятором получилось...

[Xandr_5890]

22 минуты назад, Fireman сказал:

да, достаточно посмотреть второй член бинома - n * 80, чтобы он был кратен 10000

 

n * 80 = 10000

n = 125

 

Вот это здОрово!

Только вот как доказать, что 125 - минимальное значение?

24 минуты назад, Fireman сказал:

125! / 2! / 123! кратно 25
125! / 3! / 122! кратно 5

Наверное, здесь должно быть "кратно 125"

[Xandr_5890]

8 минут назад, E.K. сказал:

У меня без Дирихле и Ньютона просто Калькулятором получилось...

Как-то неспортивно

[E.K.]

41 minutes ago, Xandr_5890 said:

Как-то неспортивно

Наоборот!

 

А то вы тут комаров фигарите телескопами... Задачки простые же, а тут "Ферма", "Дирихле"...

[Xandr_5890]

11 минут назад, E.K. сказал:

Наоборот!

 

А то вы тут комаров фигарите телескопами... Задачки простые же, а тут "Ферма", "Дирихле"...

Так такие "комары" могут легко мутировать в нечто более страшное

 

было б в условие не "0001", а "0000001" - и все!

[Fireman]

1 час назад, Xandr_5890 сказал:

Наверное, здесь должно быть "кратно 125"

там же 80^2 и 80^3 степени за коэффициентами C стоят, поэтому как раз кратности 25 и 5 достаточно