Which prime divides $18^{29}+1$?

Question

I am struggling with the following problem. Any help will be appreciated.

let $n= 18^{29}+1$. Prove that $n$ is divisible by $19$. Prove that if $ p $ is a prime which divides $n$, $p\ne19$,then $p \equiv 1\pmod{58}$. Is $n$ is divisible by $59$?

Thank you.

Answer 1

$$18^{29}\equiv -1\pmod{p}$$ implies that the order of $18$ in $\mathbb{F}_p^*$ is $2\cdot 29=58$ (since $18\not\equiv -1\pmod{p}$), from which $58\mid |\mathbb{F}_p^*|$ follows, i.e.: $$ 58\mid(p-1)\Longleftrightarrow p\equiv 1\pmod{58}.$$ For the second part, given that $p=59$, we have: $$ 18^{29} \equiv 18^{\frac{p-1}{2}}=\left(\frac{18}{59}\right)=\left(\frac{2}{59}\right)=-1$$ since $59\equiv 3\pmod{8}$, hence $59$ is a prime divisor of $18^{29}+1$.

^{Here $\left(\frac{\cdot}{\cdot}\right)$ is the Legendre symbol.}

Answer 2

$18^{29}\equiv (-1)^{29}=-1\pmod{19}$, so $18^{29}+1\equiv 0$, so $19$ divides your number.

$18^{29}=18\cdot(18^2)^{14}\equiv 18\cdot 29^{14}=18\cdot (29^2)^7\equiv 18\cdot 15^7=(18\cdot 15)\cdot(15^2)^3\equiv 34(-11)^3\equiv 34\cdot 26\equiv -1\pmod{59}$, so $59$ divides your number.

Using a computer program, one can find that there are only 3 prime factors: $$ 18^{29}+1 = 19·59·2255781524824231358697279947382689 $$