Aritmética modular
Seja $n\geq 2$ um inteiro. Denotamos por $\Z/n\Z$ o conjunto $\{0,\ldots,n-1\}$. Vamos introduzir duas operações sobre $\Z/n\Z$, uma adição e uma multiplicação. Relembramos a Teorema de divisão:
Se $a,\ b\in\Z$ com $b\neq 0$ existem unicamente $q,\ r\in \Z$ tais que $0\leq r< |b|$ e $a=qb+r$.
Adição: Sejam $a,\ b\in\Z/n\Z$. Definimos
$$
a\oplus b
\left\{\begin{array}{ll}
a+b & \mbox{se $a+b\leq n-1$}\\
a+b-n & \mbox{ se $a+b\geq n$}
\end{array}\right.
$$
Multiplicação: Sejam $a,\ b\in\Z/n\Z$. Escreva $ab=qn+r$ tal que $0\leq r\leq n-1$. Definimos $a\odot b=r$.
A estrutura $(\Z/n\Z,\oplus)$ é sempre um grupo. Pois, a operação $\oplus$ é associativa, $0$ é elemento neutro, e o inverso de $a\in\Z/n\Z$ é $n-a$. A situação com $\odot$ é mais complicada. A operação $\odot$ é associativa e $1$ é um elemento neutro. Por outro lado, o elemento $0$ jamais tem inverso com respeito à operação $\odot$. De fato, $0a=0$ para todo $a$, pois não existe $a\in\Z/n\Z$ tal que $0a=1$.
$(\Z/n\Z\setminus\{0\},\odot)$ é um grupo se e só se $n$ é primo.
Se $n$ não é primo, então existem $2\leq a,\ b\leq n-1$ tais que $n=ab$. Neste caso $a\odot b=0$ e $\Z/n\Z\setminus\{0\}$ não é fechado sob $\odot$.
Assumimos que $n$ é primo. Mostramos primeiro que $\Z/n\Z\setminus\{0\}$ é fechado sob $\odot$. Sejam $a,\ b\in \Z/n\Z\setminus\{0\}$. Se $a\odot b\not\in \Z/n\Z\setminus\{0\}$, então $a\odot b =0$, e usando a definição de $\odot$, temos que $ab=qn$. Então $n\mid ab$. Como $n$ é primo, $n\mid a$ ou $n\mid b$. Isso é uma contradição, pois $a,\ b\in\{1,\ldots,n-1\}$.
Mostramos agora que $a\in \Z/n\Z\setminus\{0\}$ tem inverso. Como $n$ é primo, $\mbox{mdc}(a,n)=1$. Logo existem $u,\ v\in\Z$ tal que $ua+vn=1$. De fato, se $k\in\Z$ e $u'=u+kn$ e $v'=v-ka$ é também uma solução. Então existe uma escolha de $k$ tal que $u'\in\{0,\ldots,n-1\}$. Como claramente $u'\neq 0$, obtemos que $u'\in\Z/n\Z\setminus\{0\}$. Logo $u'a=-v'n+1$ que implica que $u'\odot a=1$. Então $a^{-1}=u'$.
Permutações.
Seja $\Omega$ um conjunto finito. Vamos geralmente assumir que $\Omega=\{1,\ldots,n\}$. Definimos
$$
\mbox{Sym}\,\Omega=S_n=\{\sigma:\Omega\rightarrow\Omega\mid \mbox{$\sigma$ é bijeção}\}.
$$ Se $\sigma\in S_n$ e $i\in\Omega$, a imagem de $i$ sob $\sigma$ é escrita $i\sigma$. Se $\sigma\in S_n$ vamos escrever $\sigma$ como $\begin{pmatrix} 1 & 2 & \cdots & n \\ 1\sigma & 2\sigma & \cdots & n\sigma\end{pmatrix}$. Os elementos de $S_n$ são chamados de permutações.
A composição de duas permutações é uma permutação, então a composição é uma operação associativa sobre $S_n$. Como a identidade $\begin{pmatrix} 1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n\end{pmatrix}$ é uma permutação e toda permutação é invertível, nós obtemos que $S_n$ munido da operação de composição é um grupo.
Nós escrevemos permutações como produtos de ciclos. Consideramos por exemplo a permutação
$$
\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 1 & 2 & 7 & 6 & 5 & 4\end{pmatrix}
$$
$$ Se $\sigma\in S_n$ e $i\in\Omega$, a imagem de $i$ sob $\sigma$ é escrita $i\sigma$. Se $\sigma\in S_n$ vamos escrever $\sigma$ como $\begin{pmatrix} 1 & 2 & \cdots & n \\ 1\sigma & 2\sigma & \cdots & n\sigma\end{pmatrix}$. Os elementos de $S_n$ são chamados de permutações.
A composição de duas permutações é uma permutação, então a composição é uma operação associativa sobre $S_n$. Como a identidade $\begin{pmatrix} 1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n\end{pmatrix}$ é uma permutação e toda permutação é invertível, nós obtemos que $S_n$ munido da operação de composição é um grupo.
Nós escrevemos permutações como produtos de ciclos. Consideramos por exemplo a permutação
$$
\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 1 & 2 & 7 & 6 & 5 & 4\end{pmatrix}
$$
A permutação $\sigma$ permuta ciclicamente os elementos $1\mapsto 3\mapsto 2 \mapsto 1$, os elementos $4\mapsto 7\mapsto 4$, e os elementos $5\mapsto 6\mapsto 5$. Então a permutação $\sigma$ é geralmente escrita na forma $(1,3,2)(4,7)(6,5)$.
Toda permutação pode ser escrita unicamente, a menos da ordem dos fatores, como produto de ciclos.
Toda permutação pode ser escrita unicamente, a menos da ordem dos fatores, como produto de ciclos.
Nincsenek megjegyzések:
Megjegyzés küldése