Olympiad Maths Prep

Track / Stage 6 / 203 of 400 #1203 of 2000

Problem 1203

National olympiad, first round
Number theory Difficulty 6.3 Find the answer

Let nn be a positive integer. All numbers mm which are coprime to nn all satisfy m61(modn)m^6\equiv 1\pmod n. Find the maximum possible value of nn.

Official solution

1. **Determine the constraints on n n being even:**
- Since n n is even, we consider the highest power of 2 dividing n n . Let v2(n) v_2(n) denote the highest power of 2 dividing n n .
- Suppose v2(n)4 v_2(n) \geq 4 . Then n n is divisible by 16. We need m61(mod16) m^6 \equiv 1 \pmod{16} for all m m coprime to 16.
- Consider m=5 m = 5 , which is coprime to 16. We have:
56=156259(mod16) 5^6 = 15625 \equiv 9 \pmod{16}
- This is a contradiction since 56≢1(mod16) 5^6 \not\equiv 1 \pmod{16} . Therefore, v2(n)3 v_2(n) \leq 3 .

2. **Check n n being divisible by 8:**
- If v2(n)=3 v_2(n) = 3 , then n n is divisible by 8. We need m61(mod8) m^6 \equiv 1 \pmod{8} for all m m coprime to 8.
- For any m m coprime to 8, m m is odd. We have:
m21(mod8)    m6=(m2)313=1(mod8) m^2 \equiv 1 \pmod{8} \implies m^6 = (m^2)^3 \equiv 1^3 = 1 \pmod{8}
- Thus, m61(mod8) m^6 \equiv 1 \pmod{8} holds for all m m coprime to 8.

3. Check divisibility by other primes:
- Suppose 5n 5 \mid n . We need m61(mod5) m^6 \equiv 1 \pmod{5} for all m m coprime to 5.
- Consider m=3 m = 3 , which is coprime to 5. We have:
36=7294(mod5) 3^6 = 729 \equiv 4 \pmod{5}
- This is a contradiction since 36≢1(mod5) 3^6 \not\equiv 1 \pmod{5} . Therefore, n n cannot be divisible by 5.

4. **Determine the maximum n n with the given constraints:**
- Since n n must be coprime to 5 and divisible by 8, we consider the prime factors of n n other than 2 and 5.
- Let n=23327 n = 2^3 \cdot 3^2 \cdot 7 . We need to check if m61(modn) m^6 \equiv 1 \pmod{n} for all m m coprime to n n .
- For n=504 n = 504 :
504=23327 504 = 2^3 \cdot 3^2 \cdot 7
- We need m61(mod504) m^6 \equiv 1 \pmod{504} for all m m coprime to 504.
- By the Chinese Remainder Theorem, it suffices to check m61(mod8) m^6 \equiv 1 \pmod{8} , m61(mod9) m^6 \equiv 1 \pmod{9} , and m61(mod7) m^6 \equiv 1 \pmod{7} .

5. Verify the conditions:
- For m m coprime to 8, m61(mod8) m^6 \equiv 1 \pmod{8} holds as shown earlier.
- For m m coprime to 9, m61(mod9) m^6 \equiv 1 \pmod{9} holds because the order of any element modulo 9 divides ϕ(9)=6 \phi(9) = 6 .
- For m m coprime to 7, m61(mod7) m^6 \equiv 1 \pmod{7} holds because the order of any element modulo 7 divides ϕ(7)=6 \phi(7) = 6 .

Thus, n=504 n = 504 satisfies all the conditions.

The final answer is 504 \boxed{504}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.