Showing that $38^n+31$ is prime I was reading a question in one of the previous pages, in searching for a proof I stumble across what seem like a contradiction. All I want is for someone to provide the missing link in my argument. 
The question

Find the least $n$ for which $38^n+31$ is prime. 

My attempt at a proof
If $38^n+31$ composite, then there exist at least a prime $p$ such that $p|38^n+31$. Now $\gcd(p,38)=1$, otherwise, $d=\gcd(p,38)=2$ or $19$ and $d|31$ a contradiction. Hence, by Fermat's Little Theorem; 
$38^{p-1} \equiv 1 \pmod p$, and for all positive integer $r$, $38^{r(p-1)} \equiv 1 \pmod p$. 
Hence, $38^{r(p-1)}+31 \equiv 32 \pmod p$, but $38^{r(p-1)}+31 \equiv 0 \pmod p$, because it's composite. It follows that $32 \equiv 0 \pmod p$ i.e $p|32$, a contradiction, and hence, the above expression cannot be composite (but inputing real values for $n$ shows that it is indeed composite).

For $38^x+31$, it is useful to note that the small primes divide $38^x+1$, as $x$ is odd or double-odd.  So, eg $3 \mid 38^x+1 $ for odd x.  $5 \mid 3d^x + 1$ for $x=2 \pmod 4$.  So after removing 3 and 5, one is left with $4 \mid x$.   
Running through the output of factor for $38^{4x}+31$, gives some rather difficult numbers to factorise.  for x=3, there are three divisors, 338431, 322249, and 83126873.  
It's probably not an easy row to hoe here.  There well may be primes, but these are not generally accessable.  factor seems to indicate that if it were prime, then $4x\gt 176$
