The Fundamental Theorem of Arithmetic states that every integer $n > 1$ can be uniquely expressed as a product of prime powers, that is:
$$n = p_1^{n_1}p_2^{n_2} \cdots p_k^{n_k}= \Pi_{i=1}^{k}p_i^{n_i}$$
Here, $p_1 < p_2 \cdots < p_k$ are primes, and the $n_i$s are positive integers.
Now, when listing the prime factorisations of $2$ arbitrary integers $a$ and $b$ ( in order to compute their gcd, lcm, etc ), many resources online, including some textbooks, simply say: Let $a=p_1^{m_1} \cdots p_k^{m_k}$ and $b=p_1^{n_1} \cdots p_k^{n_k}-\mathbf(1) $. My concern is why this can be simply stated without the need to prove it ... Or is this actually a pretty trivial observation? Granted, one could first provide the caveat that $p_i$ is the set of all primes dividing either $a$ or $b$. Still, I am not convinced that the factorisation in $ -\mathbf(1)$ should be so intuitive, because, from the FTA, we know that the canonical factorisation of any integer must be unique. In addition, some sort of permutation of the prime factors between those in $a$ and those in $b$ may be involved. I think the following claim has to be proven first, before this statement can be validated:
Let $a=q_1^{e_1} \cdots q_r^{e_r}$ and $b=s_1^{f_1} \cdots s_t^{f_t}$ be the canonical prime factorisations of $a$ and $b$ respectively, and each prime power is a postitive integer. Then, there exists a strictly increasing sequence of primes $(p_i)_{i=1}^{k}$, and 2 non-negative sequences of integers, $(m_i)_{i=1}^{k}$ and $(n_i)_{i=1}^{k}$, such that :
$a=p_1^{m_1} \cdots p_k^{m_k}$ and $b=p_1^{n_1} \cdots p_k^{n_k} $
Below's the approach that I have taken:
Clearly, $a= q_1^{e_1}...q_r^{e_r}s_1^0s_2^0\cdots s_t^0$, and $b=s_1^{f_1}s_2^{f_2} \cdots s_t^{f_t}q_1^0 \cdots q_r^0$. Thus, there exists $ k \in \mathbb{Z^+}$, $max(r,t) \leq k \leq r+t$, such that $a=\Pi_{p=1}^{k}p_i^{m_i}$. Also, $p_i \in \{q_1, \cdots q_r, s_1, \cdots s_t\}$ is a strictly increasing sequence of primes, and we have that $m_i \in (e_i)_{i=1}^{r}$ or $m_i =0 \ \forall \ i $.
Similarly, for $b$, we have that $b=\Pi_{p=1}^{k}p_i^{n_i}$. Also, $p_i \in \{q_1, \cdots q_r, s_1, \cdots s_t\}$ is a strictly increasing sequence of primes, and $n_i \in (f_i)_{i=1}^{t}$ or $n_i =0 \ \forall \ i $.
Of course, this proof may not be complete. In particular, I would appreciate it if anyone could suggest on how to improve it, or give a more concise/elegant argument.
Answer
You're overcomplicating things. Let $P_1,P_2$ be the set of primes dividing two positive integers $m,n$ respectively, then we write $m=\prod p^\alpha,n=\prod p^\beta$ with the understanding that $p\in P_1\cup P_2$ and $\alpha,\beta$ are nonnegative (not necessarily nonzero).
There is absolutely no need to prove this in a more "mathematical" way by using more abstract symbols or logical notation. If the logic is clear (as it should be---since raising anything to the $0$th power gives you the multiplicative identity and does not change the integer in question), then your proof is complete, and you don't need to "complete" it even more with more symbols in order for it to seem more "mathematical". Beware of confusing yourself when you do so!
By the way, the fundamental theorem of arithmetic doesn't exactly say that the canonical factorisation is unique. It says that it is unique up to permutation of the factors. Since multiplication of integers is commutative, this means we can always write the canonical factorisation without loss of generality in increasing order of the factors, so the issue of permutation of factors you raised is really a non-issue.
No comments:
Post a Comment