There are $2^{\omega(a)}$ pairs $(b,c)$ such that $a=bc$ and $\gcd(b,c)=1$

Question

It looks as there are $2^{\omega(a)}$ ordered pairs $(b,c)$ such that $a=bc$ and $\gcd(b,c)=1$, where $\omega(a)$ is the number of different prime factors of $a$.

Proof?

It's also true that there are $n^{\omega(a)}$ n-tipples $(a_1,\dots ,a_n)$ such that $a=a_1\cdots a_n$.

Answer 1

Hint: a pair $\,(b,c)\,$ corresponds to a partition $\, A = B\cup C\, $ of the set of primary factors $\,p_i^{e_i}\,$ of $\,a,\,$ hence mapping $\,b\,$ to its corresponding subset $B$ of the partition bijects these pairs with all subsets of the set $A$ of primary factors of $a$, of which there are $2^n,\,$ since $a$ has $n$ distinct prime factors.

For example if $\,a = 2^i 3^j 5^k$ then $\,A = \{ 2^i, 3^j, 5^k\}$ and the coprime factorization corresponding to the partition $\, A = \{2^i ,3^j\}\cup \{5^k\}\,$ is $\,a = \color{#c00}{2^i 3^j}\times 5^c = \color{#c00}b\times c,\,$ where $\,b\,$ corresponds to the product of the elements in the first set, i.e. $\,\color{#c00}{b = \prod\, \{2^i,3^j\}}$

Equivalently these coprime factorizations correspond to idempotents of $\,\Bbb Z/a \,\cong\, \Bbb Z/b \times \Bbb Z/c,\,$ elements which govern such ring factorizations. This correspondence between element vs. ring factorizations holds much more generally - as proved here if $R$ is a UFD then proper factorizations of the ring $\,R/a\,$ correspond to coprime (i.e. comaximal) factorizations of the element $\,a = b\times c,\,$ just like in the classical CRT = Chinese Remainder Theorem.

Answer 2

Bear with me. I'm going to introduce components for the sake of lining up my ducks in a row. And then I will shoot.

(If this whole thing is too long you can skip to the very last paragraph:

LAST PARAGRAPH:

Likewise for each prime factor of $a$ we can either have $p|b$ or $p|c$ so there are two choices for each prime factor of $a$ and so there are $2^{\text{number of prime factors}}$ choices of pairs.

If that is too terse read on for a duck guide:)

let $\omega(a) = n$. Let $U = \{p_1,p_2,....,p_n\}$ be the distinct prime factors of $a$. Then we can write the unique prime factorization of $a$ as $a = \prod_{p_i\in U} p_i^{m_i}$ where the $m_i$ are natural numbers (the powers to which the prime factors divide $a$)

Suppose $b, c$ are natural numbers. And let $B=\{$ the distinct prime factors of $b\}$ and $C = \{$ the distinct prime factors of $c\}$ and $b,c$ have unique prime factorizations of $b= \prod_{q_i\in B} q_i^{w_i}$ and $c= \prod_{r_i\in B} r_i^{u_i}$

1. Case 1: If $b|a$ and if $c|a$ then $B\subset U$ and $b= \prod\limits_{p_i\in B}p_i^{w_i}$ where $w_i \le m_i$. And $C \subset U$ and $c= \prod\limits_{p_i\in C}p_i^{u_i}$ where $u_i \le m_i$.
2. Case 2: If $\gcd(b,c) = 1$ then $B\cap C = \emptyset$
3. Case 3: If $a = bc$ (then $b|a$ and $c|a$ so Case 1 holds) then $B\cup C = U$ and $bc = \prod\limits_{p_i\in B}p_i^{w_i}\prod\limits_{p_i\in C}p_i^{u_i} = a = \prod_{p_i\in U} p_i^{m_i}$. And if $p_i \in B\cap C$ then $w_i + u_i = m_i$. And if $p_j\in B\setminus C$ then $w_i = m_i$ and if $p_k \in C\setminus B$ then $u_i = m_i$.
4. So finally Case 4: If $a = bc$ and $\gcd(b,c) = 1$ then $B\cup C = U$ and $B\cap C = \emptyset$ so if we consider $U$ as our universal set we have $C = B^c$ and we have $b = \prod_{p_i\in B}p_i^{m_i}$ and $c = \prod_{p_j\in B^c} p_j^{m_j}$.

Now..... bang.

To determine a pair of $b,c$ so that $a = bc$ and $\gcd(b,c) = 1$, I must consider each prime factor, $p_i$ of $a$.

Either $p_i\mid b$ or $p_i \not \mid b$. If $p_i\mid b$ then $p_i^{m_i}\mid b$.

So $b$ is uniquely determined by which subset $B\subseteq U$ we use. And $c$ is uniquely determined by ... what the complement of $B$ is.

And....

$|\{(b,c): a = bc; \gcd(b,c)=1\}|=$

$|\{b:b\mid a, c=\frac ab; \gcd(b,c) =1\}|=$

$|\{\prod_{p_i\in B} p_i^{m_i}: B\subseteq U\}|=$

$|\{B: B\subseteq U\}|=$

$|\mathcal P(U)|=$

$2^{|U|} = 2^{\omega(a)}$.

Or if you are not that comfortable with set theory:

Remember. $\mathcal P(U)$ is the set of all subsets of $U$, and the number of subsets of $U$ are determined by considering each element of $x\in U$ and either $x$ may be in the subset or $x$ may not be in the subset. That is two choices for each element of $U$ so there are $2^{\text{number of elements of U}}$ possible subsets.

Likewise for each prime factor of $a$ we can either have $p|b$ or $p|c$ so there are two choices for each prime factor of $a$ and so there are $2^{\text{number of prime factors}}$ choices of pairs.

Answer 3

The easiest way to see this is to use kernels. If $$x=\prod_{i=1}^{\omega(x)}{p_i^{k_i}}$$ then the kernel is defined as $$\ker(x)=\prod_{i=1}^{\omega(x)}{p_i}$$ Plainly, $\omega(x)$ is the same for $x$ and $\ker(x)$. By the well known formula for the number of divisors, there are $2^{\omega(x)}$ divisors of $\ker(x)$.

Each divisor $d_i$ of $\ker(x)$ is the first member of an ordered pair $\Bigl (d_i,\ \frac{\ker(x)}{d_i}\Bigr)$ whose members are coprime. In particular, because $\ker(x)$ is square free, it is always the case that $$d_i\ne \frac{\ker(x)}{d_i}$$

Restoring the ignored exponents $k_i$ of the prime factors of $x$ back into the analysis changes nothing with respect to counting the ordered pairs possible.

Applying this to the question posed, let $a=x$, $b=d_i$ with relevant exponents restored, $c=\frac{\ker(x)}{d_i}$ with relevant exponents restored, and the proof is complete. There are $2^{\omega(a)}$ coprime ordered pairs $(b,c)$ of $a$