9
$\begingroup$

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\}\}$.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\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 Oct 23 '18 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.