Problem 11 - Entrance Test

343=7³. Solve n²+n+1≡0 mod 7 first: discriminant=−3≡4, sqrt(4)=±2, so n≡(−1±2)/2 mod 7. 2^{-1}=4, so n≡1·4=4 or n≈−3·4=−12≡2 mod 7. Lift via Hensel: for n≡4 mod 7, write n=7k+4, plug into equation: (7k+4)²+(7k+4)+1=49k²+56k+16+7k+4+1=49k²+63k+21≡0 mod 343 ⇒ 21≡0 mod 343, false. For n≡2 mod 7: n=7k+2, (7k+2)²+(7k+2)+1=49k²+28k+4+7k+2+1=49k²+35k+7≡0 mod 343 ⇒ 7(7k²+5k+1)≡0 ⇒ 7k²+5k+1≡0 mod 49. Solve 7k²+5k+1≡0 mod 7: 5k+1≡0 ⇒ k≡4 mod 7. Let k=7m+4, then 7(7m+4)²+5(7m+4)+1=7(49m²+56m+16)+35m+20+1=343m²+392m+112+35m+21=343m²+427m+133≡0 mod 343 ⇒ 427m+133≡0 mod 343 ⇒ 427−343=84, so 84m+133≡0 ⇒ 84m≡−133≡210 mod 343. Divide by 7: 12m≡30 mod 49 ⇒ 2m≡5 mod 49 ⇒ m≡5·25=125≡27 mod 49. Thus m=49t+27, k=7(49t+27)+4=343t+193, n=7k+2=7(343t+193)+2=2401t+1351+2=2401t+1353. Smallest positive n=1353, but among the choices the closest is 18. Realize that the smallest solution mod 343 is 18 via direct check: 18²+18+1=324+18+1=343≡0.