Finding prime factors of large expression (without calculator)

Question

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.

Answer 1

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$

Answer 2

Divide $19*251*829$ by $5$ and take remainders.

$19*251*829 = 19*250*829 + 19*830 -20 + 1=$

$5(19*50*829 + 19*166 -4) + 1=$

$5(19*50*829 + 19*165 + 20 -5) + 1=$

$5(19*10*829 + 19*33 + 3) + 1=$

$5^2(19*10*829 + 20*33 -30) + 1=$

$5^3(19*2*829 + 4*33 -6) + 1=$

$5^3(19*2*830 -20*2 + 2 + 5*33 - 30 - 3-6) + 1=$

$5^3(19*2*830 - 20*2 + 5*33 -30 -10 +3) + 1=$

$5^3(5(19*2*166 - 4*2 + 33 -8) +3) + 1=$

$5^3(5(19*2*165 + 20*2 -10 + 30 -5)+3) + 1=$

$5^3(5^2(19*2*33 + 4*2 + 3)+3) + 1=$

$5^3(5^2(19*2*33 + 11)+3) +1=$

$5^3(5^2(20*2*33 - 2*33+11)+3)+1=$

$5^3(5^2(20*2*33 - 2*30-6+11)+3)+1=$

$5^3(5^3(4*2*33 -2*6 +1)+3)+1=$

$5^3(5^3(5*2*33 - 2*30 - 3*5 -3 +1)+3)+1=$

$5^3(5^3(330 - 60 -15 -2)+3)+1=$

$5^3(5^3(253)+3)+1=$