# Ways of factorising into coprime factors

How many ways can we factorize a number, say $$676$$, into $$2$$ coprime factors? I tried this by factorizing $$676$$, and then counting by hit and trial, which worked just fine.

Is there another, more general method to do this? Because for very large numbers, doing it by trial and error will consume a lot of time. I don't want a code or an algorithm, any proof involving pure math will be appreciated.

• how large are we talking ? 20, 40, 200 digits ? known factorization ? or unknown ? – user645636 Apr 27 '19 at 23:54

First do the prime factorization: $$676=2^213^2$$, so it involves two primes $$2$$ and $$13$$. Of two factors, at least one must be divisible by each of the primes occurring. On the other hand, for co-prime factors, no prime is allowed to divide both factors. So if there are $$n$$ distinct primes involved and we count switched order as different factorizations, there are $$2^n$$ cop-prime factorizations into positive factors, coming from the $$2^n$$ possible subsets of the set of involved primes. In the example, we find four: $$676 = 1\cdot 2^213^2 = 2^2\cdot 13^2=13^2\cdot 2^2=2^213^2\cdot 1.$$ Less trivial, for $$n=100!$$, there are $$2^{25}$$ such factorizations because $$100!$$ is divisible by the $$25$$ primes below $$100$$ (and no other).