Factorization of Natural Numbers within 4 n + 1 not Unique
Jump to navigation
Jump to search
Theorem
Let:
- $S = \set {4 n + 1: n \in \N} = \set {1, 5, 9, 13, 17, \ldots}$
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:
| \(\ds 9\) | \(=\) | \(\ds 4 \times 2 + 1\) | \(\ds \in S\) | |||||||||||
| \(\ds 77\) | \(=\) | \(\ds 4 \times 19 + 1\) | \(\ds \in S\) | |||||||||||
| \(\ds 21\) | \(=\) | \(\ds 4 \times 5 + 1\) | \(\ds \in S\) | |||||||||||
| \(\ds 33\) | \(=\) | \(\ds 4 \times 8 + 1\) | \(\ds \in S\) |
The divisors of these numbers are as follows:
| \(\ds 9\) | \(=\) | \(\ds 3^2\) | where $3 \notin S$ | |||||||||||
| \(\ds 77\) | \(=\) | \(\ds 7 \times 11\) | where $7 \notin S$ and $11 \notin S$ | |||||||||||
| \(\ds 21\) | \(=\) | \(\ds 3 \times 7\) | where $3 \notin S$ and $7 \notin S$ | |||||||||||
| \(\ds 33\) | \(=\) | \(\ds 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: Euclid