В бытность мою репетитором я практиковал такую помощь своим ученикам, которым не удавалось запомнить определенные математические факты — свойства, формулы, теоремы, хотя стремление разобраться в математике было. Помощь заключалась в подборе и решении (желательно несложном) ярких задач на эти математические факты. Впоследствии срабатывали ассоциации. По-видимому, практический материал в виде задачи легче запоминается в отличие от сухой, иногда слишком абстрактной теории.
Предлагаю задачу на одну нечасто встречающуюся на олимпиадах теорему Эйлера из теории чисел, которая гласит:
\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 \)).
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 .
\)
Предлагаю задачу на одну нечасто встречающуюся на олимпиадах теорему Эйлера из теории чисел, которая гласит:
Если \( a \) и \( m \) взаимно простые числа, то \[
a^{ \varphi (m) } \equiv 1 \pmod m ,
\] где \( \varphi (m) \) — функция Эйлера, равная количеству натуральных чисел, меньших \( m \) и взаимно простых с ним, включая \( 1 . \)
Например, пусть для некоторого натурального \( k \) имеет место условие \(a^{ \varphi (m) } \equiv 1 \pmod m ,
\] где \( \varphi (m) \) — функция Эйлера, равная количеству натуральных чисел, меньших \( m \) и взаимно простых с ним, включая \( 1 . \)
\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}
\) представлено в виде \(
\overline { a_n \ldots a_1 a_0 } .
\) Определите цифру \( a_k \) такую, что \(
a_k \not= 0 ,
\) \(
a_{k-1} = \ldots = a_1 = a_0 = 0 .
\)
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 .
\)
