«Антье и мантисса. Сборник задач с решениями»

В блоге публикуются рецензии на книгу, обсуждения критических замечаний, ответы на часто задаваемые вопросы, комментарии к задачам из сборника, а также материалы, не вошедшие в книгу, формулировки и решения новых задач.
http://keldysh.ru/e-biblio/entier — электронная версия книги в формате PDF (редакция от 20.11.2017).

23 сентября 2015 г.

\( 1024!^{1024} \)

В бытность мою репетитором я практиковал такую помощь своим ученикам, которым не удавалось запомнить определенные математические факты — свойства, формулы, теоремы, хотя стремление разобраться в математике было. Помощь заключалась в подборе и решении (желательно несложном) ярких задач на эти математические факты. Впоследствии срабатывали ассоциации. По-видимому, практический материал в виде задачи легче запоминается в отличие от сухой, иногда слишком абстрактной теории.
Предлагаю задачу на одну нечасто встречающуюся на олимпиадах теорему Эйлера из теории чисел, которая гласит:
Если \( a \) и \( m \) взаимно простые числа, то \[
a^{ \varphi (m) } \equiv 1 \pmod m ,
\] где \( \varphi (m) \) — функция Эйлера, равная количеству натуральных чисел, меньших \( m \) и взаимно простых с ним, включая \( 1 . \)
Например, пусть для некоторого натурального \( k \) имеет место условие \(
\mbox {НОД} \, (k, \, 10 ) = 1
\), тогда \[
k^{ \varphi (10) } =
k^4 \equiv 1 \pmod {10} ,
\] поскольку только числа \( 1, \, 3, \, 7, \, 9 \) меньше \( 10 \) и взаимно простые с ним.
Конечно, догадаться, что \(
k^4 \equiv 1 \pmod {10}
\) для всех \( k , \) взаимно простых с \( 10 , \) можно, используя арифметику остатков по модулю \( 10 \). Отметим, частным случаем теоремы Эйлера является малая теорема Ферма (при простом \( m \)).

45. Пусть число \(
1024!^{1024}
\) представлено в виде \(
\overline { a_n \ldots a_1 a_0 } .
\) Определите цифру \( a_k \) такую, что \(
a_k \not= 0 ,
\) \(
a_{k-1} = \ldots = a_1 = a_0 = 0 .
\)
Решение. Согласно основной теореме арифметики каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причем единственным способом с точностью до порядка следования сомножителей. Понятно, что в разложении числа \( 1024! \) на простые множители степень \( 2 \mbox {-ки} \) больше степени \( 5 \mbox {-ки} .\) Тогда \[
1024!^{1024} = \left( 2^n \cdot 10^m \cdot K \right)^{1024} ,
\tag {45.1}
\] где \( n, \, m \in \mathbb N \) (заметим, что нет надобности в вычислении \( n \) и \( m \)) и \( K \) — произведение простых чисел, каждое из которых взаимно простое с числами \( 2 \) и \( 5 . \) Значит, числа \( K \) и \( 10 \) также взаимно простые.
Представление (45.1) сводит задачу к определению младшего разряда числа \(
\left( 2^n \cdot K \right)^{1024} .
\) Поскольку \[
\left( 2^n \right)^{1024} =
\left( 2^4 \right)^{256n} \equiv 6 \pmod {10} ,
\] \[
\left( K \right)^{1024} =
\left( K^4 \right)^{256} \equiv 1 \pmod {10} ,
\] то \(
\left( 2^n \cdot K \right)^{1024} \equiv 6 \pmod {10} .
\)

Ответ: \( 6 . \)

Примечание. Вполне уместен вопрос: «А где в этой задаче антье или мантисса?»
Во-первых, в решении можно пойти по необязательному усложненному пути, если использовать формулу Лежандра (см. одноименный раздел 6. в «А. и м.»).
Во-вторых, задание можно слегка расширить «нахождением значения \( k \)». Вот здесь-то и пригодится формула Лежандра. Кстати, \(
k = 253 \cdot 1024 .
\)


Автор: И.Л. на 11:38
Отправить по электронной почте Написать об этом в блоге Опубликовать в Twitter Опубликовать в Facebook Поделиться в Pinterest
Следующее Предыдущее Главная страница

Автор

Автор
СЕМЕНОВ
Игорь Ленидович,
науч.сотр-к (1983-2018)
ИПМ им. М. В. Келдыша РАН

Разделы

  • Обозначения
  • Определения
  • Свойства
  • Cообщения

Просмотров за неделю

Архив

  • янв. 2017 ( 1 )
  • нояб. 2016 ( 9 )
  • окт. 2016 ( 11 )
  • сент. 2016 ( 7 )
  • авг. 2016 ( 8 )
  • июл. 2016 ( 5 )
  • июн. 2016 ( 5 )
  • мая 2016 ( 10 )
  • апр. 2016 ( 12 )
  • мар. 2016 ( 5 )
  • янв. 2016 ( 1 )
  • дек. 2015 ( 11 )
  • нояб. 2015 ( 11 )
  • окт. 2015 ( 17 )
  • сент. 2015 ( 13 )
  • авг. 2015 ( 12 )
  • июл. 2015 ( 14 )
  • июн. 2015 ( 2 )
Технологии Blogger.