Let . Determine the number of functions satisfying the following conditions.
(i) ;
(ii) is bijective (i.e. for every in , the equation has exactly one solution);
(iii) for every in .
Here and denote the uniquely determined positive integers such that , and is as small as possible. (For instance, , and .)
Solution
There are 348364800 such functions.
We first claim that condition (iii) can be replaced by the completely multiplicative condition. This means
for any distinct primes and positive integers . We prove this by induction on .
The base cases hold trivially. Assume the result holds whenever the sum of exponents is less than . Consider where . Note that is composite, and so . Since , the sum of exponents in the prime factorizations of and are both smaller than . Thus, by the inductive hypothesis, and can be decomposed into a product of 's. Clearly, this proves
By induction, we have shown that is completely multiplicative. Conversely, if is completely multiplicative, condition (iii) holds trivially.
Let be the set of all primes from 1 to 100, and let be the set of all composites. For any , since , we must have . Therefore, . This implies . As , by the bijective condition, we must have . Thus, it remains to assign distinct prime values to for . Afterwards we can easily compute by the completely multiplicative condition, while the bijective condition is always satisfied.
Now, the only constraint is that for any . For example, since
and , we must have . Similarly, by considering , we can prove that . Next, since
we have , and hence . Similarly, by considering and , we can prove that for .
Next, by considering and , we can only prove that . Therefore, we have . There is no further constraint on and since we can verify that for any being multiples of 17 or 19, as long as .
Similarly, by considering , we find that .
By considering and , we find that .
By considering and , we find that can be mapped to any permutation of themselves.
Lastly, the images of can be any permutation of themselves.
In view of the above arguments, we can choose the images within each group in an arbitrary way. Each choice corresponds to a unique function satisfying all requirements. Therefore, the number of such functions is
2! 2! 4! 10! = 348364800.