This is an extension of a previous question (Maximizing $\frac{\gcd(m,n)}{k}.$) which is interesting.
Let $m=(p-1)^{p-1}+(p-1)!$ and let $n=((p-1)^{p-1}-(p-1)!)^{p-1}-1.$
For which odd primes is $\gcd(m,n)\neq p?$
For simplicity, let $d=\gcd(m,n).$ Then, we very easily see that $p\mid d.$ However, through some experimentation on Wolfram Alpha, I found that for most primes, $d=p,$ but not for all. The first few primes that satisfy the requirements are $S=\{5,31,41,43,53,71,97,\ldots\}$ (I hope I didn't miss one). This is not a known sequence according to OEIS. I am curious how exactly to find these primes.
Two other things to note. First, we see that if $p\in S$ then $d=p(2p-3)$ and $2p-3$ is prime. However, not all primes $p$ such that $2p-3$ is prime are in $S$, for example $p=13$ and $2p-3=23.$
Moreover, I also found that if $p\in S$ then it is not necessarily true that $2p-3\in S.$ Indeed, $2p-3\not \in S$ for the first few $p\in S,$ but the first example is $97$ and $191,$ which are both in $S.$
Edit: As noted by user dezdichado in the comments, we see that $S\subset \{p \in\mathbb{P}\mid 2p-3 \in \mathbb{P}\},$ where $\mathbb{P}$ is the set of prime numbers. Obviously, this is a weaker condition, but it would be interesting to see the proof of this.