2
$\begingroup$

Prove that comparison is solvable (has solutions) for any prime $p$ and any $a, b, c \in \mathbb{Z}$: $$(x^2 - ab)(x^2 - bc)(x^2 - ac) \equiv 0 \ (mod \ p)$$

Not sure where to begin here. I will be grateful for any hints and solutions to this task.

UPD: There was already an idea to solve this problem (see below in the comments). But it seems to me that this idea already assumes that the comparison has a solution and p divides one of $(x^2 - ab), (x^2 - bc), (x^2 - ac)$, hence the existence of such a, b, c. But we need to prove something else, that some numbers a, b, c, p already exist and prove that the comparison is $(x^2 - ab)(x^2 - bc)(x^2 - ac)\equiv 0 \ (mod \ p)$ has solutions (solvable) for these numbers (something like a proof in the other direction with respect to the proposed idea). The authors of this problem wanted people to use some properties of the quadratic residue modulo in solving it. If my reasoning is wrong, then please explain why they are not correct.

$\endgroup$
2
  • 1
    $\begingroup$ $\sqrt{(p+1)ab}$ or $\sqrt{(p+1)bc}$ or $\sqrt{(p+1)ca}$ will always be a solution $\endgroup$
    – GameTime With Aryan
    Commented Feb 25 at 7:10
  • $\begingroup$ As in the linked dupe, if $ab,bc$ are nonsquares then $ab(bc) = acb^2$ is a square so $ac$ is too. $\ \ $ $\endgroup$
    – Bill Dubuque
    Commented Feb 26 at 18:38

1 Answer 1

Reset to default
2
$\begingroup$

As $p$ is prime, it must be a factor for at least one of the factors on the LHS of the congruency because

If $p|xyz$ where $x,y,z \in \mathbb{Z}$ and $p$ is prime, then $p|x$ or $p|y$ or $p|z|

Now take

$$x^2 - ab \equiv 0 \pmod p$$ $$x^2 - ab = kp \quad k \in \mathbb{Z}$$ $$x = \pm \sqrt{kp - ab}$$

Similarly

$$x = \pm \sqrt{kp - bc}$$ $$x = \pm \sqrt{kp - ca}$$

Are also solutions to the congruency

$\endgroup$
7
  • $\begingroup$ Your idea for solving this problem is very interesting. Numbers a, b, c and p are already given in the task and it must be proved that the comparison $(x^2 - ab)(x^2 - bc)(x^2 - ac) \equiv 0 \ (mod \ p)$ has solutions (solvable). As far as I understand, you proved one way, that is, assuming that this comparison is solvable and already deduced from there that p divides at least one of the expressions $(x^2 - ab), (x^2 - bc) ... $ and so on. $\endgroup$
    – Jacobs Monarch
    Commented Feb 25 at 16:01
  • $\begingroup$ It seems to me that we need to prove in second way that for any numbers a, b, c, p, the comparison from the task has solutions. Maybe we need to use some properties of the quadratic reciprocity. (if my suggestions are incorrect, please explain why it is not necessary to prove the second way) $\endgroup$
    – Jacobs Monarch
    Commented Feb 25 at 16:01
  • 1
    $\begingroup$ @JacobsMonarch You have the right general idea, but you don't need any specific properties of quadratic reciprocity. Instead, consider what the product of $2$ quadratic residues, and $2$ quadratic nonresidues, are in terms of being a quadratic residue or quadratic nonresidues. $\endgroup$
    – John Omielan
    Commented Feb 25 at 16:27
  • 1
    $\begingroup$ @JacobsMonarch I am sorry I do not have formal knowledge about modular arithmetic, I only know the basics, hence I am unable to help you with this question. $\endgroup$
    – GameTime With Aryan
    Commented Feb 25 at 18:47
  • $\begingroup$ I realized that the product of two quadratic residues and the product of two quadratic non-residues will be quadratic residues. For the comparison to be solvable, at least one of the factors: $(x^2-ab), (x^2-bc), (x^2 - ac)$ must be divisible by p ($(x^2-ab = 0 \ (mod \ p)$ as example), and then if the remaining factors, for example $((x^2-ac)$ and $(x^2-bc))$, are not quadratic residues, then their product will be a quadratic residue in this case as well , the comparison from the task condition will be solvable $\endgroup$
    – Jacobs Monarch
    Commented Feb 26 at 18:04

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