# Why does prime factorization hold in the set of integers of the form $4k+1$?

I want to prove that in the set $$S = \{4k+1 : k\text{ is a positive integer}\}$$ (i.e. $S = \{1, 5, 9, 16, \dots \}$) unique prime factorization holds. How do I do that?

Edit: a prime in this universe is something that cannot be written as $ab$ where both $a$ and $b$ are in the set unless either $a=1$ or $b=1$.

• Can't you just invoke the fundamental theorem of arithmetic? – Cameron Williams Sep 11 '13 at 0:24
• no, because the definition of a prime in this set is different. Since the "universe" is just the numbers 1,5,9... numbers like 9 (for example) are prime. – pittabreadD4 Sep 11 '13 at 0:26
• I don't think it is true, unless you have a meaning of prime I'm missing. – Thomas Andrews Sep 11 '13 at 0:28
• 9 is not even a prime number. – user60887 Sep 11 '13 at 0:33
• @pittabreadD4: Please note that you can use \text{...} to write text inside math mode, producing upright text without the need to force spaces with \ . – Zev Chonoles Sep 11 '13 at 0:38

If by a prime in this set you mean something that cannot be factored non-trivially in this set, the result is false. For we have $(9)(49)=(21)(21)$.

The numbers $9$, $49$, and $21$ are prime in this set.

You can produce an infinite family of examples by taking $4$ distinct ordinary primes of the form $4k+3$, say $s,t,u, v$ and considering the number $stuv$, which has three distinct "prime" (in the $4k+1$ sense) factorizations.

Remark: This answers the question if we define prime as you did, as a number $p$ which has no non-trivial factorization in our set. It does not answer the question if by prime we mean a number $p$ which is not a unit, such that $p$ divides $ab$ implies that $p$ divides $a$ or $p$ divides $b$.

if you are interested in objects like that they are called ACM Arithmetic Congruence Monoids. You are asking to see if the case $M_{1,4}=\{n\in \mathbb{N}:n\equiv 1\pmod{4}\}$ is factorial, and the answer is no. You can look at Andre Nicolas answer for specific examples. Thus, we know that an equivalent to "the fundamental theorem of arithmetic" fails in this monoid. It is natural to ask how bad does it fail? By how bad does it fail, one has to give some sort of "metric" to failing being a factorial monoid. The "metric" used to see how bad does a monoid fail is called the elasticity. The elasticity of an element is taking the ratio of the length of the longest factorization over the length of the shortest factorization. To find the elasticy of the monoid on takes the supremum over all the elasticities of the elements.

It turns out that your monoid does not fail the factorial property by much, since with some work one can prove that all factorizarizations into irreducibles always yield the same length, i.e., the elasticity of the monoid is $1$.