Instituto de Matemática - UFRGS - Mat01097 - Seminário Integrador I

Exercício: periodicidade usando grupos cíclicos

Um exemplo interessante de função periódica ocorre quando temos um grupo finito cíclico $M_m = \{1,2,\dots,m-1\}$, de multiplicações modulo $m$ e um elemento gerador $d$. Isto é possível para $m$ da forma $m=2,3,4,p^k$ ou $2p^k$, onde $p$ é um número primo ímpar. Neste caso, para alguns $d \in M_m$, $\displaystyle f(n) = d^n \mbox{ modulo } m $ é uma função de período $m-1$. A operação de grupo é a multiplicação modulo $m$, o que significa que repetidamente aplicamos multiplicação seguida de cálculo do resto da divisão por $m$.

Por exemplo, considere $m=5$, e $d=3$. Primeiramente, convença-se que avaliar $d^n$ e aplicar modulo uma única vez é equivalente a multiplicar por $d$ e tomar modulo $n$ vezes. Dessa forma, $f(1) = d = 3$,

$\displaystyle f(2) = d \cdot f(1) \mbox{ modulo } 3 = 4$,

$\displaystyle f(3) = d \cdot f(2) \mbox{ modulo } 3 = 2$,

$\displaystyle f(4) = d \cdot f(3) \mbox{ modulo } 3 = 1$

A tabela abaixo mostra as quantidades $\displaystyle f(n) = d^n \mbox{ modulo } m, n=1,2,\dots$.

$n$ 1 2 3 4 5 6 7 8 9 10 11 ...
$f(n)$ 3 4 2 1 3 4 2 1 3 4 2 ...
onde confirmamos que, após gerar $M_5$ nas primeiras quatro potências, repetem seus valores periodicamente, conforme $n$ cresce.

Veja aqui e aqui mais detalhes sobre grupos cíclicos.

Para fixar os conceitos acima, use a ferramenta ao lado para gerar tabela $(n,f(n))$ para $m$, $d$ e $n$ escolhidos. Observe a periodicidade em todas as situações. Observe que o período é m-1 para algumas poucas combinações de valores de e . Tente m=11 com d=3 , d=5 e d=7, por exemplo.


Joao Batista Carvalho 2013-04-09