# Some congruence problem

In my work, I reached the following congruence. Here, $$\square_1$$, $$\square_2$$ are square numbers and $$p$$ denotes the prime number. \begin{align} &4+1\equiv\square_1\text{ modulo }4p, \\&4(p-1)+1\equiv\square_2\text{ modulo }4p. \end{align} There exists an example each of them hold but I wonder both congruence hold at the same time or not.

For example, if $$p=5$$, then $$5\equiv 5^2$$ modulo $$20$$ but $$17\not\equiv\square$$ modulo $$20$$.

If $$p=3$$, then $$5\not\equiv\square$$ modulo $$12$$ but $$4(3-1)+1\equiv 3^2$$ modulo $$12$$.

I think that both congruence cannot hold at the same time. Can anyone help to prove this?

• Is $p$ supposed to always be a prime number? If so, please state this explicitly. Commented Jun 12 at 4:20
• Note that the square numbers in the two congruences need not be the same square number in the accepted & other answers. Indeed, if $4 + 1 \equiv 4(p-1) + 1 \mod 4p$, then $4 \equiv -4 \mod 4p$, which can never happen, so we always need there to be different squares. This confused me for a bit, perhaps it'd be clearer to write "let $\square, \square'$ be square numbers...", to emphasize the congruences need not be the same. Commented Jun 12 at 8:58

No, take $$p=19$$:

$$5 \equiv 81 = 9^2 \pmod{4\cdot19}$$ $$4(19-1)+1 \equiv 529 = 23^2\pmod{4 \cdot 19}$$

I found this counterexample using Legendre symbols and taking an educated guess at what $$p$$ could be.

Let $$p$$ be a prime. 5 is a square mod $$p$$ iff $$p=2, p=5$$ or $$p\equiv\pm 1\mod 10$$. $$-3$$ is a square mod $$p$$ iff $$p=2, p=3$$ or $$p\equiv1\mod 6$$. So, by applying the Chinese remainder theorem, both are true iff $$p=2$$ or $$p\equiv1$$ or $$19 \mod 30$$.

• Thank you for the answer! but $5\not\equiv\square$ mod $8$?? so I think $p=2$ is not possible.
– KS M
Commented Jun 12 at 5:41
• @KSM I confined my answer to the cases where $p$ is a prime. So $p=2$ is relevant to my answer but $p=8$ is not. Commented Jun 12 at 6:45
• @KSM Note that what Rosie F has done is to say, if the first congruence $5 \equiv \square \mod 4p$ holds, then certainly $5 \equiv \square \mod p$. $5$ is a square mod $2$, but is not a square mod $8$, so $p=2$ or $p \equiv 1, 19 \mod 30$ is a necessary but not sufficient condition. I think that $p \equiv 1, 19 \mod 30$ is a necessary and sufficient condition. Commented Jun 12 at 8:50
• @RosieF I think KS M is saying that $p=2$ should not be in the final list, since $5$ is not a square modulo $4p = 8$ in that case
– Marc
Commented Jun 12 at 17:45

I wrote a program to find the smallest counterexamples and I have obtained that, for $$p \leq 1000$$, there are $$36$$ primes obeying this congruence, namely

$$p=19, 31, 61, 79, 109, 139, 151, 181, 199, 211, 229, 241, 271, 331, 349, 379, 409, 421, 439, 499, 541, 571, 601, 619, 631, 661, 691, 709, 739, 751, 769, 811, 829, 859, 919, 991.$$

These turn out to be precisely the primes such that $$p \equiv 1,19 \mod 30$$ (see this other answer for a demonstration of that fact.)

• OEIS A033212 Commented Jun 12 at 19:52
• Thank you for the great answer!
– KS M
Commented Jun 17 at 5:10