Can I use prime factorization to prove that the rationals are countable? I know the classic argument for countability of $\mathbb{Q}$ is the zig-zagging traversal, but could I also prove that the rationals are countable using prime factorization of the natural numbers? For instance, defining an injective function $f: \mathbb{Q} \to \mathbb{N}$ where $f(\frac{a}{b}) = 2^{a}3^{b}$. This should work, unless I'm missing something.
 A: This almost works. You have to worry a little about the sign of $\frac{a}{b}$: as it stands your function doesn't work on negative rationals. But you could make some definition like $g(c\frac{a}{b})=2^a3^b5^{1+c}$, where $a$ is nonnegative, $b$ is positive, $\gcd(a,b)=1$, and $c \in \{-1,1\}$.
A: Just to give a single, simple expression that handles all cases, if $q=a/b$ with $\gcd(a,b)=1$ and $b\ge1$, then
$$f(q)=2^{|a|}\cdot3^b\cdot5^{|a|+a}$$
will be an injection from $\mathbb{Q}$ to $\mathbb{N}$.
A: Need to 1) specify that $\gcd(a,b) = 1$ (but we can assume that is a given)
Need to state $0 = 0/1$ (we can probably take that as a given--- oh, wait, of course we can.  $\gcd(0,a) = a$ so $a/b =0; \gcd(a,b)=1$ can only but $b =1$).
Need to take negative numbers into account.  We can declare a rational number has a unique representation as $\pm \frac ab$ where $a \ge 0$, $b > 0$ and $\gcd(a,b) = 1$.  Then we can have $f(+a/b) = 2^a3^b$ and $f(-a/b) = 2^a3^b*5$.
If for some reason we want to keep just the two prime factors we can declare that positives and zero go to even powers of $2$ and negatives to odd powers. i.e.  $f(\pm \frac ab= (-1)^n \frac ab; n = \{0, 1\}) = 2^{2a+n}3^b$. 
So, yes, these are perfect well-defined injective functions into $\mathbb N$ and so $\mathbb Q$ are countable.
