Maths Olympiad Prep

Library / /213 of 520

Number theory Difficulty 6.8 National olympiad Prove it

For prime p1(mod7)p\equiv 1\pmod{7} , prove that there exists some positive integer mm such that m3+m22m1m^3+m^2-2m-1 is a multiple of pp.

Solution

To prove that for a prime p1(mod7) p \equiv 1 \pmod{7} , there exists some positive integer m m such that m3+m22m1 m^3 + m^2 - 2m - 1 is a multiple of p p , we can proceed as follows:

1. Understanding the Problem:
We need to show that there exists an integer m m such that p p divides m3+m22m1 m^3 + m^2 - 2m - 1 . This means we need to find m m such that:
m3+m22m10(modp) m^3 + m^2 - 2m - 1 \equiv 0 \pmod{p}

2. Cyclotomic Polynomial Insight:
Since p1(mod7) p \equiv 1 \pmod{7} , p p can be expressed in the form p=7k+1 p = 7k + 1 for some integer k k . This implies that p p has a primitive 7th root of unity modulo p p . The 7th cyclotomic polynomial is given by:
Φ7(x)=x6+x5+x4+x3+x2+x+1 \Phi_7(x) = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
We need to relate this polynomial to our given polynomial m3+m22m1 m^3 + m^2 - 2m - 1 .

3. Substitution:
To make the cyclotomic polynomial appear, we use the substitution m=x+1x m = x + \frac{1}{x} . This substitution is motivated by the fact that the roots of the cyclotomic polynomial are of the form e2πik/7 e^{2\pi i k / 7} for k=0,1,,6 k = 0, 1, \ldots, 6 .

4. Polynomial Transformation:
Substitute m=x+1x m = x + \frac{1}{x} into the polynomial m3+m22m1 m^3 + m^2 - 2m - 1 :
m3=(x+1x)3=x3+3x+3x+1x3 m^3 = \left( x + \frac{1}{x} \right)^3 = x^3 + 3x + \frac{3}{x} + \frac{1}{x^3}
m2=(x+1x)2=x2+2+1x2 m^2 = \left( x + \frac{1}{x} \right)^2 = x^2 + 2 + \frac{1}{x^2}
2m=2(x+1x)=2x2x -2m = -2 \left( x + \frac{1}{x} \right) = -2x - \frac{2}{x}
1=1 -1 = -1
Combining these, we get:
m3+m22m1=(x3+1x3+3x+3x)+(x2+1x2+2)(2x+2x)1 m^3 + m^2 - 2m - 1 = \left( x^3 + \frac{1}{x^3} + 3x + \frac{3}{x} \right) + \left( x^2 + \frac{1}{x^2} + 2 \right) - \left( 2x + \frac{2}{x} \right) - 1
Simplifying, we get:
m3+m22m1=x3+1x3+x2+1x2+x+1x+11 m^3 + m^2 - 2m - 1 = x^3 + \frac{1}{x^3} + x^2 + \frac{1}{x^2} + x + \frac{1}{x} + 1 - 1
=x3+1x3+x2+1x2+x+1x = x^3 + \frac{1}{x^3} + x^2 + \frac{1}{x^2} + x + \frac{1}{x}

5. **Existence of a a with Order 7 Modulo p p :**
Since p1(mod7) p \equiv 1 \pmod{7} , there exists an integer a a such that a a has order 7 modulo p p . This means a71(modp) a^7 \equiv 1 \pmod{p} and ak≢1(modp) a^k \not\equiv 1 \pmod{p} for 1k<7 1 \leq k < 7 .

6. Conclusion:
By choosing x=a x = a , where a a is a primitive 7th root of unity modulo p p , we ensure that x71(modp) x^7 \equiv 1 \pmod{p} . Therefore, the polynomial m3+m22m1 m^3 + m^2 - 2m - 1 will be zero modulo p p for some m m .

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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