Fundamentos Matemáticos para Computação 1 - 2015.2 - IMD
Avaliação 2: Teoria dos Números, Congruência
Autor: Patrick Terrematte
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
% Fundamentos Matemáticos para Computação 1 - 2015.2
% Avaliação 2: Teoria dos Números, Congruência
% Autor: Patrick Terrematte
\documentclass[11pt,a4paper]{article}
%\usepackage[latin1]{inputenc} % Descomentar para compilar no windows
\usepackage[utf8x]{inputenc} % Comentar para compilar no windows
\usepackage{graphicx}
\usepackage{color}
\usepackage{xspace}
\usepackage[brazil]{babel}
%\usepackage[latin1]{inputenc}
\usepackage{amsfonts, amssymb,amsmath}
\usepackage{array,booktabs}
\usepackage{proof}
\usepackage{fancyhdr}
\usepackage{paralist}
%\usepackage[pdftex=true,pagebackref=true,bookmarks=true,bookmarksnumbered=true,pdffitwindow=true]{hyperref}
\usepackage{hyperref}
\usepackage{marginnote}
%\usepackage[top=Bcm, bottom=Hcm, outer=Ccm, inner=Acm, heightrounded, marginparwidth=Ecm, marginparsep=Dcm]{geometry}
\usepackage{comment}
\renewcommand{\b}{\textbf}
\newcommand{\noi}{\noindent}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\setlength{\textwidth}{170mm}%
\setlength{\textheight}{279mm}%
\setlength{\topmargin}{-30mm}%
%\setlength{\bottommargin}{ \,}%
\setlength{\oddsidemargin}{-20mm}
\setlength{\evensidemargin}{-30mm}%
\begin{document}
\frenchspacing
\begin{center}
\begin{minipage}{1.7cm}
\begin{center}
\includegraphics[width=1.7cm, height=2.0cm]{Brasao-UFRN.jpg}
\end{center}
\end{minipage}
\begin{minipage}{11.4cm}
\begin{center}
{\small \textsc{Universidade Federal do Rio Grande do Norte} \\
\textsc{Instituto Metrópole Digital}\\
\textsc{Bacharelado em Tecnologia da Informação} \\
\textbf{Disciplina:} Fundamentos Matemáticos para Computação I (IMD0028) \hspace{.65cm}\textbf{Semestre:} 2015.2\\
\textsc{Professor: Patrick Cesar Alves Terrematte}\\
}
\end{center}
\end{minipage}
\begin{minipage}{1.6cm}
\begin{center}
\includegraphics[width=2cm, height=1.1cm]{logoimd.png}
\end{center}
\end{minipage}
\end{center}
{\sf
\begin{center}
\Large \textbf{--- Avaliação: Unidade 2 ---}%
\end{center}
}\bigskip
\setlength{\marginparwidth}{5cm}
\small \noindent \textbf{Nome:}\hspace{0.3cm}\hrulefill \hrulefill
\hrulefill \hspace{0.1cm}
\textbf{Turma:}\hspace{0.1cm}\rule{1cm}{.1mm}\\*[0.1cm]
\thispagestyle{empty}\bigskip
\noindent - {\bf Todas as resoluções devem incluir os cálculos e raciocínios usados para obter a solução.}
%\noindent - Há um ponto extra distribuido na avaliação.
%\noindent - Não é necessário grampear as avaliações.
%\noindent - Escreva as respostas em apenas um lado de cada folha.
%\noindent - {\bf Mantenha as respostas em sequência.}
\noindent - {\bf No cabeçalho da folha de rascunho, \underline{escreva seu nome}.}
\noindent - {\bf No rodapé direito, confira a ordem das folhas, e escreva \underline{``Página $n$ de $m$''}, para $n$ e $m \in \N$.}
\noindent - {\bf Se for o caso, consideraremos valores já calculados em outras questões, basta indicar e justificar.}
\begin{enumerate}
%\begin{center}{\bf ÁREA 1}\end{center}
\item Demonstre, ou refute:
\begin{compactenum}
\item \marginnote{\textbf{(\rule{1.3cm}{.1mm}/2,0 pts)}} $\forall n \geq 1, n \in \N,~n^3 \equiv n~ (\text{mod } 3) $
\smallskip
{\bf Resposta:}
{\bf Demonstração por casos.} Verificar a congruência para os 3 únicos resíduos possíveis $r \in \{0, 1, 2\}$. Como qualquer número natural se reduz a um resíduo, os outros casos decorrem destes três casos:\\
\noi {\bf Caso 1:} $r = 0$. Note $0^3 \equiv 0~ (\text{mod } 3)$, dado que (0 mod 3) = (0 mod 3) pela definição de congruência.\\
\noi {\bf Caso 2:} $r = 1$. Note $1^3 \equiv 1~ (\text{mod } 3)$, dado que (1 mod 3) = (1 mod 3) pela definição de congruência.\\
\noi {\bf Caso 3:} $r = 2$. Note $2^3 \equiv 2~ (\text{mod } 3)$, dado que (8 mod 3) = (2 mod 3) pela definição de congruência.\\
{\bf Demonstração por indução simples alternativa.} \\
\noi {\bf Passo Base:} Para n = 1, note que para $1^3 \equiv 1~(\text{mod } 3)$, temos que $1 \equiv 1 (\text{mod } 3)$.\\
\noi {\bf Passo Indutivo:}
Suponha um arbitrário $k\in \N$, tal que $k^3 \equiv k~(\text{mod } 3)$.
Logo, pela definição de equivalência modular, temos que $3 \mid (k^3 - k)$. Ou seja, pela definição de divisibilidade:\\
(HI) $\exists w_1 \in \Z, k^3 - k = 3 w_1$
- Portanto, \emph{ temos que provar que } $\exists w_2 \in \Z , (k+1)^3 - (k+1) = 3 w_2$
\begin{tabular}{ l l}
$(k+1)^3 - (k+1)$ & = $ k^3 + 3k^2+ 3k + 1 - k - 1$ \\
& = $ k^3 + 3k^2+ 3k - k$ \\
& = $ (k^3 - k) + 3k^2+ 3k$\\
& = $ 3 w_1 + 3k^2+ 3k$, pela HI.\\
& = $ 3 (w_1 + k^2+ k)$\\
& = $ 3 w_2$, onde $w_2 = w_1 + k^2+ k$ e $w_2 \in \Z$
\end{tabular}
Pela definição de congruência, temos que $(k+1)^3 \equiv (k+1)~(\text{mod } 3)$. Portanto, é verdadeiro que $\forall n \geq 1, n \in N,~n^3 \equiv n~ (\text{mod } 3)$.\\
\smallskip
\item \marginnote{\textbf{(\rule{1.3cm}{.1mm}/2,0 pts)}} $\forall n \geq 1, n \in N,~9 \mid (4^n + 6n - 1)$.\\
\footnotesize{\emph{Note que uma hipótese pode ser utilizada mais de uma vez, ou podemos demonstrar lemas auxiliares.}} \normalsize
\smallskip
{\bf Resposta:}
{\bf Demonstração por indução simples.} \\
\noi {\bf Passo Base:} Para n = 1, note que para $9 \mid (4^1 + 6\cdot 1 -1)$, temos que $9 \mid 9$.\\
\noi {\bf Passo Indutivo:}
Suponha um arbitrário $k> 1 \in \Z$, tal que $9 \mid (4^k + 6 k - 1)$. Ou seja, pela definição de divisibilidade:\\
(HI) $\exists w_1 \in \Z, (4^k + 6 k -1) = 9 w_1$
- Portanto, \emph{ temos que provar que } $\exists w_2, 4^{k+1} + 6 (k+1) - 1 = 9 w_2$
\begin{tabular}{ l l}
$ 4^{k+1} + 6 (k+1) - 1 $ & = $ 4 \cdot 4^{k} + 6 k + 6 - 1 $ \\
& = $ 3 \cdot 4^{k} + (4^{k} + 6 k - 1) + 6 $, pois $4 \cdot 4^{k} = 3\cdot 4^k + 1 \cdot 4^k$ \\
& = $ (4^{k} + 6 k - 1) + 3 \cdot 4^{k} + 6 $, ajustando os termos. \\
& = $ 9w_1 + 3 \cdot 4^{k} + 6$, pela HI. \\
& = $ 9w_1 + 3 (9 w_1 - 6 k + 1) + 6$, pela HI, pois se segue de $4^k = 9 w_1 - 6 k + 1$.\\
& = $ 9w_1 + 27 w_1 - 18 k + 3 + 6$\\
& = $ 36 w_1 - 18 k + 9$\\
& = $ 9 ( 4 w_1 - 2 k + 1)$\\
& = $ 9 w_2$, onde $w_2 = 4 w_1 - 2 k + 1$ e $w_2 \in \Z$\\
\end{tabular}
Pela definição de divisibilidade, temos que $9 \mid (4^{k+1} + 6\cdot (k+1) - 1)$.\\ Portanto, é verdadeiro que $\forall n \in N,~9 \mid (4^n + 6n - 1)$.
\end{compactenum}
\pagebreak
\item Sabendo que o procedimento de criptografia RSA segue os seguintes passos:
\begin{tabular}{|p{17cm}|}
\hline
\textbf{Algorítmo para Geração de Chaves.} A comunicação entre a Alice e o Beto é realizada da seguinte forma:
\begin{compactenum}
\item[(1)] Gere dois números primos aleatórios $p$ e $q$ (distintos)
\item[(2)] Calcule $n = p\cdot q$
\item[(3)] Calcule $\phi = (p - 1) \cdot (q - 1)$
\item[(4)] Escolha um número $e$, tal que mdc($e, \phi) = 1$ e $ 1 < e < \phi$.
\item[(5)] Calcular o único número $d$ (inverso de $e$ módulo $\phi$) $1 < d < \phi$, tal que $e\cdot d \equiv 1 (\text{ mod } \phi)$.
\item[(6)] A chave privada é $d$ e a chave pública é o par ordenado $<e,n>$.
\end{compactenum}
\\ \hline
\end{tabular}
\begin{tabular}{|p{17cm}|}
\hline
\textbf{Algorítmo para encriptar.} Para encriptar uma mensagem $m$ para Alice, Beto faz o seguinte:
\begin{compactenum}
\item[(1)] Obtem a chave pública (autêntica) de Alice $(e, n)$
\item[(2)] Representa a mensagem $m$ como um inteiro em $\{0, 1, 2, ...n-1\}$.
\item[(3)] Calcula $c = m^e \text{ mod } n$
\item[(4)] Envia o texto encriptado $c$ para Alice.
\end{compactenum}
\\ \hline
\end{tabular}
\begin{tabular}{|p{17cm}|}
\hline
\textbf{Algorítmo para desencriptar:} Alice faz o seguinte com a mensagem de Beto:\\
\textbf{Entrada}: texto encriptado $c$, chave privada $d$\\
\textbf{Saída}: texto claro $m$ Para recuperar o texto claro $m$ a partir de $c$, Alice faz o seguinte:
\begin{compactenum}
\item[(1)] Utiliza a chave privada $d$ para calcular o texto claro $m$:
$$ m = c^d \text{ mod } n$$
\end{compactenum}
\\ \hline
\end{tabular}
\textbf{Considere o sistema RSA com os seguintes parâmetros $p = 5, q = 23$ e $e = 27$. }
\begin{compactenum}
\item \marginnote{\textbf{(\rule{1.3cm}{.1mm}/2,0 pts)}} Determine as chaves \textbf{privada} e \textbf{pública} do usuário.
\smallskip
\paragraph{Resposta:}
Chave pública: $(e, n) = (27, 115)$.\\
Chave privada: Calcular único inverso menor positivo de $e$ módulo $\phi$, tal que $e\cdot d \equiv 1 (\text{ mod } \phi)$.\\
\begin{tabular}{ l l l l}
27 & = $0 \cdot 88 $ & + &27 $\Longrightarrow 27 = 27 - 0 \cdot 88 $\\
88 & = $3 \cdot 27 $ & + &7 $\Longrightarrow 7 = 88 - 3 \cdot 27 $\\
27 & = $3 \cdot 7 $ & + &6 $\Longrightarrow 6 = 27 - 3 \cdot 7$\\
7 & = $1 \cdot 6 $ & + &1 $\Longrightarrow 1 = 7 - 1 \cdot 6$\\
6 & = $6 \cdot 1 $ & + &0
\end{tabular}
Logo, $mdc(27,88)= 1$.\\
Algorítmo para cálculo de MDC e constantes $s$ e $t$ do Teorema de Bézout:
\begin{tabular}{|r|r|r|r|r|r|r|r|}\hline
a & b & b div a & b mod a & s' & t' & s=t'-s'(b div a) & t= s' \\ \hline\hline
27 & 88 & 3 & 7 & 4 & -1 & -13 & 4 \\ \hline
7 & 27 & 3 & 6 & -1 & 1 & 4 & -1 \\ \hline
6 & 7 & 1 & 1 & 1 & 0 & -1 & 1 \\ \hline
1 & 6 & 6 & 0 & 0 & 1 & 1 & 0 \\ \hline
0 & 1 & - & - & - & - & 0 & 1 \\ \hline
\end{tabular}
\smallskip
Relação de Bézout: $ mdc(27, 88) = 1 = (-13) \cdot 27 + 4 \cdot 88$. Dessa forma, o coeficiente $s$ é -13.\\
Como a chave privada deve ser o único menor inverso positivo de $e$ módulo $\phi$) $1 < d < \phi$, tal que $27\cdot d \equiv 1 (\text{ mod } 88)$. Assim temos que calcular:\\
\begin{tabular}{ l l l l}
$-13\text{ mod }88$ & $= (-13) - \lfloor\frac{-13}{88} \rfloor \cdot 88 $ \\
& $= (-13) - \lfloor (-0,14..) \rfloor \cdot 88$ \\
& $= (-13) - (-1) \cdot 88$\\
& $= (-13) + 88 = 75$.
\end{tabular}
\smallskip
$d = 75$.
\smallskip
\item \marginnote{\textbf{(\rule{1.3cm}{.1mm}/3,0 pts)}} \textbf{Desencripte} o texto cifrado $c = 32$ para Alice. % Resolver 32^{75} mod 115 = 2^23 mod 115 = 48
\end{compactenum}
% 27 = 0 × 88 + 27
% 88 = 3 × 27 + 7
% 27 = 3 × 7 + 6
% 7 = 1 × 6 + 1
% 6 = 6 × 1 + 0
Nossa tarefa é desencriptar a cifra calculando com $d = 75, n = 115$ e $c = 32$:\\
$ m = c^d \text{ mod } n$
Especificamente,
$32^{75} \text{ mod } 115$
Note que a base 32 = $2^5$. Assim, considerando que agora teremos o expoente $5\cdot 75 = 375$. Aqui note que o módulo é co-primo com a base, $115 ~\bot~ 2$, assim usaremos o Teo. de Euler sabendo que
$$ 2^{\phi(115)} \equiv 1 (\text{ mod } 115)$$
\pagebreak
\begin{tabular}{ l l l l}
$(2^5)^{75} \text{ mod } 115$ & = $2^{375} \text{ mod } 115$ \\
& = $(2^{88})^4 \cdot 2^{23} \text{ mod } 115$, já que $375 = 4 * 88 + 23$\\
& = $1^4 \cdot 2^{23} \text{ mod } 115$, dado que $2^{\phi(115)} \equiv 1~ (\text{ mod } 115)$ \\
& = ($2^1 \cdot 2^2 \cdot 2^4 \cdot 2^8 \cdot 2^8) ~ \text{ mod } 115$, pois note que $2^{23} = 2^1 \cdot 2^2 \cdot 2^4 \cdot 2^8 \cdot 2^8$\\
& = ($2^1 \cdot 4 \cdot 16 \cdot 16^2 \cdot 16^2) ~ \text{ mod } 115$\\
& = ($2^1 \cdot 4 \cdot 16 \cdot (256 \text{ mod } 115) \cdot (256 \text{ mod } 115)) ~ \text{ mod } 115$\\
& = ($2^1 \cdot 64 \cdot 26 \cdot 26) ~ \text{ mod } 115$\\
& = ($128 \cdot 26 \cdot 26) ~ \text{ mod } 115$\\
& = ($13 \cdot 26 \cdot 26) ~ \text{ mod } 115$\\
& = ($13 \cdot 101) ~ \text{ mod } 115$\\
& = $ 1313 ~ \text{ mod } 115$ \\
& = 48
\end{tabular}
\smallskip
\item \marginnote{\textbf{(\rule{1.3cm}{.1mm}/1,0 pt~)}} Qual o menor valor positivo que satisfaz esta congruência linear?
%
$$81x \equiv 12 \ (\text{mod 264 } )$$
\smallskip
\paragraph{Resposta:} Note que 81, 12 e 264 são divisíveis por 3, e que $mdc(3, 264)$ é 3.
\begin{tabular}{ l l l l}
3 & = $0 \cdot 264 + 3$\\
264 & = $88 \cdot 3 + 0$ \\
\end{tabular}
Portanto, convertemos nosso problema em:
$$27x \equiv 4 \ (\text{mod 88 } )$$
Pelo item (a) da questão anterior temos que o inverso positivo de 27 módulo 88 é 75. Portanto,
\begin{tabular}{ r l l l}
$27x \cdot 75$ & $ \equiv 4 \cdot 75~ (\text{ mod 88 } )$ \\
$ x $ & $\equiv 300~ (\text{ mod 88 } )$, pois $27 \cdot 75 \equiv 1~ (\text{ mod 88 } )$ \\
$ x \text{ mod 88 } $ & $ = 300 \text{ mod 88}$, pela definição de equivalência modular.\\
$ x \text{ mod 88 } $ & $ = 36$
\end{tabular}
\item \marginnote{\textbf{(\rule{0.8cm}{.1mm}/1 pt extra)}} Após muitos conflitos políticos no Brasil em 2019, os \emph{illuminatis} decidem terceirizar uma intervenção militar e contratam um general chinês, que ficou encarregado de chefiar 500 soldados brasileiros antes de uma guerra civil, como para ele os ocidentais são todos muito parecidos, ele tinha uma certa dificuldade em contá-los. Seguindo uma intuição ancestral, após a guerra civil, o chinês alinhou os soldados em fileiras de 6 em 6 de forma que sobraram 3. Quando ele alinhou os soldados em fileiras de 7, também sobraram 3 soldados. Por fim, alinhou em fileiras de 11 e sobraram 5. Quantos soldados o general tinha no final?
Considerando,\\
$u = ( u_1\cdot M_1^{\varphi(m_1)} + u_2\cdot M_2^{\varphi(m_2)} + ... + u_r\cdot M_r^{\varphi(m_r)} ) \bmod m$
$m = 6 \cdot 7 \cdot 11 = 462$
$x \equiv 3 \ (\text{mod 6 } )$\\
$x \equiv 3 \ (\text{mod 7 } )$\\
$x \equiv 5 \ (\text{mod 11 } )$\\
$3 \cdot M_1 = 3 \cdot \left( \frac{m}{m_1}\right)^{\varphi(m_1)} = 3 \cdot \left( \frac{462}{6}\right)^{\varphi(6)} = 3 \cdot 77^{2} ~\text{mod 462 } = 3 \cdot 5929 ~\text{mod 462 } = 231 $\\
$3 \cdot M_2 = 3 \cdot\left( \frac{m}{m_2}\right)^{\varphi(m_2)} = 3 \cdot \left( \frac{462}{7}\right)^{\varphi(7)} = 3 \cdot 66^{6} ~\text{mod 462 } =
3 \cdot (66^2)^3 = 3 (4356)^3 ~\text{mod 462 } = 3\cdot (198)^3 ~\text{mod 462 } = $ \\$ 3 \cdot 7762392 ~\text{mod 462 } = 3 \cdot 330~ \text{mod 462 } = 66 $\\
$5 \cdot M_3 = 5 \cdot \left( \frac{m}{m_3}\right)^{\varphi(m_3)} = 5 \cdot \left( \frac{462}{11} \right)^{\varphi(11)} ~\text{mod 462 }= 5 \cdot 42^{10} ~\text{mod 462 } = 5 \cdot (42^2)^{5}~\text{mod 462 } = 5 \cdot 1764^5 ~\text{mod 462 } = (5 \cdot 378^2 \cdot 378^3 )~ \text{mod 462 } = (5 \cdot 126 \cdot 42)~ \text{mod 462 } = (168 \cdot 42)~ \text{mod 462 } = $\\ $ 7056~ \text{mod 462 } = 126$\\
$x = (231 + 66 + 126)~ \text{mod 462 } = 423 $\\
Verificando temos que \\
423 mod 6 = 3\\
423 mod 7 = 3\\
423 mod 11 = 5\\
Portanto, ficaram 423 soldados.
\end{enumerate}
\smallskip
%\end{enumerate}
\pagebreak
\setcounter{page}{1}
\vskip2ex
\begin{center}
\b{--- Propriedades e Teoremas ---}
\end{center}
\begin{itemize}
\item \b{Soma modular.} Sejam $ a $, $ b $ e $ n $ inteiros e $ n > 1 $, então
$$a + b \equiv ((a \textbf{ mod } n) + (b \textbf{ mod } n))\textbf{ mod } n$$
\item \b{Multiplicação modular.} Sejam $ a $, $ b $ e $ n $ inteiros e $ n > 1 $, então
$$a \cdot b \equiv ((a \textbf{ mod } n) \cdot (b \textbf{ mod } n))\textbf{ mod } n$$
\item \b{Exponenciação modular.} Sejam $ a $, $ b $ e $ n $ inteiros e $ n > 1 $, então
$$a^m \equiv ((a \textbf{ mod } n)^m)\textbf{ mod } n$$
\item \b{Regra do cancelamento I.}
Sejam $a, b, c, n \in Z$, com $ n > 0$. Se $c \perp n$, então
$$ac \equiv bc \ (\text{mod } n) \text{ se, e somente se, } a \equiv b \ (\text{mod } n)$$
\item \b{Regra do cancelamento II.} Sejam $a, b, c, n$ inteiros, com $n > 0$, então
$$ac \equiv bc \ (\text{mod } n) \text{ se, e somente se, } a \equiv b \ (\text{mod } \frac{n}{\text{mdc}(c, \ n)} )$$
\item \b{Resolvendo Congruências Lineares.} Sejam $ a, b, n$ inteiros, com $ n > 0$, e seja $d := \text{mdc}(a, n)$. Se $d \mid b$, então a congruência $ax \equiv b \ (\text{mod } n) $ possui uma solução $x$, e qualquer inteiro $x'$ é também solução \underline{se e somente} \underline{se} $x \equiv x' \ (\text{mod } \frac{n}{d})$.
\item \b{Inverso Modular.} Dizemos que, para um inteiro positivo $n$ e um inteiro $a$, temos que $a^{-1}_n$ é o \textbf{inverso de $a$ módulo $n$} se este é o menor inteiro positivo que satisfaz $$a \cdot a^{-1}_n \equiv 1 \ (\text{mod } n)$$
\item \b{Pequeno Teorema de Fermat.} Para qualquer número primo $p$ e $a \in Z$, sendo $p \nmid a$, então
$$a^{p-1} \equiv 1 \ \text{(mod } p)$$
\item \b{Método de computar a Totiente}. Se $ n = p_i^{e_1}\text{... } p_r^{e_r} $ é a fatoração de $n$ em primos, então
\begin{equation*}
\varphi(n) = \prod^r_{i=1} p_i^{e_i - 1}(p_i - 1) = n\prod_{i=1}^{r}(1- \frac{1}{p_i})
\end{equation*}
\item \b{Teorema de Euler.} Para quaisquer $ a, n \in Z$, sendo $ n > 0 $ e $ a \perp n$, então
$$ a^{\varphi(n)} \equiv 1 \text{ (mod } n) $$
\item \b{Teorema Chinês dos Restos.} Sejam $m_1, m_2, ..., m_r$ inteiros positivos tal que
\begin{equation*}
m_j \perp m_k\text{, quando } j \neq k
\end{equation*}
Sejam $u_1, u_2, ..., u_r$ inteiros, então há um único
inteiro $u$ que satisfaça as condições
\begin{equation*}
0 \leq u < m \quad \text{ e } \quad u \equiv u_j \pmod{m_j} \text{, para } 1 \leq j \leq r
\end{equation*}
Assim, o número que satisfaz tais condições é
\begin{equation*}
u = ( u_1\cdot M_1^{\varphi(m_1)} + u_2\cdot M_2^{\varphi(m_2)} + ... + u_r\cdot M_r^{\varphi(m_r)} ) \bmod m
\end{equation*}
em que $m = \prod\limits_{i=1}^r m_i$, $M_i = \frac{m}{m_i}$%, $u_i = p_i \bmod m$.
Alternativamente, o número pode ser determinado como
\begin{equation*}
u = u_1\cdot M_1 \cdot y_1 + u_2\cdot M_2 \cdot y_2 + ... + u_r\cdot M_r \cdot y_r\bmod m
\end{equation*}
em que $m = \prod\limits_{i=1}^r m_i$, $M_i = \frac{m}{m_i}$ e $y_i$ é o inverso de $M_i \bmod m$ %e $u_i = p_i \bmod m_i$.
\end{itemize}
\end{document}