# Why is factor count of n equal to product of the factor counts of n's coprime factors?

I recently read in a thread that if you know that $a$ and $b$ are coprime, then the number of factors in $n = ab$ is equal to the number of factors in $a$ multiplied by the number of factors in $b$. The reason for this isn't obvious to me and I want to see a proof, but I don't know what to google to find it. Could somebody explain this relationship to me?

• Because every factor of $n$ splits as (factor of $a$)(factor of $b$) in a unique way. – user296602 Oct 17 '17 at 19:15
• If $d\mid n$ then $\gcd(d,a)\cdot \gcd(d,b)=d$, when $n=ab$ with $a,b$ relatively prime. – Thomas Andrews Oct 17 '17 at 19:19

## 1 Answer

Here's a proof:

Let $F_{x}$ denote the set of factors of a positive integer $x$. Clearly $|F_{a} \times F_{b}| = |F_{a}||F_{b}|$. Define a function $f: F_{a} \times F_{b} \longrightarrow F_{n}$ such that $f(x,y) = xy$ for all $(x,y) \in F_{a} \times F_{b}$.

Let $d \in F_{n}$. As stated in Thomas Andrew's comment, $d = \gcd(d,a)\gcd(d,b)$, so $f( \gcd(d,a),\gcd(d,b)) = d$. Hence $f$ is surjective.

Suppose that $f(x,y) = f(x',y')$, so $xy = x'y'$. Let $p$ be prime, and suppose that $p|xy$. Then, by the definition of prime, $p | x$ or $p | y$. If $p | x$, then $p|a$, so $p$ cannot divide $y$ or $y'$. Hence, $p | x'$. Thus, $x$ and $x'$ must have the same prime factors. By the same reasoning $y$ and $y'$ must have the same prime factors. Therefore, by the Fundamental Theorem of Arithmetic, $x = x'$ and $y = y'$. Thus, $f$ is injective and therefore a bijection.

Since there exists a bijection from $F_{a} \times F_{b}$ to $F_{n}$, $|F_{n}| = |F_{a} \times F_{b}| = |F_{a}||F_{b}|$.

• Bravo! Thomas Andrew's comment sort of made it click for me, but this answer crystalized my understanding. Thank you Keima! – Broseph Oct 18 '17 at 4:02