Number theoryDifficulty 6.9National olympiadProve it
Prove that for all positive integers n, 169 divides 21n2+89n+44 if 13 divides n2+3n+51.
Solution
1. Given Conditions: - We need to prove that for all positive integers n, 169 divides 21n2+89n+44 if 13 divides n2+3n+51.
2. Condition Analysis: - If 13 divides n2+3n+51, then n2+3n+51≡0(mod13).
3. Simplify the Congruence: - We need to find n such that n2+3n+51≡0(mod13). - Simplify 51mod13: 51÷13=3remainder12⇒51≡12(mod13) - Thus, the congruence becomes: n2+3n+12≡0(mod13)
4. Solve the Quadratic Congruence: - We solve n2+3n+12≡0(mod13). - The roots of the quadratic equation n2+3n+12=0 can be found using the quadratic formula: n=2a−b±b2−4ac where a=1, b=3, and c=12. - Calculate the discriminant: Δ=b2−4ac=32−4⋅1⋅12=9−48=−39 - Since we are working modulo 13: −39≡10(mod13) - The discriminant modulo 13 is 10, and we need to find the square root of 10 modulo 13. By inspection or using quadratic reciprocity, we find that 10 is a quadratic residue modulo 13, and its square roots are 6 and 7 (since 62≡36≡10(mod13) and 72≡49≡10(mod13)).
5. Find the Roots: - Using the roots 6 and 7: n≡2−3±6(mod13)andn≡2−3±7(mod13) - Simplify the roots: n≡23(mod13)andn≡2−9(mod13) - Since 2 has an inverse modulo 13 (which is 7 because 2⋅7≡1(mod13)): n≡3⋅7≡21≡8(mod13)andn≡−9⋅7≡−63≡10(mod13) - Thus, n≡8(mod13) or n≡10(mod13).
6. **General Form of n:** - Let n=13k+8 or n=13k+10 for some integer k.
7. **Substitute n into 21n2+89n+44:** - For n=13k+8: 21(13k+8)2+89(13k+8)+44 - Expand and simplify: 21(169k2+208k+64)+89(13k+8)+44 =21⋅169k2+21⋅208k+21⋅64+89⋅13k+89⋅8+44 =21⋅169k2+21⋅208k+1344+1157k+712+44 =21⋅169k2+(21⋅208+1157)k+(1344+712+44) =21⋅169k2+169⋅23k+2100 =169(21k2+23k+12) - Clearly, 169 divides 21n2+89n+44.
8. Conclusion: - The same steps can be applied for n=13k+10 and will yield a similar result.
■
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.