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

Question

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?

Answer 1

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.

Answer 2

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<p$. But if $q\equiv 1\pmod p$, then $p\mid q-1$, whence $p<q$, a contradiction.