Maths Olympiad Prep

Library / /268 of 520

Number theory Difficulty 6.9 National olympiad Prove it

Prove that for all positive integers nn, 169169 divides 21n2+89n+4421n^2 + 89n + 44 if 1313 divides n2+3n+51n^2 + 3n + 51.

Solution

1. Given Conditions:
- We need to prove that for all positive integers n n , 169 169 divides 21n2+89n+44 21n^2 + 89n + 44 if 13 13 divides n2+3n+51 n^2 + 3n + 51 .

2. Condition Analysis:
- If 13 13 divides n2+3n+51 n^2 + 3n + 51 , then n2+3n+510(mod13) n^2 + 3n + 51 \equiv 0 \pmod{13} .

3. Simplify the Congruence:
- We need to find n n such that n2+3n+510(mod13) n^2 + 3n + 51 \equiv 0 \pmod{13} .
- Simplify 51mod13 51 \mod 13 :
51÷13=3remainder125112(mod13) 51 \div 13 = 3 \quad \text{remainder} \quad 12 \quad \Rightarrow \quad 51 \equiv 12 \pmod{13}
- Thus, the congruence becomes:
n2+3n+120(mod13) n^2 + 3n + 12 \equiv 0 \pmod{13}

4. Solve the Quadratic Congruence:
- We solve n2+3n+120(mod13) n^2 + 3n + 12 \equiv 0 \pmod{13} .
- The roots of the quadratic equation n2+3n+12=0 n^2 + 3n + 12 = 0 can be found using the quadratic formula:
n=b±b24ac2a n = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}
where a=1 a = 1 , b=3 b = 3 , and c=12 c = 12 .
- Calculate the discriminant:
Δ=b24ac=324112=948=39 \Delta = b^2 - 4ac = 3^2 - 4 \cdot 1 \cdot 12 = 9 - 48 = -39
- Since we are working modulo 13 13 :
3910(mod13) -39 \equiv 10 \pmod{13}
- The discriminant modulo 13 13 is 10 10 , and we need to find the square root of 10 10 modulo 13 13 . By inspection or using quadratic reciprocity, we find that 10 10 is a quadratic residue modulo 13 13 , and its square roots are 6 6 and 7 7 (since 623610(mod13) 6^2 \equiv 36 \equiv 10 \pmod{13} and 724910(mod13) 7^2 \equiv 49 \equiv 10 \pmod{13} ).

5. Find the Roots:
- Using the roots 6 6 and 7 7 :
n3±62(mod13)andn3±72(mod13) n \equiv \frac{-3 \pm 6}{2} \pmod{13} \quad \text{and} \quad n \equiv \frac{-3 \pm 7}{2} \pmod{13}
- Simplify the roots:
n32(mod13)andn92(mod13) n \equiv \frac{3}{2} \pmod{13} \quad \text{and} \quad n \equiv \frac{-9}{2} \pmod{13}
- Since 2 2 has an inverse modulo 13 13 (which is 7 7 because 271(mod13) 2 \cdot 7 \equiv 1 \pmod{13} ):
n37218(mod13)andn976310(mod13) n \equiv 3 \cdot 7 \equiv 21 \equiv 8 \pmod{13} \quad \text{and} \quad n \equiv -9 \cdot 7 \equiv -63 \equiv 10 \pmod{13}
- Thus, n8(mod13) n \equiv 8 \pmod{13} or n10(mod13) n \equiv 10 \pmod{13} .

6. **General Form of n n :**
- Let n=13k+8 n = 13k + 8 or n=13k+10 n = 13k + 10 for some integer k k .

7. **Substitute n n into 21n2+89n+44 21n^2 + 89n + 44 :**
- For n=13k+8 n = 13k + 8 :
21(13k+8)2+89(13k+8)+44 21(13k + 8)^2 + 89(13k + 8) + 44
- Expand and simplify:
21(169k2+208k+64)+89(13k+8)+44 21(169k^2 + 208k + 64) + 89(13k + 8) + 44
=21169k2+21208k+2164+8913k+898+44 = 21 \cdot 169k^2 + 21 \cdot 208k + 21 \cdot 64 + 89 \cdot 13k + 89 \cdot 8 + 44
=21169k2+21208k+1344+1157k+712+44 = 21 \cdot 169k^2 + 21 \cdot 208k + 1344 + 1157k + 712 + 44
=21169k2+(21208+1157)k+(1344+712+44) = 21 \cdot 169k^2 + (21 \cdot 208 + 1157)k + (1344 + 712 + 44)
=21169k2+16923k+2100 = 21 \cdot 169k^2 + 169 \cdot 23k + 2100
=169(21k2+23k+12) = 169(21k^2 + 23k + 12)
- Clearly, 169 169 divides 21n2+89n+44 21n^2 + 89n + 44 .

8. Conclusion:
- The same steps can be applied for n=13k+10 n = 13k + 10 and will yield a similar result.

\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.