Fixed Points of $K$ -Fibonacci Sequences

Brennan Benfield and Oliver Lippard Brennan Benfield: Department of Mathematics and Statistics, University of North Carolina at Charlotte, 9201 University City Blvd., Charlotte, NC 28223, USA Oliver Lippard: Department of Mathematics and Statistics, University of North Carolina at Charlotte, 9201 University City Blvd., Charlotte, NC 28223, USA

Abstract.

A $K$ -Fibonacci sequence is a binary recurrence sequence where $F_{0}=0$ , $F_{1}=1$ , and $F_{n}=K\cdot F_{n-1}+F_{n-2}$ . These sequences are known to be periodic modulo every positive integer greater than $1$ . If the length of one shortest period of a $K$ -Fibonacci sequence modulo a positive integer is equal to the modulus, then that positive integer is called a fixed point. This paper determines the fixed points of $K$ -Fibonacci sequences according to the factorization of $K^{2}+4$ and concludes that if this process is iterated, then every modulus greater than 3 eventually terminates at a fixed point.

Mathematics Subject Classifications. 11B39, 11B50
Keywords. Fibonacci sequence, Pisano period, fixed points

The results of this paper were presented at the 21^st International Fibonacci Conference, hosted at Harvey Mudd College, July 8, 2024.

1. Introduction

Perhaps the most popular sequence of all, the Fibonacci sequence is a binary recurrence defined by $F_{0}=0$ , $F_{1}=1$ , and $F_{n}=F_{n-1}+F_{n-2}$ and has been studied so thoroughly that discovering new properties at all is almost as surprising as the property discovered. The focus of this paper is a particular property that was first recognized in 1877 by Lagrange [10]: the terms in the Fibonacci sequence modulo $10$ (i.e. the one’s place digits) repeat every $60$ terms. Inquiry regarding the periodicity of the sequence modulo a positive integer has continued and in 2003 it was proven by Everest, Shparlinski, and Ward [4] that every binary recurrence sequence is periodic modulo a positive integer $m>1$ .

Define the Pisano period as the length of one (shortest) period of the Fibonacci sequence modulo $m$ . The Pisano period is denoted $\pi(m)$ and can be recursively applied: denote $\pi(\pi(m))~{}=~{}\pi^{2}(m)$ and $\pi(\pi^{i}(m))=\pi^{i+1}(m)$ for $n>2$ . The trajectory of an integer $m$ is the set of integers given by recursively applying the Pisano period to $m$ . How long can the trajectory of a starting integer $m$ be?

A fixed point is a positive integer $m$ such that $\pi(m)=m$ . A $k$ -periodic point is a $k$ -tuple of positive integers such that $\pi(m)=\pi^{2}(m)=\ldots=\pi^{k}(m)=m$ . In 1969, Fulton and Morris [6] determined the fixed points of the Fibonacci sequence and proved that the trajectory of every integer will eventually terminate at a fixed point. In 2020, Trojovská [14] showed that there are no $k$ -periodic points in the Fibonacci sequence.

Theorem 1.1 (Fixed Point Theorem, Fulton and Morris [6]).

For and integer $m>1$ , $\pi(m)=m$ if and only if $m=24\times 5^{k-1}$ .

Theorem 1.2.

(Iteration Theorem, Fulton and Morris [6]) For every integer $m>1$ , there exists a least integer $j$ such that $\pi^{j+1}(m)=\pi^{j}(m)$ .

Example.

Trajectories of the integers in the Fibonacci sequence for $m\leq 24$ .

	$\displaystyle\pi(2)=3\rightarrow\pi(3)=8\rightarrow\pi(8)=12\rightarrow\pi(12)=24\qquad$	$\displaystyle\pi(13)=28\rightarrow\pi(28)=48\rightarrow\pi(48)=24$
	$\displaystyle\pi(3)=8\rightarrow\pi(8)=12\rightarrow\pi(12)=24\qquad$	$\displaystyle\pi(14)=48\rightarrow\pi(48)=24$
	$\displaystyle\pi(4)=6\rightarrow\pi(6)=24\qquad$	$\displaystyle\pi(15)=40\rightarrow\pi(40)=60\rightarrow\pi(60)=120$
	$\displaystyle\pi(5)=20\rightarrow\pi(20)=60\rightarrow\pi(60)=120\qquad$	$\displaystyle\pi(16)=24$
	$\displaystyle\pi(6)=24\qquad$	$\displaystyle\pi(17)=36\rightarrow\pi(36)=24$
	$\displaystyle\pi(7)=16\rightarrow\pi(16)=24\qquad$	$\displaystyle\pi(18)=24$
	$\displaystyle\pi(8)=12\rightarrow\pi(12)=24\qquad$	$\displaystyle\pi(19)=18\rightarrow\pi(18)=24$
	$\displaystyle\pi(9)=24\qquad$	$\displaystyle\pi(20)=60\rightarrow\pi(60)=120$
	$\displaystyle\pi(10)=60\rightarrow\pi(60)=120\qquad$	$\displaystyle\pi(21)=16\rightarrow\pi(16)=24$
	$\displaystyle\pi(11)=10\rightarrow\pi(10)=60\rightarrow\pi(60)=120\qquad$	$\displaystyle\pi(22)=30\rightarrow\pi(30)=120$
	$\displaystyle\pi(12)=24\qquad$	$\displaystyle\pi(23)=48\rightarrow\pi(48)=24$
		$\displaystyle\pi(24)=24$

Let $\mathcal{T}(m)$ denote the number of iterations of the Pisano period of $m$ until the trajectory reaches a fixed point. For example, $\mathcal{T}(2)=4$ and $\mathcal{T}(24)=0$ .

Theorem 1.3.

$\limsup\frac{\mathcal{T}(m)}{\log m}<\infty$ .

Closely related are $K$ -Fibonacci sequences defined by $F_{K,0}=0$ , $F_{K,1}=1$ , and $F_{K,n}=KF_{n-1}+F_{n-2}$ . The Pisano period of these sequences is commonly denoted $\pi_{K}(m)$ . What are the fixed points of $K$ -Fibonacci sequences? Some fixed points have already been calculated:

Theorem 1.4 (Falcon and Plaza [5]).

If $K\geq 2$ is even, then $\pi_{K}(2K)=4$ . If $K\geq 3$ is odd, then $\pi_{K}(2K)=6$ .

It follows that if $K=2$ , then $\pi_{K}(4)=4$ and if $K=3$ , then $\pi_{K}(6)=6$ . The main result of this paper extends the results of Fulton & Morris [6], establishing that for each $K$ , fixed points may be classified according to one of four categories of $K$ . Essentially, for every $K$ the trajectory of every $m>1$ terminates at a fixed point (or is a $k$ -periodic point).

Theorem 1.5 ( $K$ -Fixed Point Theorem).

Let $p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{t}^{e_{t}}$ be the prime factorization of $K^{2}+4$ for a positive integer $K\geq 1$ , then for every modulus $m>1$ and for $j_{i}=0,1,2,\ldots$ , $\pi_{K}(m)=m$ if and only if:

(romanenumi)

$K\equiv\pm 1\pmod{6}$ and $m=24\times p_{1}^{j_{1}}p_{2}^{j_{2}}\cdots p_{t}^{j_{t}}$ .
(romanenumi)

$K\equiv 2\pmod{4}$ and $m=2^{j_{1}}$ or $m=2^{j_{1}+1}p_{2}^{j_{2}}\cdots p_{t}^{j_{t}}$ where $p_{1}=2$ .
(romanenumi)

$K\equiv 3\pmod{6}$ and $m=6$ or $m=12\times p_{3}^{j_{3}}p_{4}^{j_{4}}\cdots p_{t}^{j_{t}}$ .
(romanenumi)

$K\equiv 0\pmod{4}$ and $m=2$ or $m=4\times p_{2}^{j_{2}+1}p_{3}^{j_{3}+1}\cdots p_{t}^{j_{t}+1}$ where $p_{1}^{e_{1}}=2^{2}$ .

with the only exception when $K\equiv 3\pmod{6}$ , which has the $2$ -periodic points $\pi_{K}(2)=3$ and $\pi_{K}(3)=2$ .

Theorem 1.6 ( $K$ -Iteration Theorem).

For every $m>1$ , there exists a positive integer $N$ such that $\pi_{K}^{N}(m)=m$ , with the only exception when $K\equiv 3\pmod{6}$ , which has the $2$ -periodic points $\pi(2)=3$ and $\pi(3)=2$ .

Note that every positive integer $K\geq 1$ belongs to exactly one of the four categories in Theorem 1.5. Perhaps it is surprising that the prime factors of $K^{2}+4$ are important in finding fixed points. Famously, the limit of the ratio between successive Fibonacci numbers is the number $\phi$ where Binet’s formula gives the $n$ ^th Fibonacci number:

F_{n}=\frac{\phi^{n}-\phi^{-n}}{\sqrt{5}}\qquad\text{where}\ \qquad\phi=\frac{1+\sqrt{5}}{2}.

Something analogous occurs for $K$ -Fibonacci sequences (see [5, 11]). Note the similarity when $K=1$ :

F_{K,n}=\frac{\sigma^{n}-\sigma^{-n}}{\sqrt{K^{2}+4}}\qquad\text{where}\ \qquad\sigma=\frac{K+\sqrt{K^{2}+4}}{2}.

$K$ $K^{2}+4$ $K\equiv\pm 1\pmod{6}$ $K\equiv 2\pmod{4}$ $K\equiv 3\pmod{6}$ $K\equiv 0\pmod{4}$ $K=1$ 5 $24\times 5^{j_{1}}$ $K=2$ $2^{3}$ $2^{j_{1}}$ $K=3$ $13$ $6$ or $12\times 13^{j_{1}}$ $K=4$ $2^{2}\cdot 5$ $2$ or $4\times 5^{j_{1}+1}$ $K=5$ 29 $24\times 29^{j_{1}}$ $K=6$ $2^{3}\cdot 5$ $2^{j_{1}}$ or $2^{j_{1}+1}\times 5^{j_{2}}$ $K=7$ $53$ $24\times 53^{j_{1}}$ $K=8$ $2^{2}\cdot 17$ $2$ or $4\times 17^{j_{1}+1}$ $K=9$ $5\cdot 17$ $6$ or $12\times 5^{j_{1}}\times 17^{j_{2}}$ $K=10$ $2^{3}\cdot 13$ $2^{j_{1}}$ or $2^{j_{1}+1}\times 13^{j_{2}}$ $K=11$ $5^{3}$ $24\times 5^{j_{1}}$ $K=12$ $2^{2}\cdot 37$ $2$ or $4\times 37^{j_{1}+1}$ $K=13$ $173$ $24\times 173^{j_{1}}$ $K=14$ $2^{3}\cdot 5^{3}$ $2^{j_{1}}$ or $2^{j_{1}+1}\times 5^{j_{2}}$ $K=15$ $229$ $6$ or $12\times 229^{j_{1}}$ $K=16$ $2^{2}\cdot 5\cdot 13$ $2$ or $4\times 5^{j_{1}+1}\times 13^{j_{2}+1}$ $K=17$ $293$ $24\times 293^{j_{1}}$ $K=18$ $2^{3}\cdot 41$ $2^{j_{1}}$ or $2^{j_{1}+1}\times 41^{j_{2}}$ $K=19$ $5\cdot 73$ $24\times 5^{j_{1}}\times 73^{j_{2}}$ $K=20$ $2^{2}\cdot 101$ $2$ or $4\times 101^{j_{1}+1}$ $K=21$ $5\cdot 89$ $6$ or $12\times 5^{j_{1}}\times 89^{j_{2}}$ $K=22$ $2^{3}\cdot 61$ $2^{j_{1}}$ or $2^{j_{1}+1}\times 61^{j_{2}}$ $K=23$ $13\cdot 41$ $24\times 13^{j_{1}}\times 41^{j_{2}}$ $K=24$ $2^{2}\cdot 5\cdot 29$ $2$ or $4\times 5^{j_{1}+1}\times 29^{j_{2}+1}$

Table 1. Fixed points of

(K,1,0,1)

-sequences for

k=1,2,\ldots,24

and

j_{i}=0,1,2,\ldots

2. Preliminaries

Used in the proof of Theorems 1.5 and 1.6 are select results for $K$ -Fibonacci sequences. Renault [11] generalizes a result of Wall [15] and establishes a particular type of multiplicativity for $\pi_{K}(m)$ among the prime factors of $m$ .

Theorem 2.1 (Renault [11]).

Let $m=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{r}^{e_{r}}$ be the prime factorization of $m$ , then

\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(p_{1}^{e_{1}}),\pi_{K}(p_{2}^{e_{2}}),\ldots,\pi_{K}(p_{r}^{e_{r}})\right].

Another result generalized by Renault [11] concerns Wall-Sun-Sun primes - conjectured primes $p$ where $\pi(p)=\pi(p^{2})$ . For the Fibonacci sequence, these primes were originally investigated by Wall [15] in 1960 but became exceedingly popular in the 1990s when Sun & Sun [13] demonstrated that the first case of Fermat’s Last Theorem is false for an exponent $p$ only if $p$ is a Wall-Sun-Sun prime. No Wall-Sun-Sun prime has been found, though infinitely many are conjectured to exist. For $K$ -Fibonacci sequences, any prime $p$ such that $\pi_{K}(p)=\pi_{K}(p^{2})$ is a $K$ -Wall-Sun-Sun prime. These are much more common: if $K=2$ , then $\pi_{2}(13)=\pi_{2}(169)$ and $\pi_{2}(31)=\pi_{2}(961)$ .

Theorem 2.2 (Renault [11]).

For all $K$ and all primes $p$ , there exists a maximal $e$ such that $\pi_{K}(p^{e})=\pi_{K}(p)$ . For all $x\geq e\geq 1$ , $\pi_{K}(p^{x})=p^{x-e}\cdot\pi_{K}(p)$ .

Theorem 2.3 (Renault [11]).

If $\pi_{K}(p^{e})\neq\pi_{K}(p^{e+1})$ , then $\pi_{K}(p^{e+1})\neq\pi_{K}(p^{e+2})$ .

For $K$ -Fibonacci sequences, Bouazzaoui [2, 3] showed that a prime $p$ that does not divide $K^{2}+4$ is a $K$ -Wall-Sun-Sun prime if and only if $\mathbb{Q}\left(\sqrt{K^{2}+4}\right)$ is not $p$ -rational. Results from Harrington & Jones [7, 8, 9] establish necessary and sufficient conditions for precisely which primes that do divide $K^{2}+4$ are $K$ -Wall-Sun-Sun primes. In particular, Harrington & Jones establish that no odd prime divisor of $K^{2}+4$ is ever a $K$ -Wall-Sun-Sun prime.

Theorem 2.4 (Harrington & Jones [7]).

Let $p$ be a prime divisor of $K^{2}+4$ . Then $p$ is a $K$ -Wall-Sun-Sun prime if and only if $p=2$ and $K\equiv 0\pmod{4}$ .

In [1] the authors proved explicit formulas for $\pi_{K}(2^{e})$ , which depend upon the parity of $K$ :

Theorem 2.5 ([1], Theorems 4.25 and 4.28).

Let $K$ be an integer and let $e\geq 1$ , then:

•

If $K$ is odd, then $\pi_{K}(2^{e})=3\cdot 2^{e-1}$ .
•

If $K$ is even, then $\pi_{K}(2^{e})=2^{e+1-\nu_{2}(\gcd(K,2^{e}))}$ where $\nu_{2}(x)$ is the 2-adic valuation.

In an effort to characterize the behavior of $\pi_{K}(p)$ for a prime $p$ , Renault [11] develops a trichotomy depending on the quadratic residues of $K^{2}+4$ modulo $p$ .

Theorem 2.6 (Renault [11]).

Let $p$ be an odd prime.

•

If $K^{2}+4$ is a nonzero quadratic residue modulo $p$ , then $\pi_{K}(p)\mid(p-1)$ .
•

If $K^{2}+4$ is a quadratic non-residue modulo $p$ , then $\pi_{K}(p)\mid 2(p+1)$ .
•

If $p\mid(K^{2}+4)$ , then $\pi_{K}(p)=p\cdot\text{ord}_{p}(2^{-1}K)$ .

In light of Theorem 2.6, it is possible to completely determine $\pi_{K}(p)$ for primes that divide $K^{2}+4$ .

Theorem 2.7.

If $p$ is an odd prime and $p\mid(K^{2}+4)$ , then, $\text{ord}_{p}(2^{-1}K)=4$ and $\pi_{K}(p)=4p$ .

Proof.

Notice that $K^{4}=(K^{2}+4)(K^{2}-4)+16$ , hence $K^{4}\equiv 16\pmod{K^{2}+4}$ . It follows that $(2^{-1}K)^{4}=\frac{K^{4}}{16}\equiv 1\pmod{K^{2}+4}$ . Similarly, if a prime $p\mid(K^{2}+4)$ , then $(2^{-1}K)^{4}\equiv 1\pmod{p}$ . Thus, $\text{ord}_{p}(2^{-1}K)\mid 4$ . Notice that $K^{2}\equiv-4\pmod{K^{2}+4}$ . It follows that $(2^{-1}K)^{2}=\frac{K^{2}}{4}\equiv-1\pmod{K^{2}+4}$ . Hence $(2^{-1}K)^{2}\equiv-1\pmod{p}$ for all $p\mid(K^{2}+4)$ . The condition that $(2^{-1}K)^{2}\equiv-1\equiv 1\pmod{p}$ is equivalent to the condition that $p=2$ , contradicting the assumption that $p$ is an odd prime. Thus, if $p\neq 2$ , then $\text{ord}_{p}(2^{-1}K)=4$ . ∎

Harrington & Jones [7] discovered the value of $\pi_{K}(2)$ when $K$ is an even integer.

Theorem 2.8 (Renault [11] and Harrington & Jones [7]).

If $K$ is even, (i.e. if $2\mid(K^{2}+4)$ ), then $\pi_{K}(2)=2$ .

For the proof of the main result, it is important to also understand the nature of $\pi_{K}(2)$ when $K$ is odd.

Theorem 2.9 (Renault [11]).

If $K$ is odd, then $\pi_{K}(2)=3$ .

Theorem 2.10.

If $3\mid K$ , then $\pi_{K}(3)=2$ . Otherwise, $\pi_{K}(3)=8$ .

Proof.

Consider the $K$ -Fibonacci sequence modulo $3$ . If $3\mid K$ , the sequence becomes $0,1,\circlearrowleft$ , with a period of $2$ . If $K\equiv 1\pmod{3}$ , the sequence is $0,1,1,2,0,2,2,1,0,1,\circlearrowleft$ with a period of $8$ . If $K\equiv 2\pmod{3}$ , the sequence is $0,1,2,2,0,2,1,1,0,1,\circlearrowleft$ again with a period of $8$ . ∎

Theorem 2.11.

For all odd primes $p$ , if $q$ is a prime such that $q\mid\pi_{K}(p)$ , then $q\leq p$ , with equality only if $p\mid(K^{2}+4)$ .

Proof.

If $K^{2}+4$ is a nonzero quadratic residue modulo $p$ , then $q\mid(p-1)$ and $q<p$ . If $K^{2}+4$ is a quadratic non-residue, then $q\mid 2(p+1)$ . Since $p$ is an odd prime, $p+1$ is composite, and is therefore composed of prime factors smaller than $p$ . Finally, if $p\mid(K^{2}+4)$ , then by Theorem 2.6 $\pi_{K}(p)=p\cdot\text{ord}_{p}(2^{-1}K)$ . It is clear that $p\mid\pi_{K}(p)$ . Since the integers modulo $p$ form a cyclic group of order at most $p-1$ , it follows that $\text{ord}_{p}(2^{-1}K)\mid(p-1)$ . Hence, $q\leq p$ . ∎

3. Proof of the K-Fixed Point Theorem

Theorem 3.1.

If $K\equiv\pm 1\pmod{6}$ and $m=24\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ , then $\pi_{K}(m)=m$ .

Proof.

Suppose $K\equiv\pm 1\pmod{6}$ and $m=24\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . By Theorem 2.1,

\displaystyle\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(2^{3}),\pi_{K}(3),\pi_{K}(p_{1}^{j_{1}}),\ldots,\pi_{K}(p_{r}^{j_{r}})\right]

(1)

By Theorem 2.4, neither $2$ , $3$ , nor any $p_{i}$ is a $K$ -Wall-Sun-Sun prime. By Theorems 2.2 and 2.9, $\pi_{K}(2^{3})=2^{3-1}\pi_{K}(2)=2^{2}\cdot 3=12$ . By Theorem 2.10, $\pi_{K}(3)=8$ . By Theorem 2.2, $\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})$ for $i=1,2,\ldots r$ . By Theorem 2.6, $\pi_{K}(p_{i})=p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)$ and by Theorem 2.7, $\text{ord}_{p_{i}}(2^{-1}K)=4$ since $p_{i}$ is odd and divides $K^{2}+4$ . It follows that

\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})=p_{i}^{j_{i}-1}\cdot p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)=4p_{i}^{j_{i}}

These may be substituted into equation (1) to obtain:

\pi_{K}(m)=\operatorname{lcm}\left[12,8,4p_{1},\ldots,4p_{r}\right]=24\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}=m.

∎

Theorem 3.2.

If $K\equiv\pm 1\pmod{6}$ and $\pi_{K}(m)=m$ , then $m=24\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ .

Proof.

Suppose $K\equiv\pm 1\pmod{6}$ and $\pi_{K}(m)=m$ . Let $m=2^{j_{1}}\cdot 3^{j_{2}}\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}\cdot q_{1}^{\theta_{1}}\cdots q_{s}^{\theta_{s}}$ where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . Note that if $\theta_{\lambda}\neq 0$ then $q_{\lambda}\mid m$ . By Theorem 2.1,

\displaystyle m=\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(2^{j_{1}}),\pi_{K}(3^{j_{2}}),\pi_{K}(p_{1}^{j_{1}}),\ldots,\pi_{K}(p_{r}^{j_{r}}),\pi_{K}(q_{1}^{\theta_{1}}),\ldots,\pi_{K}(q_{s}^{\theta_{s}})\right]

(2)

By Theorem 2.11, if $\rho\mid\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ , then $\rho<q_{\lambda}$ for all $1\leq i\leq s$ . By Theorem 2.2, $\pi_{K}(q_{\lambda}^{\theta_{\lambda}})=q_{\lambda}^{\theta_{\lambda}-1}\pi_{K}(q_{\lambda})$ and by Theorem 2.6, $\pi_{K}(q_{\lambda})\mid(q_{\lambda}-1)$ if $K^{2}+4$ is a quadratic residue, or $\pi_{K}(q_{\lambda})\mid 2(q_{\lambda}+1)$ if $K^{2}+4$ is not a quadratic residue modulo $q_{\lambda}$ . Either way, it follows that $q_{\lambda}\not\mid\pi_{K}(q_{\lambda})$ and $q_{\lambda}^{\theta_{\lambda}-1}$ is the largest factor of $q_{\lambda}$ that divides $\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ , that is, $q_{\lambda}^{\theta_{\lambda}-1}\mid\mid\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ .

By Theorem 2.4, neither $2$ , $3$ , $p_{i}$ , nor $q_{\lambda}$ are $K$ -Wall-Sun-Sun primes. By Theorems 2.2 and 2.9, $\pi_{K}(2^{j_{1}})=2^{j_{1}-1}\pi_{K}(2)=2^{j_{1}-1}\cdot 3$ . By Theorems 2.2 and 2.10, $\pi_{K}(3^{j_{2}})=3^{j_{2}-1}\pi_{K}(3)=3^{j_{2}-1}\cdot 8$ . By Theorem 2.2, $\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})$ for $i=1,2,\ldots r$ . By Theorem 2.6, $\pi_{K}(p_{i})=p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)$ and by Theorem 2.7, $\text{ord}_{p_{i}}(2^{-1}K)=4$ since $p_{i}$ is odd and divides $K^{2}+4$ . It follows that

\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})=p_{i}^{j_{i}-1}\cdot p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)=4p_{i}^{j_{i}}

Note that $q_{\lambda}\not\mid\pi_{K}(2^{j_{1}})=2^{j_{1}-1}\cdot 3$ and $q_{\lambda}\not\mid\pi_{K}(3^{j_{2}})=3^{j_{2}-1}\cdot 2$ , and $q_{\lambda}\not\mid\pi_{K}(p_{i}^{j_{i}})=4p_{i}^{j_{i}}$ . Thus, $q_{\lambda}^{\theta_{\lambda}-1}\mid\mid m$ . But this implies that $q_{\lambda}^{\theta_{\lambda}}\not\mid m$ , which is a contradiction. Equation (7) is reduced to:

\displaystyle m=\pi_{K}(m)=\operatorname{lcm}\left[2^{j_{1}-1}\cdot 3,3^{j_{2}-1}\cdot 8,4p_{1}^{j_{1}},\ldots,4p_{r}^{j_{r}}\right]

(3)

Recall that by hypothesis, $m=2^{j_{1}}\cdot 3^{j_{2}}\cdot p_{3}^{j_{3}}\cdots p_{r}^{j_{r}}\cdot q_{1}^{\theta_{1}}\cdots q_{s}^{\theta_{s}}$ . Suppose $j_{1}\geq 4$ , then $2^{j_{1}-1}$ is the largest power of $2$ in (3), implying $2^{j_{1}-1}\mid\mid m$ . However, this contradicts the hypothesis $2^{j_{1}}\mid m$ . Suppose $j_{2}\geq 2$ , then $3^{j_{2}-1}$ is the largest power of $3$ in (2), implying $3^{j_{2}-1}\mid\mid m$ . However, this contradicts the hypothesis $3^{j_{2}}\mid m$ . Thus, $j_{2}=1$ , and equation (3) is reduced to:

m=\pi_{k}(m)=\operatorname{lcm}\left[2^{j_{1}-1}\cdot 3,24,4p_{1}^{j_{1}},\ldots,4p_{r}^{j_{r}}\right]=24\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}

where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . ∎

Theorem 3.3.

If $K\equiv 2\pmod{4}$ and $m=2^{j_{1}}$ or $m=2^{j_{1}+1}p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}=2$ , then $\pi_{K}(m)=m$ .

Proof.

Suppose $K\equiv 2\pmod{4}$ and let $m=2^{j_{1}}$ . By Theorem 2.4, neither $2$ nor any $p_{i}$ is a $K$ -Wall-Sun-Sun prime. By Theorem 2.5, $\pi_{K}(2^{j_{1}})=2^{j_{1}+1-\min(1,j_{1})}=2^{j_{1}}$ .

Suppose $m=2^{j_{1}+1}\cdot p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . By Theorem 2.1,

\displaystyle\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(2^{j_{1}+1}),\pi_{K}(p_{2}^{j_{2}}),\ldots,\pi_{K}(p_{r}^{j_{r}})\right]

(4)

By Theorem 2.4, neither $2$ nor any $p_{i}$ is a $K$ -Wall-Sun-Sun prime. By Theorem 2.5, $\pi_{K}(2^{j_{1}+1})=2^{j_{1}+1}$ . By Theorem 2.6, $\pi_{K}(p_{i})=p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)$ and by Theorem 2.7, $\text{ord}_{p_{i}}(2^{-1}K)=4$ since $p_{i}$ is odd and divides $K^{2}+4$ . It follows that

\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})=p_{i}^{j_{i}-1}\cdot p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)=4p_{i}^{j_{i}}

These may be substituted into equation (4) to obtain:

\pi(m)=\operatorname{lcm}\left[2^{j_{1}+1},4p_{2}^{j_{2}},\ldots,4p_{r}^{j_{r}}\right]=2^{j_{1}+1}\cdot p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}=m.

∎

Theorem 3.4.

If $K\equiv 2\pmod{4}$ and $\pi_{K}(m)=m$ , then $m=2^{j_{1}+1}$ or $m=2^{j_{1}+2}p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}=2$ .

Proof.

Suppose $K\equiv 2\pmod{4}$ and $\pi_{K}(m)=m$ . Let $m=2^{j_{1}}\cdot p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}\cdot q_{1}^{\theta_{1}}\cdots q_{s}^{\theta_{s}}$ where $p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}=2$ . Note that if $\theta_{\lambda}\neq 0$ then $q_{\lambda}\mid m$ . By Theorem 2.1,

\displaystyle m=\pi(m)=\operatorname{lcm}\left[\pi_{K}(2^{j_{1}}),\pi_{K}(p_{2}^{j_{2}}),\ldots,\pi_{K}(p_{r}^{j_{r}}),\pi_{K}(q_{1}^{\theta_{1}}),\ldots,\pi_{K}(q_{s}^{\theta_{s}})\right]

(5)

By Theorem 2.11, if $\rho\mid\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ , then $\rho<q_{\lambda}$ for all $1\leq i\leq s$ . By Theorem 2.2, $\pi_{K}(q_{\lambda}^{\theta_{\lambda}})=q_{\lambda}^{\theta_{\lambda}-1}\pi_{K}(q_{\lambda})$ and by 2.6, $\pi_{K}(q_{\lambda})\mid(q_{\lambda}-1)$ if $K^{2}+4$ is a quadratic residue and $\pi_{K}(q_{\lambda})\mid 2(q_{\lambda}+1)$ if $K^{2}+4$ is not a quadratic residue modulo $q_{\lambda}$ . Either way, it follows that $q_{\lambda}^{\theta_{\lambda}-1}$ is the largest factor of $q_{\lambda}$ that divides $\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ , that is, $q_{\lambda}^{\theta_{\lambda}-1}\mid\mid\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ .

By Theorem 2.4, neither $2$ , $p_{i}$ , nor $q_{\lambda}$ are $K$ -Wall-Sun-Sun primes. By Theorems 2.2 and 2.8, $\pi_{K}(2^{j_{1}})=2^{j_{1}-1}\pi_{K}(2)=2^{j_{1}-1}\cdot 2=2^{j_{1}}$ . By Theorem 2.2, $\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})$ for $i=1,2,\ldots r$ . By Theorem 2.6, $\pi_{K}(p_{i})=p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)$ and by Theorem 2.7, $\text{ord}_{p_{i}}(2^{-1}K)=4$ since $p_{i}$ is odd and divides $K^{2}+4$ . It follows that

\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})=p_{i}^{j_{i}-1}\cdot p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)=4p_{i}^{j_{i}}

Note that $q_{\lambda}\not\mid\pi_{K}(2^{j_{1}})=2^{j_{1}}$ and $q_{\lambda}\not\mid\pi_{K}(3^{j_{2}})=3^{j_{2}-1}\cdot 8$ , and $q_{\lambda}\not\mid\pi_{K}(p_{i}^{j_{i}})=4p_{i}^{j_{i}}$ . Thus, $q_{\lambda}^{\theta_{\lambda}-1}\mid\mid m$ . But this implies that $q_{\lambda}^{\theta_{\lambda}}\not\mid m$ , which is a contradiction. Equation (5) is reduced to:

m=\pi_{K}(m)=\operatorname{lcm}\left[2^{j_{1}},4p_{3}^{j_{3}},\ldots,4p_{r}^{j_{r}}\right]=2^{j_{1}}\ \text{or}\ 2^{j_{1}+1}p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}

where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}=2$ . ∎

Theorem 3.5.

If $K\equiv 3\pmod{6}$ and $m=6$ or $m=12\cdot p_{3}^{j_{3}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}^{a_{1}}=2^{2}$ and $p_{2}^{a_{2}}=3$ , then $\pi_{K}(m)=m$ .

Proof.

Suppose $K\equiv 3\pmod{6}$ and $m=6$ . Then by Theorem 2.1, $\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(2),\pi_{K}(3)\right]$ . By Theorem 2.9, $\pi_{K}(2)=3$ . By Theorem 2.10, $\pi_{K}(3)=2$ . Hence, $\pi_{K}(6)=\operatorname{lcm}\left[3,2\right]=6$ . Note, this also establishes the $2$ -periodic point $\pi_{K}(2)=3\rightarrow\pi_{K}(3)=2\circlearrowleft$ .

Suppose $m=12\cdot p_{3}^{j_{3}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}^{a_{1}}=2^{2}$ and $p_{2}^{a_{2}}=3$ . By Theorem 2.4, neither $2$ , $3$ , nor any $p_{i}$ is a $K$ -Wall-Sun-Sun prime. By Theorem 2.1,

\displaystyle\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(2^{2}),\pi_{K}(3),\pi_{K}(p_{3}^{j_{3}}),\ldots,\pi_{K}(p_{r}^{j_{r})}\right]

(6)

By Theorem 2.5, $\pi_{K}(2^{2})=2\cdot 3=6$ . By Theorem 2.10, $\pi_{K}(3)=2$ . By Theorem 2.2, $\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})$ for $i=1,2,\ldots r$ . By Theorem 2.6, $\pi_{K}(p_{i})=p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)$ and by Theorem 2.7, $\text{ord}_{p_{i}}(2^{-1}K)=4$ since $p_{i}$ is odd and divides $K^{2}+4$ . It follows that

\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})=p_{i}^{j_{i}-1}\cdot p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)=4p_{i}^{j_{i}}

These may be substituted into equation (6) to obtain:

\pi_{K}(m)=\operatorname{lcm}\left[6,2,4p_{3},\ldots,4p_{r}\right]=12\cdot p_{3}^{j_{3}}\cdots p_{r}^{j_{r}}=m.

∎

Theorem 3.6.

If $K\equiv 3\pmod{6}$ and $\pi_{K}(m)=m$ , then $m=6$ or $m=12\cdot p_{3}^{j_{3}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}^{a_{1}}=2^{2}$ and $p_{2}^{a_{2}}=3$ .

Proof.

Suppose $K\equiv 3\pmod{6}$ and $\pi_{K}(m)=m$ . Let $m=2^{j_{1}}\cdot 3^{j_{2}}\cdot p_{3}^{j_{3}}\cdots p_{r}^{j_{r}}\cdot q_{1}^{\theta_{1}}\cdots q_{s}^{\theta_{s}}$ where $2^{2}\cdot 3\cdot p_{3}^{j_{3}}\cdots p_{r}^{j_{r}}$ is the prime factorization of $K^{2}+4$ . Note that if $\theta_{\lambda}\neq 0$ then $q_{\lambda}\mid m$ . By Theorem 2.1,

\displaystyle m=\pi(m)=\operatorname{lcm}\left[\pi_{K}(2^{j_{1}})\,\pi_{K}(3^{j_{2}})\,\pi_{K}(p_{3}^{j_{3}}),\ldots,\pi_{K}(p_{r}^{j_{r}}),\pi_{K}(q_{1}^{\theta_{1}}),\ldots,\pi_{K}(q_{s}^{\theta_{s}})\right]

(7)

By Theorem 2.11, if $\rho\mid\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ , then $\rho<q_{\lambda}$ for all $1\leq i\leq s$ . By Theorem 2.2, $\pi_{K}(q_{\lambda}^{\theta_{\lambda}})=q_{\lambda}^{\theta_{\lambda}-1}\pi_{K}(q_{\lambda})$ and by 2.6, $\pi_{K}(q_{\lambda})\mid(q_{\lambda}-1)$ if $K^{2}+4$ is a quadratic residue and $\pi_{K}(q_{\lambda})\mid 2(q_{\lambda}+1)$ if $K^{2}+4$ is not a quadratic residue modulo $q_{\lambda}$ . Either way, it follows that $q_{\lambda}^{\theta_{\lambda}-1}$ is the largest factor of $q_{\lambda}$ that divides $\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ , that is, $q_{\lambda}^{\theta_{\lambda}-1}\mid\mid\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ .

By Theorem 2.4, neither $2$ , $3$ , $p_{i}$ , nor $q_{\lambda}$ are $K$ -Wall-Sun-Sun primes. By Theorem 2.5, $\pi_{K}(2^{j_{1}})=2^{j_{1}-1}\cdot 3$ . By Theorems 2.2 and 2.10, $\pi_{K}(3^{j_{2}})=3^{j_{2}-1}\pi_{K}(3)=3^{j_{2}-1}\cdot 2$ . By Theorem 2.2, $\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})$ for $i=1,2,\ldots r$ . By Theorem 2.6, $\pi_{K}(p_{i})=p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)$ and by Theorem 2.7, $\text{ord}_{p_{i}}(2^{-1}K)=4$ since $p_{i}$ is odd and divides $K^{2}+4$ . It follows that

\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})=p_{i}^{j_{i}-1}\cdot p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)=4p_{i}^{j_{i}}

\displaystyle m=\pi_{K}(m)=\operatorname{lcm}\left[2^{j_{1}-1}\cdot 3,3^{j_{2}-1}\cdot 2,4p_{3}^{j_{3}},\ldots,4p_{r}^{j_{r}}\right]

(8)

Recall that by hypothesis, $m=2^{j_{1}}\cdot 3^{j_{2}}\cdot p_{3}^{j_{3}}\cdots p_{r}^{j_{r}}\cdot q_{1}^{\theta_{1}}\cdots q_{s}^{\theta_{s}}$ . Suppose $j_{1}\geq 3$ , then $2^{j_{1}-1}$ is the largest power of $2$ in (3), implying $2^{j_{1}-1}\mid\mid m$ . However, this contradicts the hypothesis $2^{j_{1}}\mid m$ . Thus, $j_{1}=1$ or $2$ . Suppose $j_{2}\geq 2$ , then $3^{j_{2}-1}$ is the largest power of $3$ in (3), implying $3^{j_{2}-1}\mid\mid m$ . However, this contradicts the hypothesis $3^{j_{2}}\mid m$ . Thus, $j_{2}=1$ , and equation (3) is reduced to:

m=\pi_{k}(m)=\operatorname{lcm}\left[(6\ \text{or}\ 12),6,4p_{3}^{j_{3}},\ldots,4p_{r}^{j_{r}}\right]=12\cdot p_{3}^{j_{3}}\cdots p_{r}^{j_{r}}\ \text{or}\ 6

where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}^{a_{1}}=2^{2}$ and $p_{2}^{a_{2}}=3$ . ∎

Theorem 3.7.

If $K\equiv 0\pmod{4}$ and $m=2$ or $m=4\cdot p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}^{a_{1}}=2^{2}$ , then $\pi_{K}(m)=m$ .

Proof.

Suppose $K\equiv 0\pmod{4}$ and $m=2$ . By Theorem 2.8, $\pi_{K}(2)=2$ . Suppose $m=4\cdot p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}^{j_{1}}=2^{2}$ . By Theorem 2.1,

\displaystyle\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(2^{2}),\pi_{K}(p_{2}^{j_{2}}),\ldots,\pi_{K}(p_{r}^{j_{r}})\right].

(9)

By Theorem 2.4, $2$ is a $K$ -Wall-Sun-Sun prime, so $\pi_{K}(2^{2})=\pi_{K}(2)=2$ . Also by Theorem 2.4, no other $p_{i}$ is a $K$ -Wall-Sun-Sun prime. By Theorem 2.2, $\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})$ for $i=1,2,\ldots r$ . By Theorem 2.6, $\pi_{K}(p_{i})=p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)$ and by Theorem 2.7, $\text{ord}_{p_{i}}(2^{-1}K)=4$ since $p_{i}$ is odd and divides $K^{2}+4$ . It follows that

\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})=p_{i}^{j_{i}-1}\cdot p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)=4p_{i}^{j_{i}}

These may be substituted into equation (9) to obtain:

\pi_{K}(m)=\operatorname{lcm}\left[2,4p_{2},\ldots,4p_{r}\right]=4\cdot p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}=m.

∎

Theorem 3.8.

If $\pi_{K}(m)=m$ and $K\equiv 0\pmod{4}$ , then $m=2$ or $m=4\cdot p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}^{a_{1}}=2^{2}$ .

Proof.

Suppose $K\equiv 0\pmod{4}$ and $\pi_{K}(m)=m$ . Let $m=2^{j_{1}}\cdot 3^{j_{2}}\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}\cdot q_{1}^{\theta_{1}}\cdots q_{s}^{\theta_{s}}$ where $p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ is the prime factorization of $K^{2}+4$ . Note that if $\theta_{\lambda}\neq 0$ then $q_{\lambda}\mid m$ . By Theorem 2.1,

\displaystyle m=\pi(m)=\operatorname{lcm}\left[\pi_{K}(2^{j_{1}})\,\pi_{K}(3^{j_{2}})\,\pi_{K}(p_{1}^{j_{1}}),\ldots,\pi_{K}(p_{r}^{j_{r}}),\pi_{K}(q_{1}^{\theta_{1}}),\ldots,\pi_{K}(q_{s}^{\theta_{s}})\right]

(10)

By Theorem 2.11, if $\rho\mid\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ , then $\rho<q_{\lambda}$ for all $1\leq i\leq s$ . By Theorem 2.2, $\pi_{K}(q_{\lambda}^{\theta_{\lambda}})=q_{\lambda}^{\theta_{\lambda}-1}\pi_{K}(q_{\lambda})$ and by Theorem 2.6, $\pi_{K}(q_{\lambda})\mid(q_{\lambda}-1)$ if $K^{2}+4$ is a quadratic residue, or $\pi_{K}(q_{\lambda})\mid 2(q_{\lambda}+1)$ if $K^{2}+4$ is not a quadratic residue modulo $q_{\lambda}$ . Either way, it follows that $q_{\lambda}^{\theta_{\lambda}-1}$ is the largest factor of $q_{\lambda}$ that divides $\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ , that is, $q_{\lambda}^{\theta_{\lambda}-1}\mid\mid\pi_{K}(q_{\lambda}^{\theta_{\lambda}})$ .

By Theorem 2.4, $2$ is a $K$ -Wall-Sun-Sun prime where $\pi_{K}(2)=\pi_{K}(2^{2})=2$ but neither $3$ , $p_{i}$ , nor $q_{\lambda}$ are $K$ -Wall-Sun-Sun primes. By Theorem 2.5, for $j_{1}\geq 2,\pi_{K}(2^{j_{1}})\mid 2^{j_{1}-1}$ . Specifically, if $a=2^{\nu_{2}(\gcd(K,m))}-1\geq 1$ , then $\pi_{K}(2^{j_{1}})=2^{j_{1}-a}$ . If $j_{1}=1,\pi_{K}(2)=2$ , thus forming a fixed point. By Theorems 2.2 and 2.10, $\pi_{K}(3^{j_{2}})=3^{j_{2}-1}\pi_{K}(3)=3^{j_{2}-1}\cdot 2$ if $3\mid K$ and $\pi_{K}(3^{j_{2}})=3^{j_{2}-1}\pi_{K}(3)=3^{j_{2}-1}\cdot 8$ if $3\not\mid K$ . By Theorem 2.2, $\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-1}\pi_{K}(p_{i})$ for $i=1,2,\ldots r$ . By Theorem 2.6, $\pi_{K}(p_{i})=p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)$ and by Theorem 2.7, $\text{ord}_{p_{i}}(2^{-1}K)=4$ since $p_{i}$ is odd and divides $K^{2}+4$ . It follows that

\pi_{K}(p_{i}^{j_{i}})=p_{i}^{j_{i}-a}\pi_{K}(p_{i})=p_{i}^{j_{i}-1}\cdot p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)=4p_{i}^{j_{i}}

Note that $q_{\lambda}\not\mid\pi_{K}(2^{j_{1}-1})=2^{j_{1}}$ and $q_{\lambda}\not\mid\pi_{K}(3^{j_{2}})=3^{j_{2}-1}\cdot 2\ \text{or}\ 8$ , and $q_{\lambda}\not\mid\pi_{K}(p_{i}^{j_{i}})=4p_{i}^{j_{i}}$ . Thus, $q_{\lambda}^{\theta_{\lambda}-1}\mid\mid m$ . But this implies that $q_{\lambda}^{\theta_{\lambda}}\not\mid m$ , which is a contradiction. Equation (10) is reduced to:

\displaystyle m=\pi_{K}(m)=\operatorname{lcm}\left[2^{j_{1}-a},3^{j_{2}-1}\cdot(2\ \text{or}\ 8),4p_{2}^{j_{1}},\ldots,4p_{r}^{j_{r}}\right]

(11)

Recall that by hypothesis, if $4\mid m$ , then $m=2^{j_{1}-a}\cdot p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}\cdot q_{1}^{\theta_{1}}\cdots q_{s}^{\theta_{s}}$ . Suppose $j_{1}\geq 3$ , then $2^{j_{1}-1}$ is the largest power of $2$ in (3), implying $2^{j_{1}-a}\mid\mid m$ . Because $a\geq 1$ , this contradicts the hypothesis that $2^{j_{1}}\mid m$ . Thus, equation (11) is reduced to:

m=\pi_{k}(m)=\operatorname{lcm}\left[2^{j_{1}-a},4p_{2}^{j_{2}},\ldots,4p_{r}^{j_{r}}\right]=4\cdot p_{2}^{j_{2}}\cdots p_{r}^{j_{r}}

where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ and $p_{1}^{a_{1}}=2^{2}$ . ∎

4. Proof of the K-Iteration Theorem

Theorem 4.1 (Renault [11]).

For all $m>2$ and $K\geq 1$ , $\pi_{K}(m)$ is even.

Theorem 4.2.

If $K$ is odd, then $2$ is not a $K$ -Wall-Sun-Sun prime.

Proof.

Note that by Theorem 2.9 that $\pi_{K}(2)=3$ for odd $K$ . It remains to show that $\pi_{K}(4)\neq 3$ for odd $K$ . If $K\equiv 1\pmod{4}$ , then the $K$ -Fibonacci sequence (modulo 4) becomes 0, 1, 1, 2, 3, 1, 0, 1, $\circlearrowleft$ , with period 6. If $K\equiv 3\pmod{4}$ , then the $K$ -Fibonacci sequence (modulo 4) becomes 0, 1, 3, 2, 1, 1, 0, 1, $\circlearrowleft$ , again with period 6. Hence, $\pi_{K}(2)\neq\pi_{K}(4)$ for all odd $K$ . ∎

Theorem 4.3.

If $p\mid(K^{2}+4)$ , then for all $N$ , $p\mid\pi_{K}^{N}(p^{j})$ .

Proof.

Suppose $p\mid(K^{2}+4)$ . By Theorem 2.4, $p$ is a $K$ -Wall-Sun-Sun prime if and only if $p=2$ and $K\equiv 0\pmod{4}$ . In this case, by Theorem 2.8 $\pi_{K}(2)=\pi_{K}(4)=2$ . Hence, $2\mid\pi_{K}^{N}(p)$ for all $N$ . If $p=2$ and $K\equiv 2\pmod{4}$ , then $\pi_{K}^{N}(p^{j})=2^{j}$ for all $j$ , because this is precisely one family of $K$ -fixed points by Theorem 3.4. On the other hand, suppose that $p$ is an odd prime. By Theorems 2.2 and 2.6, $\pi_{K}(p^{j})=p^{j-1}\pi_{K}(p_{i})=4p$ . Recursively applying the Pisano period yields $\pi_{K}^{2}(p)=\pi_{K}\left(4p\right)=\operatorname{lcm}\left[\pi_{K}(2^{2}),\pi_{K}(p)\right]=\operatorname{lcm}\left[\pi_{K}(2^{2}),4p\right]$ . Iterating the Pisano period always preserves a factor of $p$ by induction. Thus, for all $N$ , $p\mid\pi_{K}^{N}(p)$ . ∎

Theorem 4.4.

If $q\not\mid(K^{2}+4)$ , then there exists a positive integer $N$ such that for all $n\geq N$ , $q\not\mid\pi_{K}^{n}(q^{\theta})$ for any $\theta\geq 1$ .

Proof.

Suppose $q\not\mid(K^{2}+4)$ . By Theorem 2.2, there is a maximal $e$ such that $\pi_{K}(q^{e})=\pi_{K}(q)$ and for $x\geq e\geq 1$ , $\pi_{K}(q^{x})=q^{x-e}\pi_{K}(q)$ . Applying the Pisano period again yields

\displaystyle\pi_{K}^{2}(q^{\theta})

\displaystyle=\pi_{K}\left(q^{x-e}\pi_{K}(q)\right)=\operatorname{lcm}\left[\pi_{K}(q^{x-e}),\pi_{K}^{2}(q)\right]=\operatorname{lcm}\left[q^{x-e-1}\pi_{k}(q),\pi_{K}^{2}(q)\right].

By Theorem 2.6, since $q_{i}\not\mid(K^{2}+4)$ , it follows that $q^{\theta}\not\mid\pi_{K}(q)$ for any positive integer $\theta$ . As the Pisano period is recursively applied, the highest power of $q$ that carries to the next iteration is strictly decreasing. Applying the Pisano period precisely $x-e$ times ensures that the highest power of $q$ that emerges is $q^{x-e-(x-e)}$ . Hence, there exists a positive integer $N$ such that for all $n\geq N$ , $q\not\mid\pi_{K}^{n}(q^{\theta})$ . ∎

Theorem 4.5.

If $K\equiv\pm 1\pmod{6}$ and $m>1$ , then there exists an $N$ such that for all $n\geq N$ , $\pi_{K}^{n}(m)=24\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ .

Proof.

Suppose $K\equiv\pm 1\pmod{6}$ and $m=2^{s_{1}}3^{s_{2}}p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}q_{1}^{\lambda_{t}}\cdots q_{r}^{\lambda_{t}}$ for $s_{i},j_{i}\geq 0$ and $\lambda_{i}\geq 1$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . By Theorem 2.1,

\displaystyle\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(2^{s_{1}}),\pi_{K}(3^{s_{2}}),\pi_{K}(p_{1}^{j_{1}}),\ldots,\pi_{K}(p_{r}^{j_{r}}),\pi_{K}(q_{1}^{\lambda_{1}}),\ldots,\pi_{K}(q_{s}^{\lambda_{2}})\right]

(12)

By Theorem 4.1, $2\mid\pi_{K}(m)$ . By Theorem 2.9, $\pi_{K}(2)=3$ implying that $3\mid\pi_{K}^{2}(m)$ . By Theorem 2.10, $\pi_{K}(3)=8$ , implying that $2^{3}\mid\pi_{K}^{3}(m)$ . By Theorems 2.2 and 2.8, $\pi_{K}(2^{3})=2^{3-1}\pi_{K}(2)=4\cdot 3=12$ , implying $12\mid\pi_{K}^{4}(m)$ . By Theorems 2.1, 2.8, and 2.10, $\pi_{K}(12)=\operatorname{lcm}\left[\pi_{K}(2^{2}),\pi_{K}(3)\right]=\operatorname{lcm}\left[6,8\right]=24$ , implying $24\mid\pi_{K}^{5}(m)$ . By Theorem 4.3, if any $j_{i}\geq 1$ , then the corresponding $p_{i}$ is preserved for all $N$ , and $p_{i}\mid\pi_{K}(m)$ . By Theorem 4.4, for any $q_{i}\not\mid(K^{2}+4)$ , $q_{i}$ vanishes for some sufficiently large $N$ , and $q_{i}\not\mid\pi_{K}(m)$ . Hence, for some $N$ , $\pi_{K}^{n}(m)=24\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . ∎

Theorem 4.6.

If $K\equiv 3\pmod{6}$ and $m>3$ , then there exists an $N$ such that for all $n\geq N$ , $\pi_{K}^{n}(m)=p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . And if $m=2$ or $m=3$ , then $\pi_{K}(2)=3$ and $\pi_{K}(3)=2$ .

Proof.

Suppose $K\equiv 3\pmod{6}$ and $m=p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}q_{1}^{\lambda_{t}}\cdots q_{r}^{\lambda_{t}}>3$ for $j_{i}\geq 0$ and $\lambda_{i}\geq 1$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . By Theorem 2.1,

\displaystyle\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(p_{1}^{j_{1}}),\ldots,\pi_{K}(p_{r}^{j_{r}}),\pi_{K}(q_{1}^{\lambda_{1}}),\ldots,\pi_{K}(q_{s}^{\lambda_{2}})\right]

(13)

By Theorem 4.1, $2\mid\pi_{K}(m)$ . If $\pi_{K}(m)=2$ , then the $K$ -Fibonacci sequence must reduce to $0,1,K\equiv 0\pmod{m},\circlearrowleft$ , so $m\mid K$ . In this case, the iterative Pisano period cycles at the 2-periodic point $\pi(2)=3,\pi(3)=2,\circlearrowleft$ . Otherwise, either $\pi_{K}(m)=2^{\alpha}\cdot\beta$ , where $\alpha\geq 1$ and $\beta$ is an odd number greater than 1, or $\pi_{K}(m)=2^{\gamma}$ , where $\gamma\geq 2$ . By Theorem 2.9, $\pi_{K}(2)=3$ . If $\pi_{K}(m)=2^{\alpha}\cdot\beta$ , then $\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(2^{\alpha}),\pi_{K}(\beta)\right]$ . Since $3\mid\pi_{K}(2^{\alpha})$ and $2\mid\pi_{K}(\beta)$ , $6\mid\pi_{K}^{2}(m)$ . Else, if $\pi_{K}(m)=2^{\gamma}$ , and since 2 is not a $K$ -Wall-Sun-Sun prime by Theorem 4.2, then $\pi_{K}^{2}(m)=3\cdot 2^{\gamma-1}$ , so $6\mid\pi_{K}^{2}(m)$ . By Theorem 4.3, if any $j_{i}\geq 1$ , then the corresponding $p_{i}$ is preserved for all $N$ , and $p_{i}\mid\pi_{K}(m)$ . By Theorem 2.6, $\pi_{K}(p_{i})=p_{i}\cdot\text{ord}_{p_{i}}(2^{-1}K)$ and by Theorem 2.7, $\text{ord}_{p_{i}}(2^{-1}K)=4$ since $p_{i}$ is odd and divides $K^{2}+4$ . By Theorem 4.4, for any $q_{i}\not\mid(K^{2}+4)$ , $q_{i}$ vanishes for some sufficiently large $N$ , and $q_{i}\not\mid\pi_{K}(m)$ . Hence, for some $N$ , $\pi_{K}^{n}(m)=\operatorname{lcm}\left[6,4p_{1}^{j_{1}},\ldots,4p_{r}^{j_{r}}\right]$ . If there is at least one such $p_{i}$ , then $\pi_{K}^{n}(m)=12\cdot p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ ; otherwise, $\pi_{K}^{n}(m)=6$ . Finally, since $K\equiv 3\pmod{6}$ , there is a 2-periodic point: $\pi_{K}(2)=3\rightarrow\pi_{K}(3)=2\circlearrowleft$ . ∎

Theorem 4.7.

If $K\equiv 2\ \text{or}\ 0\pmod{4}$ and $m>1$ , then there exists an $N$ such that for all $n\geq N$ , $\pi_{K}^{n}(m)=p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ for $j_{i}=0,1,2,\ldots$ , where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ .

Proof.

Suppose $K\equiv 2\ \text{or}\ 0\pmod{4}$ and suppose $m=p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}q_{1}^{\lambda_{t}}\cdots q_{t}^{\lambda_{t}}>1$ for $j_{i}\geq 0$ and $\lambda_{i}\geq 1$ (and $m>3$ if $K\equiv 3\pmod{6}$ ), where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . By Theorem 2.1,

\displaystyle\pi_{K}(m)=\operatorname{lcm}\left[\pi_{K}(p_{1}^{j_{1}}),\ldots,\pi_{K}(p_{r}^{j_{r}}),\pi_{K}(q_{1}^{\lambda_{1}}),\ldots,\pi_{K}(q_{s}^{\lambda_{2}})\right]

(14)

By Theorem 4.3, if any $j_{i}\geq 1$ , then the corresponding $p_{i}$ is preserved for all $N$ , and $p_{i}\mid\pi_{K}^{N}(m)$ . By Theorem 4.4, for any $q_{i}\not\mid(K^{2}+4)$ , $q_{i}$ vanishes for some sufficiently large $N$ , and $q_{i}\not\mid\pi_{K}^{N}(m)$ . Hence, there is a positive integer $N$ such that for all $n\geq N$ , $\pi_{K}^{n}(m)=p_{1}^{j_{1}}\cdots p_{r}^{j_{r}}$ where $p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$ is the prime factorization of $K^{2}+4$ . ∎

5. Proof of Theorem 1.3

Let $q$ be an odd prime factor of $m$ that is coprime to all fixed points, and define $S(m)$ by

S(m)=\sum_{q\mid m}=\nu_{q}(m)(\log(q)-\log(3))=\log m-\sum_{q\mid m}\nu_{q}(m)\log(3).

where $\nu_{q}(m)$ is the $q$ -adic valuation of $m$ . By Theorem 2.6, $\pi_{K}(q)\leq 2(q+1)\leq\frac{8}{3}q$ . Since this number is even if $q>2$ , $\pi_{K}(q)$ must have at least two prime factors. For arbitrarily large $q$ ,

S(\pi_{K}(q))\leq\log(q)-2\log(3)=S(q)+\log(8/3)-\log(3)=S(q)+3\log(2)-2\log(3).

Since $\pi_{K}(q^{e})\mid q^{e-1}\pi_{K}(q)$ , $S(\pi_{K}(q^{e}))<S(q^{e})+3\log(2)-2\log(3)$ . Hence $S=0$ is reached in at most $\frac{\log m}{2\log(3)-3\log(2)}$ steps, where one step represents the calculation of the Pisano period for a certain $q_{i}^{e_{i}}$ . While one iteration of the Pisano period always accomplishes at least one step, as any $q_{i}^{e_{i}}$ term may be chosen and separated out by Theorem 2.1, it may accomplish more than one step if multiple $q_{i}$ ’s are present.

Any number $m$ where $S(m)=0$ must be of the form $2^{a}3^{b}\prod_{i=1}^{t}p_{i}^{j_{i}}$ , where $p_{i}\mid K^{2}+4$ for all $i$ as seen in the previous section. Note that by Theorem 2.6, all factors of $p_{i}^{j_{i}}$ remain constant upon iteration of the period, as $\pi_{K}(p_{i}^{j_{i}})=4p_{i}^{j_{i}}$ , and the only factors that vary are powers of $2$ and $3$ . If $m^{\prime}$ is not a multiple of a fixed point, then the Pisano period may be applied recursively to achieve a fixed point. The maximum number of such iterations is 5, when $K\equiv\pm 1\pmod{6}$ .

Now suppose $m^{\prime}$ is a multiple of a fixed point but not a fixed point itself. The only primes $p$ whose $p$ -adic valuations may change on the iteration of the Pisano period when $S=0$ are 2 and 3; hence let $g(m^{\prime})=\nu_{2}(m^{\prime})+\nu_{3}(m^{\prime})$ . Suppose $K\equiv\pm 1\pmod{6}$ . Then, $\nu_{2}(\pi_{K}(2^{a}))=a-1$ , $\nu_{2}(\pi_{K}(3^{b}))=3$ , and $\nu_{2}(\pi_{K}(p_{i}^{e_{i}}))=2$ ; likewise, $\nu_{3}(\pi_{K}(2^{a}))=1$ , $\nu_{3}(\pi_{K}(3^{b}))=b-1$ , and $\nu_{3}(\pi_{K}(p_{i}^{e_{i}}))=0$ . Since $m$ is a multiple of a fixed point, $\nu_{2}(m^{\prime})\geq 3$ and $\nu_{3}(m^{\prime})\geq 1$ , and because $m^{\prime}$ is not a fixed point itself there must be at least one additional factor of either 2 or 3. If $\nu_{2}(m^{\prime})>3$ , then $\nu_{2}(\pi_{K}(m^{\prime}))=\nu_{2}(m^{\prime})-1$ , and if $\nu_{3}(m^{\prime})>1$ , then $\nu_{3}(\pi_{K}(m^{\prime}))=\nu_{3}(m^{\prime})-1$ . Hence $g(m^{\prime})$ decreases by at least 1 until a fixed point is reached, and may not be greater than $\log_{2}m^{\prime}=\frac{\log m}{\log(2)}+\frac{\log m}{2\log(3)-3\log(2)}+5$ . The maximum number of iterations of the Pisano period necessary to reach a fixed point is thus $\frac{\log m}{\log(2)}+\frac{\log m}{2\log(3)-3\log(2)}+1$ .

If $K\equiv 3\pmod{6}$ , then the trajectory of $m^{\prime}$ will end at either the 2-periodic point $(2,3)$ or a fixed point that is a multiple of 12. If $p_{i}\mid m$ for at least one $p_{i}\not\in\{2,3\}$ , then $12\mid\pi_{K}^{N}(m^{\prime})$ for $N\geq 2$ since $\pi_{K}(p_{i})=4p_{i}$ and $3\mid\pi_{K}(4)$ . As above, $\nu_{2}(\pi_{K}(2^{a}))=a-1$ , $\nu_{2}(\pi_{K}(p_{i}^{e_{i}}))=2$ , $\nu_{3}(\pi_{K}(3^{b}))=b-1$ , and $\nu_{3}(\pi_{K}(p_{i}^{e_{i}}))=0$ , but $\nu_{2}(\pi_{K}(3^{b}))=1$ . If the trajectory of $m^{\prime}$ ends at a multiple of 12 and $g(m)>3$ , then $g(m)$ will again decrease by at least 1 until a fixed point is reached, and the maximum number of iterations is $\frac{\log m}{\log(2)}+\frac{\log m}{2\log(3)-3\log(2)}+2$ . Two extra steps may be necessary if the trajectory terminates at the 2-periodic point.

If $K\equiv 2\pmod{4}$ , then any number $m^{\prime}$ with $S=0$ will reach a fixed point after at most one more iteration, since any combination of powers of $2$ and $p_{i}$ ’s is a fixed point.

If $K\equiv 0\pmod{4}$ , then $\pi_{K}(2^{a})\mid 2^{a-1}$ for all $a$ ; hence, the powers of $2$ vanish in at most $\frac{\log m}{\log 2}$ steps, giving $\frac{\log m}{\log(2)}+\frac{\log m}{2\log(3)-3\log(2)}$ total iterations.

Combining these yields an overall upper bound of $\frac{\log m}{\log(2)}+\frac{\log m}{2\log(3)-3\log(2)}+2$ on the number of iterations of the Pisano period required to reach a fixed point; hence

\limsup\frac{\mathcal{T}_{K}(m)}{\log m}\leq\frac{1}{\log 2}+\frac{1}{2\log(3)-3\log(2)}\approx 9.933.

Corollary 5.1.

Let $\mathcal{P}_{K}(m)$ be the fixed point that terminates the trajectory of $m$ ; if $K\equiv 3\pmod{6}$ and $m$ terminates at the 2-periodic point, define $\mathcal{P}_{K}(m)=0$ . Then $\limsup\frac{\log\mathcal{P}_{K}(m)}{\log m}<\infty$ .

Proof.

The first part of the proof of Theorem 1.3 shows that there can be at most $\frac{\log m}{2\log(3)-3\log(2)}$ steps in the reduction to $S=0$ , and by Theorem 2.6,

\frac{\pi_{K}(q_{i}^{e_{i}})}{q_{i}^{e_{i}}}\leq\frac{2q+1}{q}\leq\frac{8}{3},

since the minimum possible $q_{i}$ is 3. If $m^{\prime}=\pi_{K}^{n}(m)$ is such that $S(m^{\prime})=0$ , and $m^{\prime}$ is a multiple of a fixed point, each successive application of the Pisano period reduces $m^{\prime}$ . If $m^{\prime}$ is not a multiple of a fixed point, it is multiplied by no more than 24 until a fixed point is reached. Therefore,

\log\mathcal{P}_{K}(m)\leq(\log(8)-\log(3))\left(\frac{\log m}{2\log(3)-3\log(2)}\right)+\log(24)

and

\limsup\frac{\log\mathcal{P}_{K}(m)}{\log m}\leq\frac{\log(8)-\log(3)}{2\log(3)-3\log(2)}\approx 8.327.

∎

6. Final Thoughts

A general binary recurrence sequence $\mathcal{U}_{n}$ is determined by the four parameters $(a,b,c,d)$ where

\mathcal{U}_{0}=c,\qquad\mathcal{U}_{1}=d,\qquad\mathcal{U}_{n}=a\times\mathcal{U}_{n-1}+b\times\mathcal{U}_{n-2}.

For example, the Fibonacci sequence is determined by $(1,1,0,1)$ , the Lucas sequence by $(1,1,2,1)$ , the Pell sequence by $(2,1,0,1)$ , the Jacobsthal sequence by $(1,2,0,1)$ , etc. When the initial values are $0$ and $1$ , the recurrence is called an $(a,b)$ -Fibonacci sequence. In all of these cases, the binary recurrence sequence is periodic modulo a positive integer $m>1$ [4]. Naturally, the Pisano period has been considered for many binary recurrence sequences. Is it possible to determine the fixed points for general binary recurrence sequences?

Sequence	Pisano Periods for $m=2,3,\ldots,24$
Fibonacci	3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60,16,30,48,24,…
Lucas	3,8,6,4,24,16,12,24,12,10,24,28,48,8,24,36,24,18,12,16,30,48,24,…
Pell	2,8,4,12,8,6,8,24,12,24,8,28,6,24,16,16,24,40,12,24,24,22,8…
Jacobsthal	6,2,4,6,6,2,18,4,10,6,12,6,12,2,8,18,18,4,6,10,22,6,…

It is well-established that the Pisano period of the Lucas sequence differs from the Pisano period of the Fibonacci sequence only when $m$ is a multiple of $5$ [12]. And note that the Pell sequence is simply the $K$ -Fibonacci sequence when $K=2$ .

Corollary 6.1.

In the Lucas sequence, $m>1$ is a fixed point if and only if $m=24$ .

Corollary 6.2.

In the Pell sequence, $m>1$ is a fixed point if and only if $m=2^{k}$ for $k=1,2,\ldots$

The Jacobsthal sequence is particularly interesting as a different type of sequence where $b\neq 1$ . Note that the results of Renault used in the proofs of Theorem 1.5 used various aspects of $a^{2}+4b$ where $a=K$ and $b=1$ . In the Jacobsthal sequence, note that $a^{2}+4b=9=3^{2}$ .

Conjecture 6.3.

In the Jacobsthal sequence, $m>1$ is a fixed point if and only if $m=2\cdot 3^{k}$ for $k=1,2,\ldots$

Renault’s Theorem 2.6 is originally stated for $(a,b)$ -Fibonacci sequences, which is less controllable when $b\neq 1$ . Let $\pi_{(a,b)}(m)$ denote the $(a,b)$ -Pisano period of the $(a,b)$ -Fibonacci sequence modulo $m$ .

Theorem 6.4 (Renault [11]).

Let $p$ be an odd prime such that $p\not\mid b$ . Then,

•

if $a^{2}+4b$ is a nonzero quadratic residue modulo $p$ , then $\pi_{(a,b)}(p)\mid(p-1)$
•

if $a^{2}+4b$ is a quadratic nonresidue, then $\pi_{(a,b)}(p)\mid(p+1)\text{ord}_{p}(-b)$ except when $b=-1$ , in which case $\pi_{(a,b)}(p)\not\mid(p+1)$ .
•

if $p\mid(a^{2}+4b)$ , then $\pi_{(a,b)}(p)=p\cdot\text{ord}_{p}(2^{-1}\cdot a)$ .

An outlying case occurs when $b=-1$ . There are five degenerate cases: $a=\pm 2$ and $a=\pm 1$ and $a=0$ . These occur when the ratio of the roots of the characteristic polynomial is a root of unity or if $a^{2}+4b=0$ .

If $a=1$ , then $a^{2}-4b=-3$ , and the sequence is a repeating six-term cycle: $0,1,1,0,-1,-1,\ldots$ . Note that if $m=2$ , then $\pi_{(1,-1)}(2)=3$ but for all other $m>2$ , $\pi_{(1,-1)}(m)=6$ . Hence, the only fixed point is $m=6$ . Similarly, if $a=-1$ , then $a^{2}-4b=-3$ , and the sequence is a repeating three-term cycle: $0,1,-1,\ldots$ . Note that modulo any $m>2$ , the $(-1,1,0,1)$ -sequence always has a period of 3. Hence, the only fixed point is $m=3$ .

If instead, $a=2$ , then $a^{2}+4b=0$ and the sequence is exactly: $0,1,2,3,4,5,\ldots$ , hence every positive integer $m>1$ is a fixed point, since modulo $m$ the sequence repeats with a length of $m$ . Somewhat similarly, if $a=-2$ , then $a^{2}+4b=0$ and $\pi_{(-2,-1)}(m)=m$ whenever $m$ is even and $\pi_{(-2,-1)}(m)=2m$ whenever $m$ is odd. Then, fixed points occur whenever $m$ is even.

And if $a=0$ , then $a^{2}-4b=-4$ , and the sequence is a repeating four-term cycle: $0,1,0,-1,\ldots$ . Note that if $m=2$ , then $\pi_{(0,-1)}(2)=2$ and for all other $m>2$ , $\pi_{(0,-1)}(m)=4$ . Hence, the only fixed points are $m=2$ and $m=4$ .

For other values of $a$ , $a^{2}+4b>0$ and something more familiar occurs.

Conjecture 6.5.

Let $p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{t}^{e_{t}}$ be the prime factorization of $a^{2}+4b$ for $a>0$ and $b=-1$ . Suppose $a>2$ then, for every modulus $m>1$ and for $j_{i}=0,1,2,\ldots$ , fixed points $\pi_{(a,-1)}(m)=m$ occur if and only if

(i)

$a\equiv 1\pmod{6}$ and $m=p_{i}^{j_{i}}$ where $p_{i}\mid m$ or $m=6\cdot p_{1}^{j_{1}}\cdots p_{t}^{j_{t}}$
(ii)

$a\equiv 2\pmod{4}$ and $m=p_{i}^{j_{i}}$ where $p_{i}\mid m$ or $m=2^{j_{1}+1}\cdot p_{2}^{j_{2}}\cdots p_{t}^{j_{t}}$ where $p_{1}=2$
(iii)

$a\equiv 3\pmod{6}$ and $m=p_{i}^{j_{i}}$ where $p_{i}\mid m$ and $m=12\cdot p_{1}^{j_{1}}\cdots p_{t}^{j_{t}}$ for $a>3$ ,
and $m=12\cdot p_{1}^{j_{1}}\cdots p_{t}^{j_{t}}$ when $a=3$
(iv)

$a\equiv 0\pmod{4}$ and $m=p_{i}^{j_{i}}$ where $p_{i}\mid m$ or $m=2\cdot p_{2}^{j_{2}}\cdots p_{t}^{j_{t}}$ or $m=4\cdot p_{2}^{j_{2}}\cdots p_{t}^{j_{t}}$ where $p_{1}=2$
(v)

$a\equiv-1\pmod{6}$ and $m=p_{i}^{j_{i}}$ or $m=6\cdot p_{1}^{j_{1}+1}\cdots p_{t}^{j_{t}}$ .

Suppose instead that $a<-1$ , then for every modulus $m>1$ and for $j_{i}=0,1,2,\ldots$ , fixed points $\pi_{(a,-1)}(m)=m$ occur if and only if

(i)

$a\equiv 1\pmod{6}$ and $m=p_{i}^{j_{i}}$ or $m=2^{j_{1}}\cdot 3^{j_{2}+1}\cdots p_{t}^{j_{t}+1}$ where $p_{1}=3$
(ii)

$a\equiv 2\pmod{4}$ and $m=p_{i}^{j_{i}}$ where $p_{i}\mid m$ or $m=2^{j_{1}+1}\cdot p_{2}^{j_{2}}\cdots p_{t}^{j_{t}}$
(iii)

$a\equiv 3\pmod{6}$ and $m=p_{i}^{j_{i}}$ where $p_{i}\mid m$ or $m=12\cdot p_{1}^{j_{1}}\cdots p_{t}^{j_{t}}$
(iv)

$a\equiv 0\pmod{4}$ and $m=p_{i}^{j_{i}}$ where $p_{i}\mid m$ or $m=2\cdot p_{2}^{j_{2}}\cdots p_{t}^{j_{t}}$ or $m=4\cdot p_{2}^{j_{2}}\cdots p_{t}^{j_{t}}$ where $p_{1}=2$
(v)

$a\equiv-1\pmod{6}$ and $m=p_{i}^{j_{i}}$ where $p_{i}\mid m$ or $m=2\cdot 3\cdot p_{2}^{j_{2}}\cdots p_{t}^{j_{t}}$ where $p_{1}=3$ .

It appears that in the previous conjecture, only one prime has powers that are fixed points for any given $a$ ; let this be the critical prime for the $(a,-1)$ -Fibonacci sequence. However, this prime is not always the smallest prime that divides the $a^{2}+4b$ , nor always the largest. What is the behavior of the critical prime in general? A singular case occurs when $a=3$ , there is no critical prime; $a^{2}+4b=5$ , but powers of $5$ are not fixed points.

7. Acknowledgements

The authors would like to extend sincerest appreciation to Dr. Florian Luca for the suggested addition of Theorem 1.3 and Corollary 5.1, and to Michael De Vlieger for their invaluable assistance in writing the code used in the experimental stages of this research.

References

[1] B. Benfield and O. Lippard. Connecting zeros in Pisano periods to prime factors of ${K}$ -Fibonacci numbers. Publication pending, 2024.
[2] Z. Bouazzaoui. Fibonacci numbers and real quadratic p-rational fields. Periodica Math. Hungarica, 81(1):123–133, 2020.
[3] Z. Bouazzaoui. On periods of Fibonacci sequences and real quadratic p-rational fields. Fibonacci Quart., 58(5):103–110, 2020.
[4] G. Everest, A. van der Poorten, I. Sharplinski, and T. Ward. Recurrence Sequences. Rhode Island, USA: American Mathematical Society, 2004.
[5] S. Falcon and Á. Plaza. k-Fibonacci sequences modulo m. Chaos, Solitons & Fractals, 41(1):497–504, 2009.
[6] J. Fulton and W. Morris. On arithmetical functions related to the Fibonacci numbers. Acta Arith., 2(16):105–110, 1969.
[7] J. Harrington and L. Jones. A note on generalised Wall–Sun–Sun primes. Bull. Australian Math. Soc., 108(3):373–378, 2023.
[8] L. Jones. Generalized Wall-Sun-Sun primes and monogenic power-compositional trinomials. Albanian J. Math., 17(2), 2023.
[9] L. Jones. A new condition for $k$ -Wall–Sun–Sun primes. Taiwanese J. Math., 28(1):17–28, 2024.
[10] J. L. Lagrange. Oeuvres de Lagrange. Gauthier Villars, Paris, 7:5–182, 1877.
[11] M. Renault. The period, rank, and order of the (a, b)-Fibonacci sequence mod m. Math. Magazine, 86(5):372–380, 2013.
[12] N. J. A. Sloane and The OEIS Foundation Inc. The on-line encyclopedia of integer sequences A106291. http://oeis.org/A106291, 2021.
[13] Z.-H. Sun and Z.-W. Sun. Fibonacci numbers and Fermat’s last theorem. Acta Arith., 60(4):371–388, 1992.
[14] E. Trojovská. On periodic points of the order of appearance in the Fibonacci sequence. Mathematics, 8(5):773, 2020.
[15] D. D. Wall. Fibonacci series modulo m. Amer. Math. Monthly, 67(6):525–532, 1960.

Fixed Points of KK-Fibonacci Sequences

Abstract.

1. Introduction

Theorem 1.1 (Fixed Point Theorem, Fulton and Morris [6]).

Theorem 1.2.

Example.

Theorem 1.3.

Theorem 1.4 (Falcon and Plaza [5]).

Theorem 1.5 (KK-Fixed Point Theorem).

Theorem 1.6 (KK-Iteration Theorem).

2. Preliminaries

Theorem 2.1 (Renault [11]).

Theorem 2.2 (Renault [11]).

Theorem 2.3 (Renault [11]).

Theorem 2.4 (Harrington & Jones [7]).

Theorem 2.5 ([1], Theorems 4.25 and 4.28).

Theorem 2.6 (Renault [11]).

Theorem 2.7.

Proof.

Theorem 2.8 (Renault [11] and Harrington & Jones [7]).

Theorem 2.9 (Renault [11]).

Theorem 2.10.

Proof.

Theorem 2.11.

Proof.

3. Proof of the K-Fixed Point Theorem

Theorem 3.1.

Proof.

Theorem 3.2.

Proof.

Theorem 3.3.

Proof.

Theorem 3.4.

Proof.

Theorem 3.5.

Proof.

Theorem 3.6.

Proof.

Theorem 3.7.

Proof.

Theorem 3.8.

Proof.

4. Proof of the K-Iteration Theorem

Theorem 4.1 (Renault [11]).

Theorem 4.2.

Proof.

Theorem 4.3.

Proof.

Theorem 4.4.

Proof.

Theorem 4.5.

Proof.

Theorem 4.6.

Proof.

Theorem 4.7.

Proof.

5. Proof of Theorem 1.3

Corollary 5.1.

Proof.

6. Final Thoughts

Corollary 6.1.

Corollary 6.2.

Conjecture 6.3.

Theorem 6.4 (Renault [11]).

Conjecture 6.5.

7. Acknowledgements

References

Fixed Points of $K$ -Fibonacci Sequences

Theorem 1.5 ( $K$ -Fixed Point Theorem).

Theorem 1.6 ( $K$ -Iteration Theorem).