Let be a positive integer. All numbers which are coprime to all satisfy . Find the maximum possible value of .
Problem 1203
Official solution
1. **Determine the constraints on being even:**
- Since is even, we consider the highest power of 2 dividing . Let denote the highest power of 2 dividing .
- Suppose . Then is divisible by 16. We need for all coprime to 16.
- Consider , which is coprime to 16. We have:
- This is a contradiction since . Therefore, .
2. **Check being divisible by 8:**
- If , then is divisible by 8. We need for all coprime to 8.
- For any coprime to 8, is odd. We have:
- Thus, holds for all coprime to 8.
3. Check divisibility by other primes:
- Suppose . We need for all coprime to 5.
- Consider , which is coprime to 5. We have:
- This is a contradiction since . Therefore, cannot be divisible by 5.
4. **Determine the maximum with the given constraints:**
- Since must be coprime to 5 and divisible by 8, we consider the prime factors of other than 2 and 5.
- Let . We need to check if for all coprime to .
- For :
- We need for all coprime to 504.
- By the Chinese Remainder Theorem, it suffices to check , , and .
5. Verify the conditions:
- For coprime to 8, holds as shown earlier.
- For coprime to 9, holds because the order of any element modulo 9 divides .
- For coprime to 7, holds because the order of any element modulo 7 divides .
Thus, satisfies all the conditions.
The final answer is