Compute the number of permutations of the set so that for all (not necessarily distinct) where is prime, is prime.
Solution
Since sends pairs with prime to pairs with prime, and there are only finitely many such pairs, we conclude that if is composite, then so is . Also note that is prime because is prime. Thus, . Now, since , and are all prime, we know that , and are all even. Additionally, since , and are all composite, it is not hard to see that must also be even. Therefore preserves parity. Now, draw a bipartite graph between the odd and even numbers where we have an edge between and if and only if composite. We now only need to compute automorphisms of this graph that fix 1. Note that the edges are precisely , and . Since 1 is a fixed point of , we know that fixes , and 2. Additionally, and . We can swap 3 and 9, as well as 4 and 10. Thus, there are possible permutations.