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?

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

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}|$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.