Factorization of Natural Numbers within 4 n + 1 not Unique

From ProofWiki
Jump to: navigation, search

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

Proof by Counterexample:


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