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

\usepackage{scrextend}

\input{intro}

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

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

\maketitle

\twocolumn

\dmquestion{1}
    \[
        99^{1000} = (-1)^{1000} = 1 \pmod{100}
    \]

\dmquestion{2}
    \begin{align*}
        x + 10y &=\\
        &= x + 10y - 13x - 13y\\
        &= -12x - 3y\\
        &= -3(4x + y) \pmod{13}
    \end{align*}

    Так как $(3; 13) = 1$, то $x + 10y = 0 \pmod{13}$ тогда и только тогда,
    когда $4x + y = 0 \pmod{13}$

\dmquestion{3}
    \begin{align*}
        53x &= 1 &\pmod{42}\\
        11x &= 1 + 42 \cdot 6 &\pmod{42}\\
        11x &= 253 &\pmod{42}\\
        x &= 23 &\pmod{42}
    \end{align*}

\dmquestion{4}
    \begin{align*}
        74x + 47y = 2900\\
        27x = 2900  \pmod{47}\\
        27x = 33    \pmod{47}\\
        9x = 11     \pmod{47}\\
        9x = -36    \pmod{47}\\
        x = -4 = 43 \pmod{47}\\\\
        74 \cdot 43 + 47y = 2900\\
        47y = -282\\
        y = -6
    \end{align*}

    Все решения имеют вид
    \[
        (x_0 + 47k; y_0 - 74k), \qquad k \in \mathbb{Z}
    \]

    Поэтому неотрицательных решений у этого уравнения нет

\dmquestion{5}
    \[
        \frac{n^2 - n + 1}{n^2 + 1}
    \]
    
    Предположим противное: пусть такая дробь сократима.
    
    Пусть существует $p > 1$ такое, что
    \[
        p \mid (n^2 + 1), p \mid (n^2 - n + 1)
    \]
    
    Значит,
    \[
        n = (n^2 + 1) - (n^2 - n + 1) \text{ тоже делится на $p$.}
    \]
    
    Значит, $p \mid n^2$.

    Но $n^2 + 1 = 1 \pmod{p}$. Противоречие.

\dmquestion{6}

    \textbf{Лемма}
    \[
        3^m - 1 = 3^{m - n} - 1 \pmod{3^n - 1}
    \]
    
    Доказательство:
    \begin{align*}
        3^{m - n}(3^n - 1) = 0 \pmod{3^n - 1}\\
        3^m - 3^{m - n} = 0 \pmod{3^n - 1}\\
        3^m = 3^{m - n} \pmod{3^n - 1}\\
        3^m - 1 = 3^{m - n} - 1 \pmod{3^n - 1}\\
        \qed
    \end{align*}

    По алгоритму Евклида и лемме (просто вычитаем одну степень из другой):
    \begin{align*}
        (3^{133} - 1, 3^{101} - 1) =\\
        (3^{101} - 1, 3^{32} - 1) =\\
        (3^{32} - 1, 3^5 - 1) =\\
        (3^2 - 1, 3^5 - 1) =\\
        (3^1 - 1, 3^2 - 1) =\\
        (2, 8) = 2
    \end{align*}

\dmquestion{7}

    \[
        \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{p - 1} =
        \frac{\frac{(p - 1)!}{1} + \frac{(p - 1)!}{2} + \ldots + \frac{(p - 1)!}{p - 1}}{(p - 1)!}
    \]

    Сгруппируем слагаемые в числителе так, чтобы их знаменатели в сумме равнялись $p$.
    Так можно сделать, потому что их четное число.
    \[
        \frac{
            \br{ \frac{(p - 1)!}{1} + \frac{(p - 1)!}{p - 1} } +
            \br{ \frac{(p - 1)!}{2} + \frac{(p - 1)!}{p - 2} } + \ldots
        }{(p - 1)!}
    \]

    Заметим, что каждая скобка тогда делится на $p$:
    \begin{gather*}
        \frac{(p - 1)!}{k} + \frac{(p - 1)!}{p - k} =\\[8pt]
        (p - 1)! \br{ \frac{(p - k) + k}{k(p - k)}} =\\[8pt]
        p\frac{(p - 1)!}{k(p - k)}
    \end{gather*}

    Так как это сумма факториалов, деленных на одно число, меньшее аргумента факториала, то это все еще целое число, а так как $p$ - простое и точно не делится на $k$ и $p - k$, то его можно вынести за скобку.

    Тогда наша сумма представляется в виде

    \[
        \frac{p \cdot Q}{(p - 1)!}
    \]

    Так как в факториале нет множителей, делящих $p$, то $p$ останется в числителе, значит, числитель делится на $p$ \qed
\end{document}