# Do there exist (non-trivial) prime solutions to the equations $p^2 = 1$ mod $q$, $q = 1$ mod $p$?

Question: Do there exist odd primes $$p$$ and $$q$$ such that $$p^2 = 1 + qt,\quad q = 1 + ps$$ for some positive integers $$s,t$$? I've written some code which has verified that no solutions exist for $$p,q < 30,000$$ but don't know how to go about a formal proof.

Background:

To practice group theory, I decided to try and classify small groups on my own. I got stuck trying to classify groups of order $$p^2q$$ for distinct primes $$p,q$$.

Suppose $$G$$ has order $$p^2q$$ for distinct primes $$p,q$$. By Sylow theorems, there exists a Sylow $$p$$ subgroup of order $$p^2$$, and a Sylow $$q$$ subgroup of order $$q$$. We can express $$G$$ as a semidirect product if at least one of them is normal. A test for normality is if the Sylow subgroups are unique. We have the following:

$$|\text{Syl}_p(G)| \in \{1,q\}$$

$$|\text{Syl}_p(G)| \equiv 1\mod p$$

$$|\text{Syl}_q(G)| \in \{1,p,p^2\}$$

$$|\text{Syl}_q(G)| \equiv 1\mod q$$

Unlike the case of groups of order $$pq$$, it is not immediately clear from these facts that one of the Sylow subgroups is unique. Namely, the following situation might occur:

$$p < q < p^2$$, such that: $$|\text{Syl}_p(G)| = q$$, $$s$$ is a positive integer with $$q = 1 + ps$$, $$|\text{Syl}_q(G)| = p^2$$, $$t$$ is a positive integer with $$p^2 = 1 + qt$$.

In fact, a concrete example of this is the following:

$$p = 2, q = 3, t = s = 1$$.

However, when I tried to find other primes $$p,q$$ satisfying the equations "There exists $$s,t > 0$$ such that $$p^2 = 1 + qt, q = 1 + ps$$", I couldn't find any. Are there any solutions to these equations other than the one I found?

I'm a geometer so I have no idea I how do anything with diophantine equations, so all I could do was write code to search for solutions. My code has verified that there are no solutions where $$p$$ and $$q$$ are odd primes less than 30,000. Does someone have a nice proof that no non-trivial solutions exist?

If $$p^2=1\mod q$$ then $$p=\pm 1\mod q$$.

Suppose that $$p=1\mod q$$. Then, $$p=1+qt$$ for some $$t\in\mathbb{Z}$$. Of course, it's clear, in fact, that $$t\geqslant 0$$. Similarly, since $$q=1\mod p$$ we can write $$q=1+ps$$ for some integer $$s\geqslant 0$$. So, then

$$p=1+qt=1+(1+ps)t=1+t+ps$$

Since $$t,s\geqslant 0$$ this is impossible.

If $$p=-1\mod q$$ then we can write $$p=qt-1$$ for some $$t\geqslant 0$$. Again, we can write $$q=1+ps$$ for some $$s\geqslant 0$$. Then,

$$p=qt-1=(1+ps)t-1=1+t+ps-1$$

The only possible solution to this is $$s=t=1$$. This says that $$p=q-1$$ and $$q=1+p$$ which of course is impossible since $$p$$ and $$q$$ are odd.

This is just a slightly simplified version of Alex Youcis's solution.

If $$p^2\equiv 1\pmod q$$, then $$q\mid(p-1)(p+1)$$, whence $$q\mid(p-1)$$ or $$q\mid(p+1)$$; in either case, $$q. But if $$q\equiv 1\pmod p$$, then $$p\mid q-1$$, whence $$p, a contradiction.