Finding prime factors of large expression (without calculator) Show that: $5^3(5^3(253)+3)+1 = 19 \times 251 \times 829$.
I tried setting $n=5$, so that $253 = 23 \times 11 = (4n+3)(2n+1)$ and going from there, but the resulting polynomial in $n$ was $8n^6 + 10n^7 + 3n^6 + 3n^3 + 1$, which turns out to be irreducible over the integers, so this doesn't help at all.

My eye is drawn to the $253$ in the expression being close to the factor $251$ and the fact that $5^3$ is very close to half of $251$.  Given the known result I would write
$$5^3(5^3(253)+3)+1=5^3(5^3\cdot (251+2)+3)+1\\=5^6\cdot 251+5^3\cdot253+1\\=(5^6+5^3+1)251$$
then just compute $5^6+5^3+1=15625+125+1=15751$ and divide by $19$
