We interpret the question as asking for the number of *unordered pairs* of (distinct) divisors of $n$ that are relatively prime. For me it is easier to think in terms of ordered pairs.

So we are producing an ordered pair $(x,y)$ of relatively prime divisors of $n$. Examine one after the other the primes $p_i$. At each prime we have three types of choices: (i) assign $p_i$ to $x$; (ii) assign it to $y$; (iii) assign it to neither. If we assign $p_i$ to $x$, it can be done in $a_i$ ways, for the *power* of $p_i$ is at our disposal. Same with $y$. And we can assign to neither in $1$ way,for a total of $2a_i+1$. Thus the total number of ordered pairs is $P$, where
$$P=\prod_1^k(2a_i+1).$$
This includes the ordered pair $(1,1)$. Now for unordered pairs of distinct relatively prime divisors, there are $\frac{P-1}{2}$ possibilities.

**Remark:** If we want the product of the two factors to be $n$, the counting becomes much simpler. For ordered pairs, we choose a *subset* of the set of primes, and assign $p_i^{a_i}$ in the chosen subset to $x$, and assign the rest to $y$. There are $2^k$ ways of choosing $x$, and then $y$ is determined. So there are $2^k$ ordered pairs, and for $n\gt 1$, there are $2^{k-1}$ unordered pairs.

First, note that the positive integer $n = p_1^{\alpha_1} \cdots p_n^{\alpha_n}$ has

$$ \prod_{k=1}^n (\alpha_k + 1) = (\alpha_1 + 1) \cdot (\alpha_2 +1 ) \cdots (\alpha_k + 1)$$

factors.

So if your number $n$ has 72 positive divisors, then

$$ 72 = (\alpha_1 + 1) \cdot (\alpha_2 +1 ) \cdots (\alpha_k + 1) $$

where $k$ is the number of distinct primes in the prime factorization for $n$. You correctly noted that $72 = 2\cdot 2\cdot 2\cdot 3\cdot 3$. To get as many prime factors as possible, set $k = 5$ and $\alpha_1 = \alpha_2 = \alpha_3 = 1$ and $\alpha_4 = \alpha_5 = 2$. So for example your $n$ could be equal to $2^2 3^2 5^2 7^1 11^1$. Check that this has $72$ factors. For the minimum, just set $k=1$ and $\alpha_1 = 71$. So for example your $n$ could be $2^{71}$.

If you're just looking at composite factors, the process is similar. Since $n$ has $\prod_{k=1}^n (\alpha_k + 1) $ total factors, $k$ prime factors and $1$ (which is not composite) as factor, the number of composite factors is

$$ \left( \prod_{k=1}^n (\alpha_k + 1)\right) - (k+1). $$

The minimum is still $1$ (set $\alpha_1 = 73$).
For the maximum, you might need to do some casework. You want the number $72 + k + 1$ to have exactly $k$ prime factors. So $k$ cannot get too large. (See below for precise reasoning.) I tried the first $10$ values of $k$ and $k = 2$ (yielding $\prod_{k=1}^n (\alpha_k + 1) = 75$) was the only match. So the maximum number of prime factors for the case when you only want composite factors is $2$. An example number would be $2^{24} 3^2$. Check that this has $75$ total factors, three of which ($1$, $2$, $3$) are not composite.

Here is why $k$ cannot get too large in the composite case. Let $\{ p_1, \cdots, p_k, \cdots \}$ be the set of primes in order. So $p_1 = 2$, etc. Let the smallest number with exactly $k$ prime factors be $S_k = p_1 \cdots p_k$. So $S_1, S_2, S_3, S_4 = 2,6,30,210$. Note that $S_k \geq 2^k$.

We want $72 + k+1$ to have exactly $k$ prime factors, which means $72 + k + 1 \geq S_k$. But this means $72 + k + 1 \geq 2^k$, which is false for all $k \geq 7$. (Polynomials grow more slowly than exponentials.) So we can stop our search in the composite case for all $k \geq 7$.

## Best Answer

If you are able to factor the number (which I did with wolframalpha), you will get $$5\cdot 13\cdot 17\cdot 97\cdot 401\cdot 3041\cdot 14177$$ which immediately answers your question.

However most likely the intent of the person asking was for you to use indirect means to determine small factors. For example, to tell whether $5$ is a factor, we calculate the expression modulo 5: $$3^{32}-2^{32}\equiv 3^{32}-(-3)^{32}\equiv 3^{32}-(-1)^{32}3^{32}\equiv 0$$

Additional example as requested, modulo 13:

$$3^4= 81\equiv 3, 3^{16}=(3^4)^4\equiv 3, 3^{32}=(3^{16})^2\equiv 9$$ $$2^4=16\equiv 3, 2^{16}=(2^4)^4\equiv 3^4\equiv 3, 2^{32}=(2^{16})^2\equiv 9$$