1. ## irreducibles

Let N' be the set of all positive integers congruent to 1 (mod 4).
Call an element N'\{1} irreducible if it can't be factorized into strictly smaller elements of N'.

Is every element of N' a product of irreducibles?
Is this expression of an element of N' as a product of irreducibles unique up to order?

2. Let's see some work!

3. Ok so we have N' = {1 + 4n : n is an integer >= 0}
i.e. N' = {1,5,9,13,17,21,25,....}

So N'\{1} = {5,9,13,17,21,25,....}

So 5 is irreducible since 5 = 1 x 5 [it cant be factorized into STRICTLY smaller elements of N']

Also 9 is irreducible since
(i) 9 = 1 x 9 [i.e. it cant be factorized into STRICTLY smaller elements of N']
(ii) 9 = 3 x 3 [but 3 is NOT an element of N']

But 25 is not irreducible since 25 = 5 x 5.

How do I proceed??

I was thinking of something like a tree diagram and saying that if m is irreducible, then it is a product of irreducibles?? If m is not irreducible, then m = m_1 x m_2 and then continue until process stops?
Im thinking that it is not unique somehow but I cant find a counterexample?

4. Umm is this correct so far? Just to note this is not an assessed assignment question (in case you dont want to give much away - but its from an assignment sheet from autumn 2009)

http://www.warwick.ac.uk/~maseap/tea...nt/assign1.pdf

5. Originally Posted by vinnie100
Let N' be the set of all positive integers congruent to 1 (mod 4).
Call an element N'\{1} irreducible if it can't be factorized into strictly smaller elements of N'.

Is every element of N' a product of irreducibles?
Well, the answer to this should be obvious- by definition, if a number is not irreducible itself it can be factored into strictly smaller elements of N' which are either irreducible or can be factored. Eventually, that has to stop so you have factored in to a product of irreducibles, just as you say in your second post. It is important to note that there are only finite number of integers less than a given integer so this will stop!

Is this expression of an element of N' as a product of irreducibles unique up to order?
This is a little harder. Suppose such a number could be factored in two different ways. Because prime factorization of integers is unique, the "irreducible factors" would have to have the same prime factors, just "shifted" from one "irreducible factor" to the other. Is that possible?