notes.tex

\documentclass{article}

\usepackage[margin=1in]{geometry}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{calc}
\usepackage{lmodern}
\usepackage{pgfplots}
\usepackage{qtree}
\usepackage{slashed}
\usepackage{upgreek}
\usepackage{xfrac}
\usepackage[normalem]{ulem}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[hidelinks]{hyperref}

\begin{document}

\section{Conceitos Fundamentais}

\subsection{Divisão Euclidiana}
Sejam $a, b \in \mathbb{Z}$ com $b \neq 0$, a divisão euclidiana de $a$ por $b$ consiste na identidade
\[ a = b \cdot q + r \qquad q, r \in \mathbb{Z} \> \land \> 0 \leq r < b \]


\subsection{Divisibilidade}
Sejam $a, b \in \mathbb{Z}$ com $b \neq 0$, dizemos que $b$ divide $a$, denotando $b \mid a$, se
\[ \exists \> c \in \mathbb{Z}: \enspace a = b \cdot c \]
Propriedades:
\begin{itemize}
  \item $\forall \> a \in \mathbb{Z}: \enspace a \mid 0$
  \item $\forall \> a \in \mathbb{Z}: \enspace \pm 1 \mid a$
  \item $\forall \> a \in \mathbb{Z}: \enspace \pm a \mid a$
  \item $\forall \> c \in \mathbb{Z}: \enspace a \mid b \implies ac \mid bc$
  \item $\forall \> x, y \in \mathbb{Z}: \enspace a \mid b \> \land \> a \mid c \implies a \mid (bx + cy)$
  \item $\forall \> a, b \in \mathbb{Z}: \enspace a \mid b \> \land \> b \mid a \implies b = \pm a$
\end{itemize}


\subsection{Máximo Divisor Comum}
Sejam $a, b \in \mathbb{Z}$ com $(a, b) \neq (0, 0)$, o máximo divisor comum de $a$ e $b$ é um inteiro $d$ tal que
\begin{gather*}
  d \mid a \> \land \> d \mid b \\[5pt]
  \forall \> d': \enspace d' \mid a \> \land \> d' \mid b \implies d' \mid d
\end{gather*}
\vspace{-10pt}
\begin{tabbing}
  \uline{Lema}: \= Sejam $a, b \in \mathbb{Z}$ com $(a,b) \neq (0,0)$, e $q, r \in \mathbb{Z}$ com $a = b \cdot q + r$. \\
  \> O $\text{mdc}(a,b)$, se existe, é igual a $\text{mdc}(b, r)$.
\end{tabbing}
\vspace{7pt}
\uline{Identidade de Bézout}: Sejam $a, b \in \mathbb{Z}$ com $(a,b) \neq (0,0)$, então
\vspace{-5pt}
\[ \exists \, \alpha, \beta \in \mathbb{Z}: \enspace \alpha \cdot a + \beta \cdot b = \text{mdc}(a,b) \]
\uline{Lema de Euclides}: Sejam $a,b,c \in \mathbb{Z}$ com $a,b,c \neq 0$. Se $a|bc$ e $\text{mdc}(a,b) = 1$, então $a|c$. \\[10pt]
Propriedades: Sejam $a,b,c \in \mathbb{Z}$ com $a,b,c \neq 0$
\begin{itemize}
  \item $\text{mdc}(a,c) = \text{mdc}(b,c) \iff \text{mdc}(a b,c) = 1$
  \item $\text{mdc}(a,b) = d \iff \text{mdc} \left( \dfrac{a}{d}, \dfrac{b}{d} \right) = 1$
  \item $a \mid c \:\land\: b \mid c \implies \left( \dfrac{ab}{\text{mdc}(a,b)} \right) \bigg | \, c$
  \item $(a \mid c \:\land\: b \mid c \:\land\: \text{mdc}(a,b) = 1) \implies ab \mid c$
\end{itemize}


\subsection{Mínimo Multiplo Comum}
Sejam $a, b \in \mathbb{Z}$ com $(a, b) \neq (0, 0)$, o mínimo multiplo comum de $a$ e $b$ é um inteiro $m$ tal que
\begin{gather*}
  a \mid m \:\land\: b \mid m \\[5pt]
  \forall \> m': \enspace a \mid m' \:\land\: b \mid m' \implies m \mid m'
\end{gather*}
\uline{Teorema}: $\forall \, a, b \in \mathbb{Z}, (a, b) \neq (0, 0): \enspace \text{mmc}(a,b) = \dfrac{ab}{\text{mdc}(a,b)}$


\subsection{Fatoração}
\uline{Lema}: Seja $n = ab \in \mathbb{Z}$ com $n \neq 0, \pm 1$, então $a \leq \lfloor \sqrt{n} \rfloor \>\lor\> b \leq \lfloor \sqrt{n} \rfloor$.


\subsection{Números Primos}
Um número $p$ é primo se os únicos divisores de $p$ são $\pm1$ e $\pm p$.
\begin{tabbing}
  \uline{Lema}: \= Seja $p \in \mathbb{Z}$ primo, e $x_1, \hdots, x_n \in \mathbb{Z}$. \\
  \> Se $p \mid (x_1 \cdot \hdots \cdot x_n)$, então $p \mid x_i$ para ao menos algum $i \in [1, n] \subset \mathbb{Z}$.
\end{tabbing}
\vspace{10pt}
\uline{Teorema}: Qualquer número natural $n \geq 2$ é produto de um conjunto \uline{único} e finito de números primos.
\begin{tabbing}
  \uline{Corolário}: \= Seja $a \in \mathbb{Z}$ com $a \neq 0, \pm 1$. \\
  \> Sejam $p_1, \hdots, p_n \in \mathbb{Z}$ primos. \\
  \> Sejam $h_1, \hdots, h_n \in \mathbb{Z}$ maiores que $0$. \\
  \> $a$ pode ser escrito como $a = \pm \left( p_1^{h_1} \cdot \hdots \cdot p_n^{h_n} \right)$
\end{tabbing}
\begin{tabbing}
  \uline{Corolário}: \= Seja $a, b \in \mathbb{Z}$ com $a$ e $b \neq 0, \pm 1$. \\
  \> Sejam $\forall\: i : h_i, k_i \geq 0$, e $p_1, \hdots, p_n \in \mathbb{Z}$ primos tais que \\[3pt]
  \> $a = \pm \enspace p_1^{h_1} \cdot \hdots \cdot p_n^{h_n}$ \\[3pt]
  \> $b = \pm \enspace p_1^{k_1} \cdot \hdots \cdot p_n^{k_n}$ \\[3pt]
  \> Então: \\
  \>\begin{minipage}{\linewidth}
    \begin{itemize}
      \item $\text{mdc}(a,b) = p_1^{d_1} \cdot \hdots \cdot p_n^{d_n}$, onde $d_i = \text{min}(h_i, k_i)$
      \item $\text{mmc}(a,b) = p_1^{d_1} \cdot \hdots \cdot p_n^{d_n}$, onde $d_i = \text{max}(h_i, k_i)$
    \end{itemize}
  \end{minipage}
\end{tabbing}
\vspace{10pt}
\uline{Teorema}: Há um número infinito de números primos. \\[5pt]
\uline{Corolário}: Seja $p \in \mathbb{Z}$ primo com $p > 0$, então $\sqrt{p} \in \mathbb{Q}$.\\[10pt]
\uline{Teorema}: Não há forma polinomial que gere \uline{apenas} números primos. \\[10pt]
\uline{Teorema}: Sejam $a, b \in \mathbb{N}^+$ com $\text{mdc}(a,b) = 1$, então a sequência ${\left( an + b \right)}_{n=0}^{\infty}$ contém infinitos primos. \\[10pt]
A função para o número de primos menores que $x \in \mathbb{R}$ é
\[ \pi(x) \sim \frac{x}{\ln x} \]

\pagebreak

\subsubsection{Números de Fermat}
Os números de Fermat são dados pela função
\begin{gather*}
  F: \mathbb{N}^+ \to \mathbb{N}^+ \\
  F(n) = 2^{2^n} + 1
\end{gather*}
\uline{Teorema}: Nem todos números de Fermat são primos. \\[5pt]
\uline{Teorema}: Seja $a \geq 2 \in \mathbb{Z}$ e $a^2 + 1$ primo. Então $a$ é par e $n = 2^m$.
\begin{tabbing}
  \uline{Teorema}: \= $\forall \: k \in \mathbb{Z}, n \in \mathbb{N}^+: \text{mdc}(F(n), F(n + k)) = 1$. \\
  \> Ou seja, \uline{todos} números de Fermat são co-primos entre si.
\end{tabbing}
\uline{Corolário}: Como $F(1), \hdots, F(n)$ são co-primos, entre seus fatores há ao menos $n$ números primos distintos.

\subsubsection{Números de Mersenne}
Os números de Mersenne são dados pela função
\begin{gather*}
  M: \mathbb{P} \to \mathbb{N}^+ \\
  M(p) = 2^p - 1
\end{gather*}
\uline{Teorema}: Nem todos números de Mersenne são primos. \\[5pt]
\uline{Teorema}: Seja $a \in \mathbb{Z}$ com $a \geq 1$. Então $a^n - 1$ é primo se e somente se $a = 2$ e $n$ é primo.



\section{Congruências}

\subsection{Relações de Equivalência}
Uma relação sobre um conjunto $A$ é um subconjunto $R \subset A \times A$. \\
Dizemos que $a R b$ se $(a,b) \in R$. \\[5pt]
Uma relação \uline{pode} ter as seguintes propriedades:
\begin{itemize}
  \item Reflexividade: se $\forall \: a \in A: aRa$.
  \item Simetria: se $\forall \: a,b \in A: aRb \implies bRa$.
  \item Transitividade: $\forall \: a,b,c \in A: aRb \land bRc \implies aRc$.
  \item Antissimetria: se $\forall \: a,b \in A: aRb \land bRa \implies a = b$.
  \item Totalidade: se $\forall \: a,b \in A: aRb \oplus bRa$.
\end{itemize}
\uline{Definição}: Uma relação $R$ sobre $A$ é de \uline{equivalência} se ela é reflexiva, simétrica e transitiva.


\pagebreak


\subsection{Classes de Equivalência}
Seja $a \in A$ e $R$ uma relação de equivalência sobre $A$. Definimos a classe de equivalência de $a$ como
\[ {[a]}_R := \{ x \in A \mid aRx \} = \{ x \in A \mid xRa \} \]
Notação: $\bar{a} := {[a]}_m$ \\[5pt]
Propriedades:
\begin{itemize}
  \item $\forall \: a \in A: a \in {[a]}_R$
  \item ${[a]}_R = {[b]}_R \iff aRb$
  \item ${[a]}_R \cap {[b]}_R = \varnothing \iff a\slashed{R}b$
  \item As classes de equivalência de um conjunto formam uma partição deste: $\forall \: A: A = \bigsqcup\limits_{a \in A} {[a]}_R$
\end{itemize}
Seja $R$ uma relação de equivalência sobre $A$. Denotamos o conjunto das classes de equivalência de $R$
\[ A_{/R} := \{ {[a]}_R \mid a \in A \} \]


\subsection{Congruência}
Seja $m \in \mathbb{Z}$ com $m > 1$. Dizemos que $a$ é congruente $b$ módulo $m$ se $m \mid (a - b)$. Denota-se
\[ a \equiv_m b \]
\uline{Teorema}: Para qualquer $m > 1$, $\equiv_m$ forma uma relação de equivalência sobre $\mathbb{Z}$.
\begin{itemize}
  \item $\forall \: a \in \mathbb{Z}: a \equiv_m a$.
  \item $\forall \: a,b \in \mathbb{Z}: a \equiv_m b \implies b \equiv_m a$.
  \item $\forall \: a,b,c \in \mathbb{Z}: a \equiv_m b \land b \equiv_m c \implies a \equiv_m c$.
\end{itemize}
\vspace{5pt}
Propriedades:
\begin{itemize}
  \item $a \equiv_m 0 \iff m \mid a$.
  \item $a \equiv_m b \iff -a \equiv_m -b$.
  \item $a \equiv_m b \:\land\: a' \equiv_m b' \implies (a + a') \equiv_m (b + b')$.
  \item $a \equiv_m b \:\land\: a' \equiv_m b' \implies (a \cdot a') \equiv_m (b \cdot b')$.
  \item $\forall \: k \neq 0 \in \mathbb{Z}: a \equiv_m b \iff ka \equiv_m kb$.
\end{itemize}
\vspace{-2pt}
\begin{tabbing}
  \uline{Teorema}: \= Seja $m \in \mathbb{Z}$ com $m > 1$. Então $\mathbb{Z}_{/m} = \{ {[0]}_m, {[1]}_m, \hdots {[m - 1]}_m \}$ \\[5pt]
  \> Portanto, $\big| \mathbb{Z}_{/m} \big| = m$.
\end{tabbing}
\uline{Corolário}: Seja $p(x)$ um polinômio com coeficientes inteiros. Então $a \equiv_m b \implies p(a) \equiv_m p(b)$.
%Criterios de divisibilidade: 4, 5, 9, 11

\subsubsection{Inverso Aritmético}
Sejam $a, n \in \mathbb{Z}$. O inverso mod $n$ de $a$ é um número $a'$ tal que
\[ a \cdot a' \equiv_n 1 \]
\uline{Teorema}: O inverso de $a$ existe se e somente se $\text{mdc}(a,n) = 1$.

\subsubsection{Equações Lineares de Congruência}
Sejam $a, b, n \in \mathbb{Z}$ com $n \neq 0$. Uma equação linear de congruência é da forma
\[ ax \equiv_n b \]
Duas equações lineares de congruência são equivalentes se o conjunto solução de ambas é o mesmo.\\
\begin{tabbing}
  \uline{Teorema}: \= Uma equação linear de congruência $ax \equiv_n b$ possui solução inteira se e somente se \\[5pt]
  \>\begin{minipage}{\textwidth}
    \[ \text{mdc}(a,n) \mid b \]
    Se a equação possui uma ou mais soluções inteiras, e seja $d = \text{mdc}(a,n)$. \\
    Então, esta equação é equivalente à equação reduzida
    \[ \frac{a}{d} \cdot x \equiv_{\frac{n}{d}} \frac{b}{d} \]
    Seja $ax \equiv_n b$ uma equação de congruência reduzida ($\text{mdc}(a, n) = 1$). \\
    Seja $a'$ o inverso aritmético mod $n$ de $a$. \\
    Então, a equação é equivalente a
    \[ x \equiv_n b \cdot a' \]
  \end{minipage}
\end{tabbing}



\section{Resíduo}
Seja $n \in \mathbb{N}^*$ e $a \in \mathbb{Z}$. O resíduo $r$ de $a$ mod $n$ é o resto da divisão euclidiana de $a$ por $n$.
\[ r \equiv_n a \]
Portanto, o resíduo é \uline{único} e \uline{mínimo}.

% exponenciação modular: residuo de a^k mod n



\section{Sistemas Lineares de Congruência}
Um sistema linear de equações de congruência é do tipo
\[
  \begin{cases}
    a_1 \cdot x \equiv_{n_1} b_1 \\
    \qquad \vdots \\
    a_s \cdot x \equiv_{n_s} b_s \\
  \end{cases}
\]
Dizemos que o sistema é compatível se ele possuir ao menos uma solução inteira. \\[5pt]
Se um sistema é compatível, então todas suas equações são compatíveis. Então
\[ \forall\: i \in [1, s]:\> \text{mdc}(a_i, n_i) \mid b_i \]

\subsection{Sistema Chinês}
Um sistema chinês de equações de congruência é um conjunto
\[
  \begin{cases}
    x \equiv_{n_1} c_1 \\
    \quad \vdots \\
    x \equiv_{n_s} c_s
  \end{cases}
  \text{com mdc}(n_i, n_j) = 1 \quad \forall\: i \neq j
\]
\uline{Teorema chinês do resto}: Um sistema chinês tem única solução mod $n_1 \cdot \hdots \cdot n_s$. \\[10pt]
\uline{Teorema}: Sejam $m, n \in \mathbb{Z}$ co-primos. A congruência $x \equiv_{(m \cdot n)} a$ é equivalente ao sistema chinês
\[
  \begin{cases}
    x \equiv_m a \\
    x \equiv_n a
  \end{cases}
\]



\section{Anéis}
Seja $A$ um conjunto. Uma operação binária $*$ sobre $A$ é uma função
\[ *: A \times A \to A \]
Uma operação binária \uline{pode} ter as seguintes propriedades:
\begin{itemize}
  \item \makebox[6cm][l]{$\forall\: a,b,c \in A: a * (b * c) = (a * b) * c$} (associativa)
  \item \makebox[6cm][l]{$\exists\: \lambda \in A, \forall\: a \in A: a * \lambda = \lambda * a = a$} (elemento neutro)
  \item \makebox[6cm][l]{$\forall\: a \in A, \exists\: a' \in A: a * a' = a' * a = \lambda$} (inverso)
  \item \makebox[6cm][l]{$\forall\: a,b \in A: a * b = b * a$} (comutatividade)
\end{itemize}
\vspace{10pt}
\uline{Definição}: Um conjunto $A$ com operações $+$ e $\cdot$ é um anel comutativo unitário se
\begin{itemize}
  \item $+$ e $\cdot$ são associativos, comutativos e possuem elemento neutro.
  \item $+$ possui inverso.
\end{itemize}
\vspace{5pt}
Se, além disso, $(A, +, \cdot)$ é tal que $(A^*, \cdot)$ possui inverso, então dizemos que $A$ é um corpo.


\subsection{Anéis em $\mathbb{Z}$}
Podemos definir as operações $+$ e $\cdot$ para as classes de equivalência de qualquer $m$ sobre os inteiros
\[
  \arraycolsep=1.4pt\def\arraystretch{1.5}
  \begin{array}{lcl}
    \forall\: {[a]}_m, {[b]}_m \in \mathbb{Z}_{/m}: \enspace {[a]}_m & + & {[b]}_m := {[a + b]}_m \\
    \forall\: {[a]}_m, {[b]}_m \in \mathbb{Z}_{/m}: \enspace {[a]}_m & \cdot & {[b]}_m := {[a \cdot b]}_m
  \end{array}
\]
\uline{Teorema}: $(\mathbb{Z}_{/m}, +, \cdot)$ é um anel comutativo unitário $\forall\: m \in \mathbb{Z}$. \\[5pt]
\uline{Teorema}: Seja $\bar{a} \cdot \bar{c} = \bar{b} \cdot \bar{c}$ em $Z_{/m}$. Se $c$ e $m$ são co-primos, então $\bar{a} = \bar{b}$ \\[5pt]
\uline{Lema}: Seja $(A, +, \cdot)$ um anel comutativo unitário. O inverso de um de um elemento $a \in A$, se existe, é único.

\subsubsection{Conjunto das Unidades}
O conjunto das unidades de $\mathbb{Z}_{/m}$ são os elementos de $\mathbb{Z}_{/m}$ que possuem um inverso multiplicativo
\[ \mathcal{U}(\mathbb{Z}_{/m}) = \left\{ \bar{a} \in \mathbb{Z}_{/m} \>\big|\> \exists\: \bar{a}' \in \mathbb{Z}_{/m}: \bar{a} \cdot \bar{a}' = \bar{1} \right\} \]
\uline{Teorema}: $\left(\mathcal{U}(\mathbb{Z}_{/m}), \cdot \right)$ é um grupo comutativo. \\[10pt]
\uline{Teorema}: $\bar{a} \in \mathcal{U}(\mathbb{Z}_{/m})$ se e somente se $a$ e $m$ são co-primos.

\subsubsection{Divisores de Zero}
Um elemento $a \in A^*$ de um anel $(A, +, \cdot)$ é um divisor de zero se
\[ \exists\: b \in A^*: \enspace a \cdot b = 0 \]
\uline{Teorema}: Se $\bar{a} \in \mathbb{Z}_{/m}$ é uma unidade, então $\bar{a}$ não é divisor de zero.

\subsubsection{Teoremas}
\uline{Corolário}: Seja $m \geq 2 \in \mathbb{Z}$. As seguintes \uline{afirmações} são equivalentes:
\begin{itemize}
  \setlength\itemsep{0px}
  \item $(\mathbb{Z}_{/m}, +, \cdot)$ é um corpo, ou seja: $\mathcal{U}(\mathbb{Z}_{/m}) = \mathbb{Z}_{/m} \setminus \{\bar{0}\}$
  \item $(\mathbb{Z}_{/m}, +, \cdot)$ não tem divisores de zero.
  \item $m$ é primo
\end{itemize}
\uline{Lema}: Seja $p$ primo. Em $\mathbb{Z}_{/p}$, a equação $x^2 = \bar{1}$ tem como únicas soluções $\pm \bar{1}$. \\[10pt]
\uline{Teorema de Wilson}: Seja $n > 1 \in \mathbb{Z}$. Então $n > 0 \in \mathbb{P} \iff (n - 1)! \equiv_n -1$.

\subsubsection{Pequeno Teorema de Fermat}
Seja $p > 0 \in \mathbb{P}, a \in \mathbb{Z}$. Então
\[ a^p \equiv_p a \]
\uline{Corolário}: Seja $p > 0 \in \mathbb{P}, a \in \mathbb{Z}$ com $\text{mdc}(p,a) = 1$. Então
\[ a^{p-1} \equiv_p 1 \]

\subsubsection{Teorema de Euler-Fermat}
Seja $a, n \in \mathbb{Z}$ com $n \geq 2$ e $\text{mdc}(a,n) = 1$. Então
\begin{gather*}
  \varphi(n) = \big| \left\{ k \mid \forall\: n > 0 \in \mathbb{Z}: \text{mdc}(k,n) = 1 \right\} \big| = \big| \mathcal{U}(\mathbb{Z}_{/n}) \big| \\[5pt]
  a^{\varphi(n)} \equiv_n 1
\end{gather*}
\uline{Corolário}: $\forall\: p \in \mathbb{P},\, k \in \mathbb{N}^*: \> \varphi \left( p^k \right) = p^k - p^{k-1}$ \\[10pt]
\uline{Teorema}: Seja $n = p_1^{h_1} \cdot \hdots \cdot p_s^{h_s}$ a fatoração de $n$. Então
\[ \varphi(n) =  \Big( p_1^{h_1} - p_1^{h_1 - 1} \Big) \cdot \hdots \cdot \Big( p_s^{h_s} - p_s^{h_s - 1} \Big) \]

\subsubsection{Morfismos}
Sejam $(A, +, \cdot)$ e $(B, +, \cdot)$ anéis. Uma função $f: A \to B$ é um \uline{homomorfismo} se
\begin{itemize}
  \item $\forall\: x,y \in A: f(x+y) = f(x) + f(y)$
  \item $\forall\: x,y \in A: f(x \cdot y) = f(x) \cdot f(y)$
\end{itemize}
\vspace{5pt}
Uma função $f$ é um \uline{isomorfismo} se $f$ é um homomorfismo e $f$ é bijetiva. \\[5pt]
\uline{Teorema chinês do resto}: Sejam $m,n > 1 \in \mathbb{Z}$ co-primos. A função $\varphi$ é multiplicativa:
\[ \varphi (a \cdot b) = \varphi(a) \cdot \varphi(b) \]
\uline{Teorema}: Sejam $m,n > 1 \in \mathbb{Z}$. Então
\[ \mathcal{U} \left( \mathbb{Z}_{/m} \times \mathbb{Z}_{/n} \right) = \mathcal{U} \left( \mathbb{Z}_{/m} \right) \times \mathcal{U} \left( \mathbb{Z}_{/n} \right) \]
\\
\uline{Corolário}: Seja $n > 1 \in \mathbb{Z}, a \in \mathbb{Z}$ co-primos. O inverso aritmético de $a$ módulo $n$ é
\[ a' \equiv_n a^{\varphi(n) - 1} \]



\section{Pseudoprimos}
Um pseudoprimo é um número $n \in \mathbb{N}^*$ \uline{composto} tal que
\[ \exists\: b \in \mathbb{Z}, 1 < b < n - 1:\enspace b^{n - 1} \equiv_n 1 \]
Denota-se que $n$ é pseudoprimo na base $b$.

\subsection{Números de Carmichael}
Um número $n \in \mathbb{N}^*$ composto é um número de Carmichael se ele é pseudoprimo em \uline{todas} bases $b$ tais que mdc$(b,n) = 1$. \\[10pt]
\uline{Teorema de Korselt}: Um inteiro composto $n \geq 3$ é um número de Carmichael se e somente se
\begin{itemize}
  \item $\forall\: p \in \mathbb{P}: \> p \mid n \implies p^2 \nmid n$
  \item $\forall\: p \in \mathbb{P}: \> p \mid n \implies p - 1 \mid n - 1$
\end{itemize}

\subsection{Testes de Primalidade}
Sejam $n > 2 \in \mathbb{N}$ e $a \in \mathbb{Z}$ co-primos. Fatoramos $n - 1 = 2^s \cdot d$ com $d \geq 1$ ímpar. Há duas possibilidades:
\begin{itemize}
  \item $a^d \equiv_n 1$
  \item $\exists\: r \in [0, s - 1]:\enspace a^{2^r \cdot\, d} \equiv_n -1$
\end{itemize}
Se nenhum dos itens é verdadeiro, então $n$ é composto e $a$ é uma testemunha disso. \\[5pt]
Se $n$ é composto, mas ambos itens são satisfeitos, então $n$ é um pseudoprimo forte na base $a$.

\subsubsection{Teste de Miller-Rabin}
Seja $n > 2 \in \mathbb{Z}$ ímpar.
\begin{itemize}
  \item Escolhemos de forma aleatória um inteiro $a \in [2, n - 1]$. \\[5pt]
        Se mdc$(a,n) > 1$, então $n$ é composto.
  \item Fatoramos $n - 1 = 2^s \cdot d$ com $d$ ímpar, e calculamos em sequência os resíduos módulo $n$ de \\
        \[ a^d, {\left( a^d \right)}^2, {\left( a^d \right)}^4, \hdots, {\left( a^d \right)}^{2^{(s - 1)}} \]
        \begin{enumerate}
          \item Se $a^d \equiv_n \pm 1$, então $n$ pode ser primo.
          \item Se ${\left( a^d \right)}^{2^r} \equiv_n -1$ para algum $r \in [1, s - 1]$, então $n$ pode ser primo.
        \end{enumerate}
        Se nem (1) nem (2) acontecem, então $n$ é composto e $a$ é testemunha disso.
\end{itemize}
\begin{tabbing}
  \uline{Teorema}: \= Seja $n > 2$ ímpar composto. O conjunto $\{ 1, \hdots, n-1\}$ contém no máximo \\[5pt]
  \> $\dfrac{n - 1}{4}$ números co-primos com $n$ que \uline{não} são testemunhas de $n$ ser composto.
\end{tabbing}


\end{document}