\documentclass[11pt]{article}
\usepackage[x11names, svgnames, rgb]{xcolor}
%\usepackage{tikz}
%\usetikzlibrary{arrows,shapes}

\usepackage{scrextend}

\input{intro}

\lhead{\color{gray} Шарафатдинов Камиль 192}
\rhead{\color{gray} дм-16 (\texttt{cw16\_plus})}
\title{Дискретная математика 16}
\author{Шарафатдинов Камиль БПМИ192}
\date{билд: \today}

% -- Here bet  dragons --
\begin{document}

\maketitle

\twocolumn

\dmquestion{1}

    $\varphi(n) < n$, поэтому в $n!$ точно есть множитель $\varphi(n)$.

    Пусть $n! = \varphi(n) \cdot Q$

    Тогда по теореме Эйлера (так как $(n, 2) = 1$)
    \[
        2^{n!} = 2^{\varphi(n) \cdot Q} = \br{ 2^{\varphi(n)} }^Q = 1^Q = 1 \pmod{n}
    \]

    Поэтому $2^{n!} - 1 \divby n$

\dmquestion{2}

    Посмотрим, какие остатки может иметь $a^{10}$ при делении на $11$:
    Либо $a$ делится на $11$, тогда $a^{10} = a = 0 \pmod{11}$. Либо $a$ не делится на $11$ и тогда, так как $11$ - простое число, $a^{10} = 1 \pmod{11}$ по МТФ. Аналогично для других букв. Тогда сумма
    \[
        a^{10} + b^{10} + c^{10} + d^{10} + e^{10} + f^{10}
    \]
    по модулю $11$ может принимать любое значение от $0$ до $6$. Но по условию она равна $0$, поэтому и каждое слагаемое равно $0$ по модулю $11$.
    Тогда каждая переменная делится на $11$ и $abcdef$ делится на $11^6$ \qed

\dmquestion{3}
    \[
        7^2 = 49 = 1 \pmod{16}
    \]
    Поэтому $7^{7^7} = 7 \pmod{16}$, так как $7^7$ - нечетное число.
    Тогда по теореме Эйлера
    \[
        7^{7^{7^7}} = 7^7 \pmod{17}
    \]
    \[
        7^7 = 49^3 \cdot 7 = (-2)^3 \cdot 7 = -8 \cdot 7 = 12 \pmod{17}
    \]

\dmquestion{4}
    \begin{align*}
        x^2 = 1 \pmod{200}\\
        x^2 - 1 = 0 \pmod{200}\\
        (x + 1)(x - 1) = 0 \pmod{200}
    \end{align*}

    Если $x$ - нечетный, то такое произведение всегда делится на $8$,
    а если четный, то не делится даже на $2$.

    Если одна из скобок делится на $5$, то другая точно не делится.

    Поэтому нам нужно решить такую систему:
    \[
        \begin{cases}
            x = 1 \pmod{2}\\
            \begin{sqcases}
                x + 1 = 0 \pmod{25}\\
                x - 1 = 0 \pmod{25}
            \end{sqcases}
        \end{cases}
    \]
    Решениями являются вычеты $\{49, 51, 99, 101, 149, 151, 199, 1\}$

\dmquestion{5}
    Число заканчивается на $0001$ тогда и только тогда, когда оно сравнимо с $1$ по модулю $10^4$.
    По теореме Эйлера
    \[
        3^{\varphi(10000)} = 1 \pmod{10000}
    \]

\dmquestion{6}
    \begin{align*}
        x^2 = x \pmod{10^k}\\
        x(x - 1) = 0 \pmod{10^k}
    \end{align*}

    Если $x$ делится на $2^n$, то $x - 1$ на $2$ не делится.
    Поэтому, на $2^k$ делится либо $x$, либо $x - 1$. Аналогично с $5$.
    Тогда есть 4 случая:
    \begin{enumerate}
        \item $x \divby 10^k \Rightarrow x = 0 \pmod{10^k}$
        \item $x - 1 \divby 10^k \Rightarrow x = 1 \pmod{10^k}$
        \item $x \divby 2^k, \quad x - 1 \divby 5^k$
        \item $x \divby 5^k, \quad x - 1 \divby 2^k$
    \end{enumerate}

    В каждом из 3 и 4 пунктов есть ровно одно решение по модулю $10^k$ по китайской теореме об остатках. Решения не совпадают, потому что иначе $x$ и $x - 1$ должны бы были одновременно делиться на $2^k$. По тем же соображениям они не пересекаются и с пунктами 1 и 2.
    \qed

\end{document}