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$.
 A: 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$. 
A: 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$. 
If you would like to read more about them: http://www.math.smith.edu/~pbaginski/Papers/SubmittedACMSurvey%20RevisedReferee%2001.20.2013.pdf
The answer for your question is given in theorem 3.4 of the above paper.
I believe professor Scot Chapman runs an REU (research experience for undergraduates) on this topic. You should consider looking into it if you qualify. 
