More specifically, for p > 2, if c = (a, b), then c^p = c mod p iff p is of the form p=4n+1. If p=4n+3, then c^p = c conjugate mod p. In this context, the conjugate of c is (a, p-b).

Why? Because i^4n+1 = i, but i^4n+3 = -i. The rest follows from the binomial proof of the little theorem (see https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem).