Problem:
Find the number of functions from the set to itself such that, for all , all three of the following conditions are satisfied:
(i) If , then ;
(ii) If , then ; and
(iii) If , then .
Solution
Solution:
Note that, from (i), our function is completely determined by ; i.e., . Then, from (i) and (ii), we need that if ; otherwise, if but for any . Thus, if , we need that for any . If 2021)=d>1f(a) a f(1) 2021). As we just established, this is not allowed. Hence, 2021)=1.
Moreover, from (iii), we need that if ; in other words, if . By similar reasoning to earlier, suppose that 2021 a(f(1)-1)f(a)=a as well.
We count the number of integers that satisfy both these conditions. We use complementary counting here; thus, we start by counting those that fail to satisfy at least one condition. Indeed, we count the number of values of that are not coprime to 2021. Either they are divisible by 43, or 47, or both. Since only 0 is divisible by both, by the principle of inclusion and exclusion, there are possible values of so that is not coprime to 2021. By the same reasoning, there are also 89 possible values of such that is not coprime to 2021. Finally, we count the values of for which neither nor is coprime to 2021. This happens precisely when and , or and . By the Chinese remainder theorem, each of these possibilities gives one value of . Thus, by the principle of inclusion and exclusion, there are such values of that fail to satisfy at least one condition. This gives us possible values of , and thus possible functions .