# Factorization of Natural Numbers within 4 n + 1 not Unique

## Theorem

Let:

- $S = \left\{{4 n + 1: n \in \N}\right\} = \left\{{1, 4, 9, 13, 17, \ldots}\right\}$

be the set of natural numbers of the form $4 n + 1$.

Then not all elements of $S$ have a complete factorization by other elements of $S$ which is unique.

## Proof

Consider the number:

- $m = 693 = 3^2 \times 7 \times 11$

Thus:

- $m = 9 \times 77 = 21 \times 33$

We have that:

\(\displaystyle 9\) | \(=\) | \(\displaystyle 4 \times 2 + 1\) | \(\displaystyle \in S\) | ||||||||||

\(\displaystyle 77\) | \(=\) | \(\displaystyle 4 \times 19 + 1\) | \(\displaystyle \in S\) | ||||||||||

\(\displaystyle 21\) | \(=\) | \(\displaystyle 4 \times 5 + 1\) | \(\displaystyle \in S\) | ||||||||||

\(\displaystyle 33\) | \(=\) | \(\displaystyle 4 \times 8 + 1\) | \(\displaystyle \in S\) |

The divisors of these numbers are as follows:

\(\displaystyle 9\) | \(=\) | \(\displaystyle 3^2\) | where $3 \notin S$ | ||||||||||

\(\displaystyle 77\) | \(=\) | \(\displaystyle 7 \times 11\) | where $7 \notin S$ and $11 \notin S$ | ||||||||||

\(\displaystyle 21\) | \(=\) | \(\displaystyle 3 \times 7\) | where $3 \notin S$ and $7 \notin S$ | ||||||||||

\(\displaystyle 33\) | \(=\) | \(\displaystyle 3 \times 11\) | where $3 \notin S$ and $11 \notin S$ |

Thus $693$ has two different complete factorizations into elements of $S$.

Hence the result.

$\blacksquare$

## Sources

- 2008: Ian Stewart:
*Taming the Infinite*... (previous) ... (next): Chapter $7$: Patterns in Numbers