Let denote the set of integers considered modulo (hence has elements). Find all positive integers for which there exists a bijective function , such that the 101 functions
are all bijections on .
[i]Ashwin Sah and Yang Liu[/i]
Let denote the set of integers considered modulo (hence has elements). Find all positive integers for which there exists a bijective function , such that the 101 functions
are all bijections on .
[i]Ashwin Sah and Yang Liu[/i]
Let denote the set of integers considered modulo . We need to find all positive integers for which there exists a bijective function , such that the 101 functions
are all bijections on .
We claim that the answer is all numbers relatively prime to . The construction is to let be the identity function.
To prove this, we need to show that if is relatively prime to , then such a bijective function exists. Conversely, if shares a common factor with , then no such bijective function can exist.
### Proof:
1. **Existence for relatively prime to :**
- Let . Then the functions for are all bijections if is invertible modulo . Since is relatively prime to , all integers from 1 to 101 are invertible modulo . Therefore, each function is a bijection.
2. **Non-existence for not relatively prime to :**
- Suppose has a prime factor . Consider the sum of the functions over all . By properties of bijections, this sum must be congruent modulo . However, if divides , then the sums of powers of modulo will not satisfy the necessary conditions for all , leading to a contradiction.
Thus, the positive integers for which there exists a bijective function such that the 101 functions are all bijections are exactly those integers that are relatively prime to .
The answer is: .