Posts

Continued fraction factorization method

Image
Prime factorization of composite integers has many applications in number theory,  especially in computing some important arithmetic functions for large inputs.

One such function is the Euler's totient function `φ(n)`, which it's practically impossible to compute for very large composite values of `n`, if the prime factorization of `n` is not known.

This led to the creation of public-key cryptography systems (such as the RSA algorithm), which are systems responsible for secure communication online and rely on the assumption that it's very hard to factorize a large integer `n` that is the product of two large random prime numbers.

The publication of the RSA algorithm led to an increasing interest in factoring large integers, which also resulted in the creation of several new factorization algorithms, none of which, however, is able to efficiently factorize an RSA modulo.

The factorization method that we present in this post is quite an old method (even older than RSA), but…

Curious formulas and exercises in number theory

Image
In this post I would like to present 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 consi…

Investigating the Fibonacci numbers modulo m

Image
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…