Intereting Posts

Pairs of points exactly $1$ unit apart in the plane
Union of ascending chain of Topologies
evaluation of series
Commutator subgroup of a dihedral group.
Product of two algebraic varieties is affine… are the two varieties affine?
The importance of basis constant
locally lipschitz implies lipschitz
Sequence of Rationals Converging to a Limit
Showing that $X^2$ and $X^3$ are irreducible but not prime in $K$
$(xy + 1)(yz + 1)(zx + 1) $ is a perfect square if and only if each factor is
On the separation axiom in a Lawvere or “generalized” metric space
The Uniqueness of a Coset of $R/\langle f\rangle$ where $f$ is a Polynomial of Degree $d$ in $R$
Cluster point of a function at a point
Examples of mathematical induction
Calculating prime numbers

Consider a Fibonacci sequence, except in $\mathbb Z_n$ instead of $\mathbb Z$:

$$F(1) = F(2) = 1$$ $$F(n+2) = F(n+1) + F(n)$$

It is easy to see that each of these sequences must cycle through some sequence and repeat. Consider, for example, the sequence in $\mathbb Z_4$:

- For what $n$ is $U_n$ cyclic?
- Cyclic group generators
- Find a generator of the multiplicative group of $\mathbb{Z}/23\mathbb{Z}$ as a cyclic group
- Suppose $G$ is a group of order 4. Show either $G$ is cyclic or $x^2=e$.
- Show $\langle a^m \rangle \cap \langle a^n \rangle = \langle a^{\operatorname{lcm}(m, n)}\rangle$
- units of group ring $\mathbb{Q}(G)$ when $G$ is infinite and cyclic

$$1,1,2,3,1,0,1,1,2,3,1,0,\dots$$

Is there a nice way to describe the length of the sequence that results before repeating? Clearly, it must be less than $n^2$, since that would cycle through all possible combinations of $a,b$ with $a,b \in \mathbb Z_n$, and once you repeat two combinations, you have a cycle.

\begin{align*}

\mathbb Z_2: 1,1,0,\dots & 3 \\

\mathbb Z_3: 1,1,2,0,2,2,1,0,\dots & 8 \\

\mathbb Z_4: 1,1,2,3,1,0,\dots & 6 \\

\mathbb Z_5: 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,\dots & 20

\end{align*}

Examining the sequences above, it seems “obvious” that there’s some pattern (just look at how $0$ occurs every $5$th number). Is there a “nice” way to describe these sequences (such as a way to calculate the $k^{th}$ term in a sequence), and, in particular, a rule for the lengths of the cycles?

- Prove or disprove that ${F_{n}^2} + 43$ is always a composite
- Induction Proof: Formula for Sum of n Fibonacci Numbers
- Isomorphism of a product $C_n \times C_m$ of cyclic groups with the cyclic group $C_{mn}$
- On the Factor group $\Bbb Q/\Bbb Z$
- Prove by induction Fibonacci equality
- GCD of Fibonacci-like recurrence relation
- induction proof of fibonacci number
- $n$ positive integer, then $n=\sum_{d|n} \phi(d)$ (proof Rotman's textbook)
- How to prove gcd of consecutive Fibonacci numbers is 1?
- Is ${\mathbb Z} \times {\mathbb Z}$ cyclic?

I found a way to do this with prime $n.$ Not sure how well it extends to prime powers.

We want to know what happens to the pair of consecutive entries $(x,y),$ shifting over one to get $(y,x+y).$ So we define the matrix

$$ A \; = \;

\left( \begin{array}{rr}

0 & 1 \\

1 & 1

\end{array}

\right) ,

$$ and note

$$

\left( \begin{array}{rr}

0 & 1 \\

1 & 1

\end{array}

\right)

\left( \begin{array}{c}

x \\

y

\end{array}

\right) \; = \;

\left( \begin{array}{c}

y \\

x+ y

\end{array}

\right)

$$

We find $A^2 = A + I,$ as well as $A^{-1} = A – I.$ As a result, the set of sums of powers of $A$ make a commutative ring; we calculate

$$ A^3 = 2A + I, $$

$$ A^4 = 3A + 2I, $$

$$ A^5 = 5A + 3I, $$

$$ A^6 = 8A + 5I, $$

$$ A^7 = 13A + 8I, $$

$$ A^8 = 21A + 13I, $$

and so on.

We do not know for sure that we have a repetition until we have repeated the pair $(x,y).$ Next, what if we regard the coefficients in this ring as elements of the field $\mathbf Z / p \mathbf Z ?$

We would like to know the smallest $m$ such that

$$ A^m \equiv I \pmod p. $$ There are two parts to this. We illustrate first.

$$ A^3 \equiv I \pmod 2. $$

$$ A^4 \equiv 2I \pmod 3, 2^2 \equiv 1 \pmod 3, A^8 \equiv I \pmod 3. $$

$$ A^5 \equiv 3I \pmod 5, 3^4 \equiv 1 \pmod 5, A^{20} \equiv I \pmod 5. $$

$$ A^8 \equiv 6I \pmod 7, 6^2 \equiv 1 \pmod 7, A^{16} \equiv I \pmod 7. $$

For each prime, the second exponent is a factor of $p-1,$ as

$$ \lambda^{p-1} \equiv 1 \pmod p. $$

I forgot one item earlier. If $p \equiv 2,3 \pmod 5,$ then there are no solutions to $x^2 – x – 1 \pmod p,$ the thing is irreducible, and our ring of matrices is a field with $p^2$ elements. The set of nonzero elements is a multiplicative group with $p^2 – 1$ elements. It follows that, with our $A^m \equiv I \pmod p,$ that $m | (p^2 – 1).$

For $p = 5$ or $p \equiv 1,4 \pmod 5,$ the ring has zero divisors, given explicitly by the factors of $x^2 – x – 1 \pmod p$ and scalar multiples of those. Annoying. On the other hand, for $p \equiv 1,4 \pmod 5$ it appears $A^{p-1} \equiv I \pmod p,$ true for $p=11,19,29,31,41,$ and perhaps provable.

From the link given in comments above about Pisano periods, I finally understand how to do $p \equiv 1,4 \pmod 5.$ Let $\phi$ be either of the two distinct roots of $\phi^2 – \phi – 1 \equiv 0 \pmod p. $ Then, with the numbering $F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5,$ we find

$$ F_n = \frac{\phi^n – (1-\phi)^n}{2 \phi – 1}. $$

Using $a^{p-1} \equiv 1 \pmod p$ and $\phi^2 \equiv \phi + 1 \pmod p$ and $\frac{1}{\phi} \equiv \phi – 1 \pmod p,$

we find both

$$ F_{p-1} \equiv 0 \pmod p, \; \; \; F_{p-2} \equiv 1 \pmod p. $$

From our earlier discussion of the matrix $A,$ we see that

$$ A^n = F_n A + F_{n-1} I, $$ pointed out below by awllower. So

$$ A^{p-1} = F_{p-1} A + F_{p-2} I \equiv I \pmod p. $$

As a result, any such sequence, Fibonacci or Lucas or what have you, repeats with period $p-1$ or some divisor thereof.

- limit of the sequence $a_n=1+\frac{1}{a_{n-1}}$ and $a_1=1$
- Determining k: $\int_{6}^{16} \frac{dx}{\sqrt{x^3 + 7x^2 + 8x – 16}} = \frac{\pi}{k}$
- summation of a trigonometric series
- Finding the power series of $\arcsin x$
- Extending exponentiation to reals
- What can we say about a locally compact Hausdorff space whose every open subset is sigma compact?
- Can a real symmetric matrix have complex eigenvectors?
- What is a homotopy equivalence?
- Deduction Theorem + Modus Ponens + What = Implicational Propositional Calculus?
- Is there a “closed” form of sequence $u_{n+1}=\frac{u_n^2}{u_n+1}$
- Raising a partial function to the power of an ordinal
- How to win at roulette?
- Treatise on non-elementary integrable functions
- Integral $\int_{1}^{2011} \frac{\sqrt{x}}{\sqrt{2012 – x} + \sqrt{x}}dx$
- Prove that if $\alpha, \beta, \gamma$ are angles in triangle, then $(tan(\frac{\alpha}{2}))^2+(tan(\frac{\beta}{2}))^2+(tan(\frac{\gamma}{2}))^2\geq1$