Order in the court!

First p=2 is clearly a solution so let's assume p is odd. Thus, $q \equiv 1 \pmod 4$ so the Legendre symbol gives $\left(\frac {-1} q\right) = +1$ and there exists

$1 < x \le \frac{q-1}2 = p-1, \quad x^2 + 1 \equiv 0 \pmod q.$

Since this means $x^4 \equiv 1 \pmod q$ , by the condition of the problem, we also have $x^4 \equiv 1 \pmod p$ . This means p divides $x^4 - 1 = (x-1)(x+1)(x^2 + 1)$ so either x = 1, p -1 or $x^2 + 1$ is a multiple of p .

Case 1 : x = 1, p -1. We already ruled out x=1. For x=p-1, we have $(p-1)^2 \equiv -1 \pmod q$ . Since $2(p-1) = q-1$ , this gives $(q-1)^2 \equiv -4 \pmod q$ . Expanding, we get $1 \equiv -4 \pmod q$ so q=5. This gives p=3.

Case 2 : $x^2 \equiv -1 \pmod p$ . Thus $x^2 + 1$ is a multiple of p and of q, and hence of pq. But this is impossible since

$1 \le x \le p-1 \implies x^2 + 1 \le (p-1)^2 + 1 < pq.$

Thus, the only solutions are $(p, q) = (2, 3), (3, 5)$ .

The cases $p=2$ and $p=3$ are quite trivial; they are solutions. We now assert $p>3$ .

Since $p$ is odd, we have $q \equiv 1 \ (\mathrm{mod}\ 4)$ . By virtue of the first supplement to the law of quadratic reciprocity, $-1$ is a quadratic residue modulo $q$ , i.e. there is a positive integer $x < q$ such that $x^2 \equiv -1 \ (\mathrm{mod}\ q)$ . Since $q-x$ has the same property, and either $x$ or $q-x$ must be smaller than $q/2$ , we can assert that $x \leq p-1$ , so $x$ is an integer that satisfies the condition for $a$ as stated in the problem.

We now have that $q$ divides $x^4-1 = (x-1)(x+1)(x^2+1)$ . If $p$ is to meet the condition of the problem statement, we must have that $p$ also divides $x^4-1$ . In order for that to be true, it must divide one of the factors given above.

If $p$ were to divide $x-1$ , we'd have $x=1$ , which is obviously impossible given the definition of $x$ . If $p$ were to divide $x^2+1$ , as $q$ does, then $x^2+1$ would be divisible by $pq$ . However, since $x < p < q$ , we obviously have $pq > x^2+1$ , so this is impossible. Therefore, the only remaining possibility is that $p$ divides $x+1$ , which implies $x=p-1$ .

By the definition of $x$ , we'd then necessarily have $(p-1)^2 \equiv -1 \ (\mathrm{mod}\ 2p-1)$ . Since $p$ is odd, $\frac12(p-1)$ is integer, and we have

$-1 \equiv (p-1)^2 \equiv (p-1)^2 - \frac12(p-1)(2p-1) \\ \quad \equiv \frac12(3p-1) \ (\mathrm{mod}\ 2p-1).$

But for $p>3$ , we have $-1 < \frac12(3p-1) < 2p-2$ , so this is never true.

Therefore, there are no solutions with $p>3$ . The only solutions are thus $\boxed{p=2}$ and $\boxed{p=3}$

If $p=2\Rightarrow q=3$ and for every $a$ integer from $1$ to $2-1=1$ we have $3|1^k-1=0\Rightarrow 2|1^k-1=0$ .

Now, be $p>2$ , $p$ is a odd prime, $p=2d+1\Rightarrow q=4d+1$ and $q$ is a prime number.

How we know, for every prime number of the form $P=4d+1$ , $-1$ is a quadractic residue $\pmod P$ .

Thus there exists a integer number $1\le x\le q$ such that $x^2\equiv -1\pmod {q}$ .

WLG, suppose that $x\le p-1$ because if $x>p-1\Rightarrow x\ge p$ , and we have $2p-1-x\le 2p-1-p=p-1$ and $(2p-1-x)^2\equiv (-x)^2\equiv x^2\equiv -1\pmod{q}$ .

Thus there exists $1\le m\le p-1$ such that $m^2\equiv -1\pmod {q}\Rightarrow m^4\equiv 1\pmod q$ and then $q|m^4-1$ .

By the enunciate we have $p|m^4-1=(m^2+1)(m+1)(m-1)$ as well.

If $p|m^2+1$ , we have $pq|m^2+1$ , where $p^2+1>m^2+1\ge pq=p(2p-1)>p*(p+1)>p^2+1$ since that $p>2$ , which is a contradiction.

And how $m-1<p$ we can conclude that $p|m+1\Rightarrow m\ge p-1\Rightarrow m=p-1$ since that $m\le p-1$ .

Thus $2p-1|m^2+1=(p-1)^2+1=p^2-2p+2$ and $2p-1|2p^2-p$ so we have $2p-1|2p^2-p -2*(p^2-2p+2)-(2p-1)=p-3$ and since that $0\le p-3<2p-1$ we must have $p-3=0\Rightarrow p=3, q=5$ .

In fact, for every positive integers $k, 1\le a\le 3-1=2$ , if $5|1^k-1=0, 2^k-1$ we have $2^k\equiv 1\pmod 5\Rightarrow ord_{5}2|k\Rightarrow 4|k, k=4M$ and thus $2^k-1\equiv 2^{4M}-1\equiv 16^M-1\equiv 1^M-1\equiv 0\pmod 3$ .

Thus $3|1^k-1=0, 2^{k}-1$ and so we have $2$ prime numbers with this property.

While the most elegant way to provide a solution is by using the general case, giving an extreme case trial could gives us a rough solution, in some cases.

We could deduce that $2p - 1 \mid a - 1$ , for $k = 1$ , the lowest positive integer. While using $a = 1$ will always provide problem requirement, the other extreme case, $a = p - 1$ , gives us $2p - 1 \mid p - 2$ .

From the last definition, we have either $2p - 1 \leq p - 2$ , because $p$ is a prime therefore it is or bigger than $2$ which is positive, or $p - 2 = 0$ , because $0$ is the only number that dividable by anything.

The latter is the solution, because the other gives us $p \leq -1$ which gives us a contradiction. Therefore, $p = 2$ is and the only solution.