# Prime factorization of

For a positive integer $$k$$, let $$S_k$$ be the set of numbers $$n > 1$$ that are expressible as $$n = kx + 1$$ for some positive integer $$x$$. The set $$S_k$$ is closed under multiplication. That is: If $$a, b$$$$S_k$$then $$ab$$$$S_k$$. Definition. Suppose $$n ∈ S_k$$ . If $$n$$ is expressible as $$n = ab$$ for some $$a, b ∈ S_k$$ , then $$n$$ is called $$k$$-composite. Otherwise $$n$$ is called a $$k$$-prime. For example, $$S_4 = \{5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, . . . \}$$ . The numbers $$25, 45, 65, 81, . . .$$ are $$4$$-composites, while $$5, 9, 13, 17, 21, 29, . . .$$ are $$4$$ -primes.

1. For which $$n ∈ S_4$$ are $$4$$-primes? (Answer in terms of the standard prime factorization of $$n$$. Show: Every $$n∈ S_4$$is either a $$4$$-prime or a product of some $$4$$-primes. But “unique factorization into $$4$$-primes” fails. To prove that, find some $$n = p_1p_2 · · · p_s$$ and $$n = q_1q_2 · · · q_t$$ where each $$p_j$$and $$q_k$$ is a $$4$$-prime, but the list $$(q_1, . . . , q_t)$$ is not just a rearrangement of the list $$(p_1, . . . , p_r)$$.

Hint: think about $$441=3^2\cdot 7^2=4\cdot 110+1 \in S4$$. It is 4-composite, how does it factor? Can you generalize?
• It is important that if you multiply two numbers that are equivalent to $3 \bmod 4$ you get a number that is equivalent to $1 \bmod 4$. Most numbers that have at least four factors of the shape $3 \bmod 4$ will fail to have unique factorization. That is how I found this example. To prove there is no unique factorization you just need to find one example that has two factorizations, and $441$ is one example because $441=9 \cdot 49=21^2$ and all the things on the right cannot be factored. Commented Mar 5, 2019 at 5:44