Browse · MATH
Printjmc
algebra senior
Problem
Let be a function taking the positive integers to the positive integers, such that for all positive integers and Find the smallest possible value of
Solution
Setting we get Thus, is a fixed point for all positive integers (In other words, satisfies )
Setting we get If is a fixed point (which we know exists), then so Hence, for all positive integer This equation tells us that the function is surjective.
Furthermore, if then so Therefore, is injecitve, which means that is bijective.
Replacing with in the given functional equation yields Since for all positive integers and
Taking in we get so
Recall that for a positive integer stands for the number of divisors of Thus, given a positive integer there are ways to write it in the form where and are positive integers. Then Since is a bijection, each way of writing as the product of two positive integers gives us at least one way of writing as the product of two positive integers, so Replacing with we get But so Therefore, for all positive integers
If is a prime then This means is also prime. Hence, if is prime, then is also prime.
Now, We know that both and are prime.
If then so and If then If then So must be at least 18. To show that the 18 is the smallest possible value of we must construct a function where Given a positive integer take the prime factorization of and replace every instance of 2 with 223, and vice-versa (and all other prime factors are left alone). For example, It can be shown that this function works. Thus, the smallest possible value of is
Setting we get If is a fixed point (which we know exists), then so Hence, for all positive integer This equation tells us that the function is surjective.
Furthermore, if then so Therefore, is injecitve, which means that is bijective.
Replacing with in the given functional equation yields Since for all positive integers and
Taking in we get so
Recall that for a positive integer stands for the number of divisors of Thus, given a positive integer there are ways to write it in the form where and are positive integers. Then Since is a bijection, each way of writing as the product of two positive integers gives us at least one way of writing as the product of two positive integers, so Replacing with we get But so Therefore, for all positive integers
If is a prime then This means is also prime. Hence, if is prime, then is also prime.
Now, We know that both and are prime.
If then so and If then If then So must be at least 18. To show that the 18 is the smallest possible value of we must construct a function where Given a positive integer take the prime factorization of and replace every instance of 2 with 223, and vice-versa (and all other prime factors are left alone). For example, It can be shown that this function works. Thus, the smallest possible value of is
Final answer
18