Aritmética modular e permutações

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}
$$

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.

Grupos - Definição e exemplos

Definimos os seguintes conjuntos de transformações
$$
SO_2=\{\rot{\varphi}\mid 0\leq \varphi< 2\pi\};
$$
$$
O_2=SO_2\cup\{\refl{\varphi}\mid 0\leq \varphi< \pi\};
$$
$$
C_4=\{\rot{i\pi/2}\mid i\in\Z\};
$$
$$
D_4=C_4\cup \{\refl{i\pi/4}\mid i\in\Z\}.
$$
Tem-se que $SO_2$ e $O_2$ sao conjuntos infinitos. No entanto, é fácil verificar que
$$
C_4=\{\rot 0,\rot{\pi/2},\rot{\pi},\rot{3\pi/2}\}
$$
e que
$$
D_4=C_4=\{\refl{0},\refl{\pi/4},\refl{\pi/2},\refl{3\pi/4}\}.
$$
Então $|C_4|=4$ e $|D_4|=8$.

Os conjuntos $SO_2$, $O_2$, $C_4$, $D_4$ têm os seguintes propriedades

1. Todo conjunto de transformações acima é fechado sob composição. Isto é, se $X$ é uns dos conjuntos acima e $x,\ y\in X$, entao $xy\in X$.
2. Os conjuntos acima são fechados sob inverso. Isto é, se $X$ é uns dos conjuntos acima e $x\in X$, então $x$ é uma transformação invertível e $x^{-1}\in X$.
3. Todo conjunto acima contém a transformação identidade que é igual a $\rot 0$.

Motivado por esses exemplos, vamos agora formalizar a definição de grupo.

Seja $X\neq\emptyset$ um conjunto  munido de uma operação. Uma operação sobre $X$ é uma aplicação $f:X\times X\rightarrow X$. Usamos a notação $f(x,y)=x*y$. O par $(X,*)$ é chamado de grupo se

1. A operação é associativa. Ou seja $(x*y)*z=x*(y*z)$ para todo $x,\ y,\ z\in G$.
2. $G$ tem um elemento neutro também chamado de elemento identidade $e$, com a propriedade que $a*e=e*a=a$ para todo $a\in G$.
3. Todo elemento $a\in G$ tem um inverso, ou seja, existe um elemento $b$ tal que $a*b=b*a=e$. Esse $b$ é geralmente denotado por $a^{-1}$.

Alguns exemplos de grupos

1. $(\Z,+)$
2. $(\{M\in\mat n\mid\det M\neq 0\},\cdot)$
3. $(\Q\setminus\{0\},\cdot)$
4. $(\{-1,1\},\cdot)$
5. os conjuntos $SO_2$, $O_2$, $C_4$, $D_4$ munidos da operação de composição.

Rotações e reflexões

Rotações

Seja $\varphi$ um ângulo. Denotaremos por $\rot\varphi$ a rotação do plano $\R^2$ pela origem com ângulo $\varphi$ no sentido contrário aos ponteiros do relógio. Vamos calcular a forma matricial de $\rot\varphi$.  Seja $v=(v_1,v_2)\in\R^2$. Seja $\alpha$ o ângulo entre o vetor $v$ e o eixo $x$. Seja $v_0$ o vetor unitário na direção de $v$. Então $v$ pode ser escrito como  $$ v=\|v\|v_0=\|v\|(\cos\alpha,\sen\alpha). $$ Se $v'=v\rot\varphi$, então  $$ v'=\|v'\|(\cos(\alpha+\varphi),\sen(\alpha+\varphi))=\|v\|(\cos\alpha\cos\varphi-\sen\alpha\sen\varphi, \sen\alpha\cos\varphi+\cos\alpha\sen\varphi)=\|v\|(\cos\alpha,\sen\alpha) \begin{pmatrix} \cos\varphi & \sen\varphi\\ -\sen\varphi & \cos\varphi \end{pmatrix}. $$ Obtemos então que a rotação $\rot\varphi$ é uma transformação linear com matriz $$ A_\varphi=\begin{pmatrix} \cos\varphi & \sen\varphi\\ -\sen\varphi & \cos\varphi \end{pmatrix}. $$ Como $\det A_\varphi=\cos^2\varphi+\sen^2\varphi=1$, a transformação $\rot\varphi$ é invertível e claramente $(\rot\varphi)^{-1}=\rot{-\varphi}$.

Temos que

1. $\rot\varphi\rot\psi=\rot{\varphi+\psi}$;
2. $\rot 0=\mbox{id}$;
3. $(\rot\varphi)^{-1}=\rot{-\varphi}$.

Afirmação 2 é clara e afirmação 3 segue do argumento acima. Provamos afirmação 1. Seja $v\in\R^2$, $$v\rot\varphi\rot\psi=v \begin{pmatrix} \cos\varphi & \sen\varphi\\ -\sen\varphi & \cos\varphi \end{pmatrix} \begin{pmatrix} \cos\psi & \sen\psi\\ -\sen\psi & \cos\psi \end{pmatrix} =v \begin{pmatrix} \cos\varphi\cos\psi-\sen\varphi\sen\psi & \cos\varphi\sen\psi+\sen\varphi\cos\psi\\ -\cos\varphi\sen\psi-\sen\varphi\cos\psi & \cos\varphi\cos\psi-\sen\varphi\sen\psi \end{pmatrix}= v \begin{pmatrix} \cos(\varphi+\psi) & \sen(\varphi+\psi)\\ -\sen(\varphi+\psi) &\cos(\varphi+\psi) \end{pmatrix}=v\rot{\varphi+\psi}. $$

Reflexões

Consideramos a reflexão pelo eixo que passe pela origem e tem ângulo $\varphi$ com o eixo $x$. Denotamos essa reflexão por $\refl\varphi$. Dado $v=(v_1,v_2)\in\R^2$, seja $\alpha$ o ângulo de $v$ com o eixo $x$, e temos que  $$ v\refl\varphi=v\rot{-2(\alpha-\varphi)}=v\rot{-2\alpha}\rot{2\varphi}=(v_1,-v_2)\rot{2\varphi}= (v_1,v_2) \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} \cos 2\varphi & \sen 2\varphi\\ -\sen 2\varphi & \cos 2\varphi \end{pmatrix}= v\begin{pmatrix} \cos 2\varphi & \sen 2\varphi\\ \sen 2\varphi & -\cos 2\varphi \end{pmatrix}. $$ Obtemos então que $\refl\varphi$ é uma transformação linear com a matriz  $$ B_\varphi=\begin{pmatrix} \cos 2\varphi & \sen 2\varphi\\ \sen 2\varphi & -\cos 2\varphi \end{pmatrix}. $$ Como $\det B_\varphi=-\cos^22\varphi-\sen^22\varphi=-1$, a transformação $\refl\varphi$ é invertível. De fato, $$ \begin{pmatrix} \cos 2\varphi & \sen 2\varphi\\ \sen 2\varphi & -\cos 2\varphi \end{pmatrix} \begin{pmatrix} \cos 2\varphi & \sen 2\varphi\\ \sen 2\varphi & -\cos 2\varphi \end{pmatrix} =\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix},  $$ que implica que $(\refl\varphi)^{-1}=\refl\varphi$.

Composição de reflexões e rotações

Já vimos que a composição de 2 rotações é uma rotação. No entanto, a composição de 2 reflexões não é geralmente uma reflexão. De fato $$ v\refl\varphi\refl\psi =v\begin{pmatrix} \cos 2\varphi & \sen 2\varphi\\ \sen 2\varphi & -\cos 2\varphi \end{pmatrix}\begin{pmatrix} \cos 2\psi & \sen 2\psi\\ \sen 2\psi & -\cos 2\psi \end{pmatrix}= v\begin{pmatrix} \cos 2\varphi\cos 2\psi+\sen 2\varphi\sen 2\psi & \cos 2\varphi\sen 2\psi-\sen 2\varphi\cos 2\psi\\ \sen 2\varphi\cos 2\psi-\cos 2\varphi\sen 2\psi & \sen 2\varphi\sen 2\psi+\cos 2\varphi\cos 2\psi\end{pmatrix}= v\begin{pmatrix} \cos 2(\psi-\varphi) & \sen 2(\psi-\varphi)\\ -\sen 2(\psi-\varphi) & \cos 2(\psi-\varphi). \end{pmatrix}=v\rot{2(\psi-\varphi)}. $$ Obtemos então que a composição de 2 reflexões é uma rotação.

Sejam $\varphi$ e $\psi$ ângulos. Então

1. $\refl\varphi\refl\psi=\rot{2(\psi-\varphi)}$
2. $\rot\varphi\refl\psi=\refl{\psi-\varphi/2}$;
3. $\refl\varphi\rot\psi=\refl{\varphi+\psi/2}$.

Afirmação 1. é consequência do argumento acima. Demonstramos 2. Temos de 1. que $\refl{\vartheta}\refl{\psi}=\rot{2(\psi-\vartheta)}$. Usando que $\refl{\psi}^{-1}=\refl{\psi}$, obtemos que $\refl{\vartheta}=\rot{2(\psi-\vartheta)}\refl{\psi}$. Agora substituímos $\varphi=2(\psi-\vartheta)$ e $\vartheta=\psi-\varphi/2$ e obtemos 2. A demonstracao de 3. é similar.

Transformações lineares

Seja
$$
\R^n=\{(v_1,\ldots,v_n)\mid v_i\in\R\}.
$$
Vamos considerar elementos de $\R^n$ como vetores linhas. Dada uma matriz $A\in \mat n$ (denotamos por $\mat n$ o conjunto de matrizes $n\times n$), definimos a aplicação
$$
T_A: \R^n\rightarrow \R^n,\quad v\mapsto vA.
$$
A imagem de $v$ sobre $T_A$ vai ser denotada por $vT_A$. Tem-se que $vT_A=vA$. A aplicação $T_A$ é dito transformação linear com matriz $A$. As propriedades principais de transformações lineares estão sumarizados no lema seguinte.

Sejam $A,\ B\in\mat n$, $u,\ v\in\R^n$ e $\alpha\in\R$.  Tem-se

1. $(u+v)T_A=uT_A+v T_A$;
2. $(\alpha u)T_A=\alpha(uT_A)$;
3. $T_I=\mbox{id}$;
4. $(0,\ldots,0)T_A=(0,\ldots,0)$;
5. $(vT_A)T_B=v T_{AB}$;
6. $T_A$ é invertível se e só se $A$ é invertível (se e só se $\det A\neq 0$). Neste caso $(T_A)^{-1}=T_{A^{-1}}$.

A demonstração das afirmações é fácil usando as propriedades das operações matriciais. Por exemplo em (5)
$$ (v T_A)T_B=(vA)T_B=(vA)B=v(AB)=v T_{AB}. $$

As outras afirmações podem ser demonstradas similarmente.