1

I am give a sequence defined by the relation

$s_{n + 3} = s_{n + 1} + as_{n}$

and need to determine, for which value of $a \in \{0, ... , 9\}$ the period of a sequence in the field $\mathbb{F}_{31}$ is the longest.

From the relation I derived a characteristic polynomial $\varphi(z) = z^3 - z - a$. Since the degree of the polynomial is 3, it's order (and the period of a sequence) must divide $31^3 - 1$. Trying all of divisors by hand seems not right.

Are there any other methods or observations that could be made to simplify the task?

Moisej Braver
  • 199
  • The polynomial you should consider is actually $z^3-z-a$ not $z^2-z-a$. You missed the jump between $s_{n+1}$ and $s_{n+3}$ (or is this a typo ?) – Ewan Delanoy Oct 28 '17 at 12:58
  • Oh, it's actually my mistake, thanks for pointing that out. I will edit the post – Moisej Braver Oct 28 '17 at 13:12
  • While $N=31^3-1$ has a lot of divisors, it has only four prime divisors : $2,3,5$ and $331$ (in fact $N=2 \times 3^2 \times 5 \times 331$ ). So, you only need to check the four divisors $\frac{N}{p}$ for $p=2,3,5$ or $331$. – Ewan Delanoy Oct 28 '17 at 13:38
  • Why does the order necessarily one of the $\frac{N}{p}?$ – Moisej Braver Oct 28 '17 at 13:47
  • 1
    It is not necessarily one of the $\frac{N}{p}$, but either it is maximal (equal to $N$), or it divides one of the $\frac{N}{p}$. – Ewan Delanoy Oct 28 '17 at 13:49
  • But how does it help me to find the period of the sequence? If, suppose, order divides $\frac{N}{331}$, I still don't know the order exactly – Moisej Braver Oct 28 '17 at 13:53
  • What happens here is that for $a=3$, the order is exactly $N$, and for other $a$, the order divides $31^2-1$. – Ewan Delanoy Oct 28 '17 at 13:55

0 Answers0