На доску записали числа $1$, $2$, ..., $100$. Далее за ход стирают любые два числа $a$ и $b$, где $a\geqslant b>0$, и пишут вместо них одно число $[a/b]$. После $99$ ходов на доске останется одно число. Каким наибольшим оно может быть? (Напомним, что $[x]$ — это наибольшее целое число, не превосходящее $x$.)

   Решение

Докажите, что число x является элементом приведённой системы вычетов тогда и только тогда, когда числа a₁, ..., a_n, определённые сравнениями
x ≡ a₁ (mod m₁),  ..., x ≡ a_n (mod m_n)  принадлежат приведённым системам вычетов по модулям m₁, ..., m_n соответственно. Выведите отсюда мультипликативность функции Эйлера.

   Решение

Страница: << 1 2 3 4 5 >> [Всего задач: 24]      

Докажите равенства:
  а)  φ(m) φ(n) = φ((m, n)) φ([m, n]);
  б)  φ(mn) φ((m, n)) = φ(m) φ(n) (m, n).
Определение функции φ(n) см. в задаче 60758.

Прислать комментарий

Решение

Докажите, что число x является элементом приведённой системы вычетов тогда и только тогда, когда числа a₁, ..., a_n, определённые сравнениями
x ≡ a₁ (mod m₁),  ..., x ≡ a_n (mod m_n)  принадлежат приведённым системам вычетов по модулям m₁, ..., m_n соответственно. Выведите отсюда мультипликативность функции Эйлера.

Прислать комментарий

Решение

Пусть    Докажите равенство   φ(n) = n(1 – ¹/_p1)...(1 – ¹/_ps).
  а) пользуясь мультипликативностью функции Эйлера;
  б) пользуясь формулой включения-исключения.
Определение функции Эйлера φ(n) см. в задаче 60758.

Прислать комментарий

Решение

Докажите тождество Гаусса  φ(d ) = n. Определение функции φ(n) см. в задаче 60758.

Прислать комментарий

Решение

Некоторые из чисел 1, 2, 3, ..., $n$ покрашены в красный цвет так, что выполняется условие: если для красных чисел $a, b, c$ (не обязательно различных)  $a(b - c)$  делится на $n$, то  $b = c$.
Докажите, что красных чисел не больше чем φ($n$).

Прислать комментарий

Решение

Страница: << 1 2 3 4 5 >> [Всего задач: 24]