Math Notes Spring 25

April 9th 2025

Fibonacci Moduli

For the Fibonacci sequence, defined by $F_{1} = 1, F_{2} = 1, F_{n} = F_{n - 1} + F_{n - 2}$

I believe the following is true (Haven’t found any counterexamples)

(F_{n} \mod n) \neq 0 when (n \mod 6) \in {2,3,4}

Complete Factorization

Quick! what are all the factors of $720$ ?

Instead of giving you an answer, here’s an algorithm to find it.

First, by repeated division, find the prime factors.

\begin{array}{lrlr} 720 / 2 & = 360 \\ 360 / 2 & = 180 \\ 180 / 2 & = 90 \\ 90 / 2 & = 45 \\ 45 / 3 & = 15 \\ 15 / 3 & = 5 \\ 5 / 5 & = 1 \end{array}

F_{0} = [2, 2, 2, 2, 3, 3, 5]

Find the all unique factors and their cartesian products in $F_{0}$ to create $P_{0}$ .

P_{0} = {2, 3, 5, 6, 10, 15, 30}

S_{0} = P_{0}

Remove one of each unique factor from $F_{0}$ to make $F_{1}$ .

F_{1} = [2, 2, 2, 2, 3, 3, 5]

Find the all unique factors and their cartesian products in $F_{1}$ to create $P_{1}$ .

P_{1} = {2, 3, 6}

Multiply each number in $P_{1}$ by each number in $S_{0}$ to find $S_{1}$ Remove any duplicate values and remove any values which had been found in previous $S_{n}$ .

\begin{array}{lrlr} S_{1} = { & 4, 6, 10, 12, 20, 30, 60 \\ 6, 9, 15, 18, 30, 45, 90 \\ 12, 18, 30, 36, 60, 90, 180} \\ S_{1} = { & 4, 10, 12, 20, 60, 9, 18, 45, 90, 36, 180} \end{array}

Remove one of each unique factor from $F_{1}$ to make $F_{2}$ .

F_{2} = [2, 2, 2, 2, 3, 3, 5]

Find the all unique factors and their cartesian products in $F_{2}$ to create $P_{2}$ .

P_{2} = {2}

Multiply each number in $P_{2}$ by each number in $S_{1}$ to find $S_{2}$ Remove any duplicate values and remove any values which had been found in previous $S_{n}$ .

\begin{array}{lrlr} S_{2} & = {8, 20, 24, 40, 120, 18, 36, 90, 180, 72, 360} \\ S_{2} & = {8, 24, 40, 120, 72, 360} \end{array}

Remove one of each unique factor from $F_{2}$ to make $F_{3}$ .

F_{3} = [2, 2, 2, 2, 3, 3, 5]

Find the all unique factors and their cartesian products in $F_{3}$ to create $P_{3}$ .

P_{3} = {2}

Multiply each number in $P_{3}$ by each number in $S_{2}$ to find $S_{3}$ Remove any duplicate values and remove any values which had been found in previous $S_{n}$ .

S_{3} = {16, 48, 80, 240, 144, 720}

Remove one of each unique factor from $F_{3}$ to make $F_{4}$ .

F_{4} = [2, 2, 2, 2, 3, 3, 5]

Seeing as there are no more prime factors left in $F$ , Halt. The factors of $720$ are found in the union $S_{0}, S_{1}, S_{2}, S_{3}$ and of course $1$ .

\begin{array}{lrlr} S & = {1} \cup S_{0} \cup S_{1} \cup S_{2} \cup S_{3} \\ S & = { \\ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, \\ 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360, 720 \\ } \end{array}

I don’t know the name of this algorithm. I figured it out myself, but the simplicity of the algorithm leads me to believe it has been known for quite some time. There are likely more efficient algorithms, but compared to the naive algorithm of dividing by all numbers less than, it is appreciably efficient. An advantage of this algorithm is that it can be done on pen-and-paper and also can be done using a computer.

Squares mod 100

Two neat little identities for squares mod 100.

n^{2} \equiv (n + 50)^{2} \mod 100

And

n^{2} \equiv (50 - n)^{2} \mod 100

These can be algebraically shown to be true

n^{2} \equiv (n^{2} + 2500 + 100 n) \mod 100

What about the generic case of a modulus $k$ ? What is the specific $m$ to be added to $n$ to make the squares congruent?

n^{2} \equiv (n + m)^{2} \mod k

Expand

n^{2} \equiv (n^{2} + m^{2} + 2 m n) \mod k

The trivial case is for $m^{2} \equiv 0 \mod k$ and $2 m n \equiv 0 \mod k$ . Let’s just ignore the possibility that both of those aren’t true and yet still $(m^{2} + 2 m n) \equiv 0 \mod k$

The smallest natural number $m$ such that $2 m n \equiv 0 \mod k$ for any integer $n$ is clearly $k / 2$ if $k$ is even, and $k$ if $k$ is odd.

The smallest natural number $m$ such that $m^{2} \equiv 0 \mod k$ is a bit trickier.

$m^{2} = k^{2}$ Obviously works, but the case of $m^{2} = (k / 2)^{2}$ only works if $k$ is divisible by $4$

m = \frac{k}{2}

m^{2} = \frac{k^{2}}{2^{2}}

\frac{m^{2}}{k} = \frac{k}{4}

So for

n^{2} \equiv (n + m)^{2} \mod k

If $k$ is divisible by $4$

m = k / 2

Otherwise:

m = k