Let $\{f_i\}_{i\in\mathbb N}$ be the sequence of Fibonacci numbers, i.e. $1,2,3,5,8,13,21,34,55,\cdots$, For every integer $n\gt3$ prove that $$4\mid\phi(f_n)$$ where $\phi$ is Euler's totient function.

By using the formula $\phi(p_1^{\alpha_1}\ldots p_k^{\alpha_k})=p_1^{\alpha_1-1}\ldots p_k^{\alpha_k-1}(p_1-1)\ldots(p_k-1)$ for distinct primes $p_i$ and natural numbers $\alpha_i$, we can say that the problem is equivalent to show that for $n\gt3$, $f_n\notin \{2^{\epsilon}q^k|k\in \mathbb N, q\equiv3\pmod4 \text{ be a natural prime number},\epsilon\in\{0,1\}\}$.


1 Answer 1


Quick background: Cassini's Identity states that $u_{n+1}u_{n-1} - u_{n}^2 = (-1)^n$ where $u_n$ is the $n$th Fibonacci number.

"We note that $(u_n,u_{n+1})=1$, $(u_n,u_{n-1})=1$.

Note that $1$, $-1$, $-u_{n-1}$, $u_{n-1}$ are incongruent modulo $u_n$, $u\geq 5$, and form a multiplicative subgroup of the multiplicative group of integers modulo $u_n$. Since the order of the multiplicative group of integers mod $u_n$ is $\phi(u_n)$, where $\phi(n)$ denotes the number of integers less than $n$ and prime to $n$, and since the order of the subgroup divides the order of a group, $4 | \phi(u_n)$."

Source: A primer for the Fibonacci numbers XVII: Generalized Fibonacci numbers satisfying $u_{n+1}u_{n-1} - u_{n}^2 = \pm 1$

This paper also defines the sequence starting from $0 , 1 , 1, 2, 3, 5,...$ which explains the offset from your $n>3$ condition.

  • $\begingroup$ I'm not getting how the Cassini's identity and $(u_n,u_{n-1})=1$ is used here :-( Can you please explain it? $\endgroup$
    – Taxicab
    Commented Oct 23, 2018 at 5:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .