[obm-l] Periodicidade mod p

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

A solucao do Gugu para o problema dos primos do Dirichlet me fez lembrar de
um outro problema que pode ser util numa olimpiada ou mesmo numa prova de
matematica de algum vestibular mais puxado:

Dado um primo p e inteiros a e b, analisar a periodicidade (mod p) da
sequencia definida por x(n) = a*x(n-1) + b, x(1) = inteiro qualquer.

Por exemplo, se a = 1, entao a sequencia eh:
x(1),
x(2) = x(1) + b,
x(3) = x(1) + 2b,
...
x(p) = x(1) + (p-1)b,
x(p+1) = x(1) + pb,
...

Se p divide b, entao a sequencia tem periodo 1 (mod p), ou seja, eh
constante (mod p). 
Se p nao divide b, entao a sequencia tem periodo p, pois quaisquer p termos
consecutivos irao formar um sistema completo de restos mod p.

Se p divide a, a sequencia eh constante e igual a b (mod p) a partir do
segundo termo (ou a partir do primeiro se p divide b).

O que acontece quando a = -1 e quando |a| > 1 e p nao divide a?


[]s,
Claudio.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================