The Euler function and other problems in number theory

Euler function The theory can be read here. Training problem Euler function
Modulo Fibonacci numbers To efficiently find the Fibonacci number, we use matrix multiplication, more details here. Knowing that \(F_{n+m} = F_m F_{n+1} + F_{m-1} F_n\), write the recurrence relation for matrix product: • if \(m = n\) then \(F_{2n} = F_n F_{n+1} + F_ {n-1} F_n\); • if \(m = n + 1\) then \(F_{2n+1} = F_{n+1 } F_{n+1} + F_n F_n\). Training problem **Fibonacci numbers modulo (C++)

The theory can be read here.

To efficiently find the Fibonacci number, we use matrix multiplication, more details here.

Knowing that

\(F_{n+m} = F_m F_{n+1} + F_{m-1} F_n\), write the recurrence relation for matrix product:

• if \(m = n\) then \(F_{2n} = F_n F_{n+1} + F_ {n-1} F_n\);

• if \(m = n + 1\) then \(F_{2n+1} = F_{n+1 } F_{n+1} + F_n F_n\).