# Positive integers are a free commutative monoid?

I'm an undergrad, and I've been presented with the following problem:

Fundamental Theorem of Arithmetic: Let $\mathbb{N}_{>0}$ be the monoid of positive integers with binary operation given by ordinary multiplication, let $P$ be the set of primes in $\mathbb{N}$, let $M$ be a commutative monoid and let $g : P → M$ be a function. Prove that there is a unique monoid homomorphism $G : \mathbb{N}_{>0} → M$ such that $G(p) = g(p)$ for every prime $p ∈ P$.

So far, I've been able to come up with this:

Let $G: \mathbb{N}_{>0} \to M$ be such that $G(p) = g(p)$ for all $p \in P$. Since $G$ isn't explicitly defined for non-prime numbers, we can just say that $G(1) = e$, where $e \in M$ is the identity. Let $x, y$ be positive integers. We want to show that $G(xy) = G(x)G(y)$.

Am I right in just declaring $G$ to be what I want it to be and then showing it's a monoid homomorphism? Does my logic for the identities make sense? How do I attack the last part (with $G(xy) = G(x)G(y)$)? Or am I completely wrong and I should erase what I have and start over? And what does the fundamental theorem of arithmetic have to do with any of this?

• 1. Yes, you should declare $G$ to be something or other, and then show it's a monoid homomorphism ($G(xy)=G(x)G(y)$). You will not be able to attack that last part until after you declare what $G$ is. 2. On the other hand, you can't declare $G$ arbitrarily. You are constrained that for non-prime numbers, $G(pq)$ has to be $G(p)G(q)$, which is $g(p)g(q)$; $G(p^2 q^3)$ has to be $G(p)^2 G(q)^3$, which is $g(p)^2 g(q)^3$, and so on. Does that give you something to work with? I hope it helps! Nov 18, 2017 at 1:25

Hint: you need to define $G(x)$ for all $x \in \Bbb{N}_{>0}$ based on the partial definition given by $g$. To do that, use what you have to prove to tell you what how to fill out the definition. E.g., you know $G(2) = g(2)$ and $G(3) = g(3)$ for the given function $g: P \to M$, so you have to define $G(6) = G(2)\cdot G(3) = g(2) \cdot g(3)$ and $G(8) = G(2^3) = g(2)^{3}$. The fundamental theorem of arithmetic tells you that each $x \in \Bbb{N}_{>0}$ has a unique representation of the form $p_1^{i_1}\cdot p_2^{i_2} \cdots p_k^{i_k}$. That tells you how to define $G(x)$.
hint: the fundamental theorem of arithmetic states that every $n=p_1^{q_1} \cdots p_n^{q_n}$ for primes $p_1, \dots q_n$. Consider $P \hookrightarrow \mathbb N$. Once you have a map defined on all of $P$, then the rest will follow by the morphism restriction.
Take a function $G:P \to M$. Let $\tilde{G}:\mathbb N \to M$ just be the extension of $G$ to all of $\mathbb N$. For example, Then $\tilde{G}(6):=\tilde{G}(2 \cdot 3)=G(2)G(3)$