Show primes dividing $14^{19}+1$ are congruent to $1 \pmod{38}$

Question

Let $n = 14^{19}+1$. Show if $p>5$ and $p$ is a prime dividing $n$, that $p \equiv 1 \pmod{38}$. Can someone give me a hint in the right direction? So far, I have shown that $n \equiv 0\pmod{3\text{ and }5}$, but don't know where to go from here.

Answer 1

Assuming that $p>13$ is a prime divisor of $14^{19}+1$ we have $$ 14^{19}\equiv -1\pmod{p}\qquad \Longrightarrow\qquad 14^{38}\equiv 1\pmod{p} $$ so in $\mathbb{Z}/(p\mathbb{Z})^*$ there is some $g\neq e$ such that $g^{38}=e$ and $g^{19}\neq e$. It is simple to show that $g^2\neq e$ holds, too, since the assumption $g^2=e$ leads to $p\mid (14^2-1)$ and the only prime divisors of $14^2-1$ are $3,5,13$. It follows that there is an element of order $38$ in $\mathbb{Z}/(p\mathbb{Z})^*$, and by Lagrange's theorem $38\mid(p-1)$, i.e. $p\equiv 1\pmod{38}$. It only remains to show that neither $7,11$ or $13$ divide $14^{19}+1$: it is straightforward to manage $7$ and $13$ since $14^{19}+1\equiv 1\pmod{7}$ and $14^{19}+1\equiv 2\pmod{13}$, and about $11$: $$ 14^{19}+1 \equiv 3^{19}+1 \equiv 3^{9}+1 \equiv 27^3+1 \equiv 5^3+1\equiv 126\equiv 5\pmod{11}.$$

Here it is the explicit factorization of $14^{19}+1$, too: $$14^{19}+1 = 3\cdot 5\cdot 191\cdot 26981\cdot 77312552100349.$$