How to find pairs of primes satisfying certain properties?

Question

This question is related to a question of mine on MathOverflow.

Can you find an infinite sequence of pairs $p,q$ of primes satisfying the following conditions?

• $p$ and $q$ are distinct with $p<q$
• $p\geq 73$
• both $p$ and $q$ are congruent to $1$ modulo $4$
• $q$ is a quadratic residue modulo $p$
• (optional) $p$ should be as small as possible (for example $p=73$ would be great)

The first example would be $p=73$ and $q=89$.

Answer 1

Yes, even with $p = 73$. The conditions that $q$ be a quadratic residue mod $p$ and congruent to $1$ mod $4$ are congruence conditions; by the Chinese remainder theorem, you can express them as one congruence. Now Dirichlet's theorem tells you there are infinitely many primes in the arithmetic progression determined by this congruence.