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.

  • $\begingroup$ how large are we talking ? 20, 40, 200 digits ? known factorization ? or unknown ? $\endgroup$ – Roddy MacPhee Apr 27 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).

  • $\begingroup$ Assuming that a•b is same as b•a , there will be 2ⁿ⁻¹ ways, right? $\endgroup$ – user226375 Apr 27 at 12:42
  • 2
    $\begingroup$ Why do you count switched order as different factorisations? Is there a specific reason for preferring this? $\endgroup$ – 雨が好きな人 Apr 27 at 13:03

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.