Let $p$ be a prime and $a$ be an integer such that $0 \lt a \lt p$.
Is there a prime number, $q$, congruent to $a$ mod $p$ such that $q\lt p^2$?
I have checked that this is true for the first $3000$ primes. I also know to check if such a number less than $p^2$ is prime, I only need to check divisibility by primes less than p. I also know there are infinitely many primes congruent to $a$ mod $p$. I'm not sure how any of this helps.
The kind of result that you may be looking for is called Linnik's Theorem, which states that if $\gcd(a,d) = 1$, then the smallest prime $q$ congruent to $a \pmod d$ satisfies $q \ll d^L$, where $L$ is Linnik's constant. The smallest known value of Linnik's constant is $L = 5$, due to Xylouris in 2011.
That being said, the conjectured smallest possible value of $L$ is indeed $L = 2$, and with the Riemann Hypothesis, you can get an upper bound of $(\phi(d) \cdot \log d)^2$, where $\phi$ is Euler's totient function.