I am reading the following problem:
If T = ${1, 4, 7, 10, 13, 16, 19, …}$
then show that the factorization of elements of $T$ into irreducible factors is non unique and find $3$ examples. An element of $T$ is called
irreducible if it is $\ne 1$ and the only factors with $T$ that it has
is $1$ and itself
My approach:
a) Any element $n$ of $T$ can be factored as a product of irreducible factors since each element $n$ is either irreducible so there is no need to prove anything further or is composite i.e. there is some $d$ that divides $n$. This means that $n = d\cdot e$ for some $e$. And each of these factors are either composite or irreducible. Following the same logic we break down further and further till we would need to reach an irreducible. Basically it is exactly the same logic for the primes and counting numbers set.
b) We know that an element $n$ can be expressed as a factor of irreducible numbers (which in my understanding "irreducible" $\equiv$ prime).
If the factorization is not unique it means that we have a number $N$ that can be written in $2$ ways:
$N = 1^{e1}\cdot 4^{e4}\cdot 7^{e7}\cdot 10^{e10}…p^{ep}=1^{f1}\cdot 4^{f4}\cdot 7^{f7}\cdot 10^{f10}…p^{fp}$
Where $e^n$ and $f^n$ are the exponent of the $n$ irreducible number and $p$ is some irreducible number.
If the factorization is not unique then this means that $e^p \ne f^p$
Assume that $e^p \le f^p$ so we define $d_p = f^p – e^p$. If we divide $N$ with $p^{ep}$:
$$\frac{N}{p^{ep}}= 1^{e1}\cdot 4^{e4}\cdot 7^{e7}\cdot 10^{e10}… p^{0}= 1^{f1}\cdot 4^{f4}\cdot 7^{f7}\cdot 10^{f10}…p^{dp}$$
If $dp > 0\space $ then this means it would divide both sides and hence divide an irreducible term which is impossible.
Hence the factorization has to be unique. This is the same proof we use for the counting numbers set.
But the problem is that the factorization of this set is indeed non unique e.g.
$100 = 4 \cdot 25 = 10^2$
So I don't understand what is wrong here. Why does the standard proof for primes does not work for this set of numbers?
Update:
It seems that the key issue here is if the euclidean lemma is applicable. My understanding was that $gcd(10,4) = 1$ so the lemma would be applicable. But then there was a counter example already provided i.e. $10^2=4\cdot 25$ which I did not come up with so, I am confused
a) when we define a new arbitrary set, which know rules are applicable. E.g. $gcd(10,4) = 2\space$ but $2 \notin T$
b) Without the counterexample given how could I have noted/proven the lemma does not hold?
Update 2:
After the comments of @Infinity_hunter, @TonyK and @arbashn I see that there is a confusion due to my terminology.
The textbook I am reading defines the Euclid's lemma as follows:
Let $a$, $b$ and $c$ be integers. If $a\mid bc$ and $gcd(a,b) = 1$
then $a \mid c$
Following that the textbook specializes the lemma for when $a$ is a prime and then goes on to show the uniqueness of prime decomposition.
These are the only premises I was working on and am/was aware and why I have been asking about the $gcd$ in my comments.
So is there a more appropriate definition of the euclidean lemma/primes that I should be familiar with?
Best Answer
The definition of irreducibles which is mentioned in the question is perfect. Now you may observe that there are elements (say $p$ ) in $T$ such that for any $a,b \in T$, $p$ divides $ab$ implies that $p$ divides $a$ or $b$. We call such elements as prime in $T$. For example, $7$ is a prime in $T$ because $7$ is a prime in $\mathbb{N}$ and we can make use of Euclid's lemma to conclude. Note that $7$ is also irreducible.
Also we can see that $10$ is not a prime in $T$. To see that we take the same example which you provided, take $ab = 100, a= 4, b =25$, so $10$ divides $100$ but none of $a,b$.
It is possible that an irreducible $p$ (such as $10$) can divide $1^{e_1}\cdot 4^{e_4}\cdot 7^{e_7}\cdot 10^{e_{10}}... $ without dividing any of $1,4,7, \dots$, etc.This was a flaw in the argument.
You can easily apply your argument to the sets where each irreducible is a prime in that set.
Update:
I think OP considering as Euclid's lemma is the generalization of Euclid's lemma given here - https://en.wikipedia.org/wiki/Euclid%27s_lemma . It says that
Note that the lemma does not make use of the concept of $\gcd$.
I don't think we can show that the lemma does not hold in $T$ without exhibiting counterexamples. When we define a new structure on sets, we appropriately define a set of rules or axioms which the elements of the set should satisfy.