Showing posts from August, 2018

Interesting formulas and exercises in number theory

In this post I would like to introduce some interesting exercises in number theory, along with some curious formulas and identities for some number-theoretic functions.

The following list includes the notations used in this post: `φ(n)` is the Euler's totient function`J_k(n)` is the Jordan's totient function`σ_k(n)` is the Divisor (sigma) function`μ(n)` is the Möbius function`c_q(n)` is the Ramanujan's sum function
# Conditional Euler's totient function Given a boolean function `f(x)`, let `a(n)` be the number of integers `k` in the range `[1, n]` for which `f(gcd(n, k))` is true.

For example, if `f(x)` returns a true value only when `x=1`, then the problem reduces to the Euler's totient function: `a(n) = φ(n)`.

This is interesting, because if the prime factorization of `n` can be computed, then we can efficiently compute `φ(n)` using the following formula:

`φ(n) = n * \prod_{p|n} (1 - 1/p)`

where the product is taken over the distinct prime factors of `n`.

Now con…

Investigating the Fibonacci numbers modulo m

The Fibonacci sequence is, without doubt, one of the most popular sequences in mathematics and in popular culture, named after Italian mathematician Leonardo of Pisa (also known as Fibonacci, Leonardo Bonacci, Leonardo of Pisa, Leonardo Pisano Bigollo, or Leonardo Fibonacci), who first introduced the numbers in Western European with his book Liber Abaci, in 1202.

The sequence is elegantly defined as:

`F(0) = 0`
`F(1) = 1`
`F(n) = F(n-1) + F(n-2)`

where the first 20 terms are:

`0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181`

In this post, we investigate the Fibonacci numbers modulo a positive integer `m`. It is well known that for every positive integer `m`, the modular Fibonacci sequence, `F(n) mod m`, is eventually periodic. This period is called the Pisano period.
For example, let's take a look at `F(n) mod 4`:
0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, ...
we observe, as highlighted above in yellow, the Pisano cycle has a length of…