Finding all factors of a number

This algorithm can also be applied to imaginary quadratic rings which are UFDs

Given a number , whose prime power factorization is:

(1.1)

• Number of positive divisors of , including  and  itself:

(1.2)

• All positive factors of , including  and  itself:

Are found by taking all j-combinations of the terms of the product:

(1.3)

The details are explained in this example:

1. But how do you find all the 4-combinations of the terms of ?

2. How can you be sure you’ve found all of them?

This is what I do… using integral mixed-radix numbers.  There are probably other ways, having certain advantages, disadvantages…

I’m going to consider each of the four factors of  to represent different digit places in the mixed-radix system I’ll create.  Each summand within each term will be represented by a digit from the digit set corresponding to the radix, , chosen such that the number of summands equals .  I also order the radices in the mixed-radix number such that , i.e. such that the higher order digit places have the greatest radix and the lowest order places have the lowest.

In this example,

I create a mixed-radix number three of the lowest order places are of radix two and the highest order place is of radix three such that the  in the first term of the  factor set would correspond to a zero in the highest order digit place of the mixed-radix number, the  in the first term of the  factor set would correspond to a one in the highest order digit place, the  in the first term of the  factor set would correspond to a two in the highest order digit place,… the  in the second term of the  factor set would correspond to a zero in the second highest order digit place, etc.

Now finding all the combinations is as simple as counting up to  in the mixed-radix system just created.  The radix two places are like counting in base  and the radix three place is like counting in base ,…

or,

ð