E.K. Опубликовано 24 декабря, 2023 Автор Поделиться Опубликовано 24 декабря, 2023 Отлично! Тогда всего три задачки осталось. Раз: Существует ли такое натуральное n, что 3^n заканчивается на 0001? Если да - то какое из них минимальное? Ссылка на комментарий Поделиться на другие сайты Поделиться
ska79 Опубликовано 24 декабря, 2023 Поделиться Опубликовано 24 декабря, 2023 не существует такого натурального числа 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. Опубликовано 24 декабря, 2023 Автор Поделиться Опубликовано 24 декабря, 2023 57 minutes ago, ska79 said: Таким образом, последняя цифра любой степени числа 3 будет одной из цифр 3, 9, 7 или 1, но никогда не будет равна 0. Так требуется найти число, которое оканчивается не на 0, а на 0001. Ссылка на комментарий Поделиться на другие сайты Поделиться
Xandr_5890 Опубликовано 24 декабря, 2023 Поделиться Опубликовано 24 декабря, 2023 Здравствуйте! Существует - по теореме Эйлера-Ферма 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. Опубликовано 24 декабря, 2023 Автор Поделиться Опубликовано 24 декабря, 2023 Попроще без Эйлера ведь тоже можно?... Ссылка на комментарий Поделиться на другие сайты Поделиться
Xandr_5890 Опубликовано 24 декабря, 2023 Поделиться Опубликовано 24 декабря, 2023 (изменено) Можно, отчего же нельзя) Заметим, что 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. Опубликовано 24 декабря, 2023 Автор Поделиться Опубликовано 24 декабря, 2023 1. Почему 500 - минимальное? 2. А можно еще проще, без многочленов? А то народ уже к Новому году готовится... Ссылка на комментарий Поделиться на другие сайты Поделиться
Xandr_5890 Опубликовано 24 декабря, 2023 Поделиться Опубликовано 24 декабря, 2023 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 Опубликовано 24 декабря, 2023 Поделиться Опубликовано 24 декабря, 2023 32 минуты назад, Xandr_5890 сказал: 1. Мои рассуждения выше по поводу минимальности не полные. А если попробовать так: очевидно, что надо рассматривать вариант (34)n поскольку только он заканчивается на 1 итак рассмотрим задачу нахождения такого n, чтобы (34)n = 81n заканчивалось на 0001. 81n = (80 + 1)n имеем Бином Ньютона и как результат 81n = (1 + 80)n=sum(C(n, k)80n-k) существует ли такое 81n которое заканчивается на 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. Опубликовано 24 декабря, 2023 Автор Поделиться Опубликовано 24 декабря, 2023 У меня без Дирихле и Ньютона просто Калькулятором получилось... Ссылка на комментарий Поделиться на другие сайты Поделиться
Xandr_5890 Опубликовано 24 декабря, 2023 Поделиться Опубликовано 24 декабря, 2023 22 минуты назад, Fireman сказал: да, достаточно посмотреть второй член бинома - n * 80, чтобы он был кратен 10000 n * 80 = 10000 n = 125 Вот это здОрово! Только вот как доказать, что 125 - минимальное значение? 24 минуты назад, Fireman сказал: 125! / 2! / 123! кратно 25 125! / 3! / 122! кратно 5 Наверное, здесь должно быть "кратно 125" Ссылка на комментарий Поделиться на другие сайты Поделиться
Xandr_5890 Опубликовано 24 декабря, 2023 Поделиться Опубликовано 24 декабря, 2023 8 минут назад, E.K. сказал: У меня без Дирихле и Ньютона просто Калькулятором получилось... Как-то неспортивно Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 24 декабря, 2023 Автор Поделиться Опубликовано 24 декабря, 2023 41 minutes ago, Xandr_5890 said: Как-то неспортивно Наоборот! А то вы тут комаров фигарите телескопами... Задачки простые же, а тут "Ферма", "Дирихле"... Ссылка на комментарий Поделиться на другие сайты Поделиться
Xandr_5890 Опубликовано 24 декабря, 2023 Поделиться Опубликовано 24 декабря, 2023 11 минут назад, E.K. сказал: Наоборот! А то вы тут комаров фигарите телескопами... Задачки простые же, а тут "Ферма", "Дирихле"... Так такие "комары" могут легко мутировать в нечто более страшное было б в условие не "0001", а "0000001" - и все! Ссылка на комментарий Поделиться на другие сайты Поделиться
Fireman Опубликовано 24 декабря, 2023 Поделиться Опубликовано 24 декабря, 2023 1 час назад, Xandr_5890 сказал: Наверное, здесь должно быть "кратно 125" там же 80^2 и 80^3 степени за коэффициентами C стоят, поэтому как раз кратности 25 и 5 достаточно 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
Рекомендуемые сообщения
Пожалуйста, войдите, чтобы комментировать
Вы сможете оставить комментарий после входа в
Войти