\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{interval}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\geometry{left=2.5cm,right=2.5cm,headsep=1cm,bottom=2cm,footnotesep=2cm,headheight=13pt}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{\ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年5月26日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{automata, positioning, arrows}

\newcounter{aufgc}
\newenvironment{example}[1]%
{\refstepcounter{aufgc}\textbf{例题1.\arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\lstset{basicstyle=\ttfamily}

\begin{document}

\section*{数论算法}

$a\mid b$, $a\nmid b$, $a\equiv b\pmod{m}$

$\gcd(a,b)$为最大的$d$，使得$d\mid a$且$d\mid b$，有$\gcd(a,0)=|a|$，$\gcd(a,b)=\gcd(-a,b)$，若$n\mid a,n\mid b$，则$n\mid \gcd(a,b)$

\begin{theorem}
    （裴蜀定理）对于任意不全为零的整数$a,b$，则$\gcd(a,b)$为集合$\{ax+by:x,y\in \mathbb{Z}\}$中的最小正元素.
\end{theorem}

\begin{proof}
    只需设该最小正值为$d'$，分别从$d\mid d'$和$d'\mid d$考虑即可.其中，$d\mid d'$显然，而$d'\mid d$需要反证.

    假如$d'\nmid d$，则有$d=kd'+r,0\leqslant r<d'$，而因为$d,d'$均为正整数，且$d\mid d'$，则$d<d',d=r$.但很难证明$d$是$a,b$的线性组合.

    我们选择证明$d'\mid a$，$d'\mid b$，依然反证，得到一个比$d'$更小的线性组合，矛盾，即可得到原结论.
\end{proof}

如果$n\mid ab$，且$\gcd(a,n)=1$，则$n\mid b$，这是因为$\gcd(a,n)=1$意味着存在$x,y$使得$ax+ny=1$，两边同时乘以$b$即可.

\begin{theorem}
    对于非负整数$a$和正整数$b$，有$\gcd(a,b)=\gcd(b,a\mod b)$.
\end{theorem}

由此引出欧几里得算法.

\begin{theorem}
    假设$F_k$为第$k$个斐波那契数列的元素，则如果$a>b\geqslant0$，欧几里得算法经过$k$次递归终止，有$a\geqslant F_{k+2},b\geqslant F_{k+1}$
\end{theorem}

反过来，如果$a>b\geqslant 0$，且$b<F_{k+1}$，欧几里得算法经过不超过$k$次迭代即可终止.由此给出欧几里得算法的时间复杂度$O(\min\{\log a,\log b\})$.

\end{document}