3
$\begingroup$

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?

$\endgroup$
2
  • 3
    $\begingroup$ Is $p$ supposed to always be a prime number? If so, please state this explicitly. $\endgroup$
    – John Omielan
    Commented Jun 12 at 4:20
  • 4
    $\begingroup$ 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. $\endgroup$
    – Robin
    Commented Jun 12 at 8:58

3 Answers 3

Reset to default
5
$\begingroup$

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.

$\endgroup$
0
4
$\begingroup$

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$.

$\endgroup$
4
  • 1
    $\begingroup$ Thank you for the answer! but $5\not\equiv\square$ mod $8$?? so I think $p=2$ is not possible. $\endgroup$
    – KS M
    Commented Jun 12 at 5:41
  • $\begingroup$ @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. $\endgroup$
    – Rosie F
    Commented Jun 12 at 6:45
  • $\begingroup$ @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. $\endgroup$
    – Robin
    Commented Jun 12 at 8:50
  • 1
    $\begingroup$ @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 $\endgroup$
    – Marc
    Commented Jun 12 at 17:45
2
$\begingroup$

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.)

$\endgroup$
2
  • 2
    $\begingroup$ OEIS A033212 $\endgroup$
    – Henry
    Commented Jun 12 at 19:52
  • $\begingroup$ Thank you for the great answer! $\endgroup$
    – KS M
    Commented Jun 17 at 5:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .