2
$\begingroup$

When applying the BRC theorem I need to test if an equation has a non-zero solution in integers.

The equation is of form:

$$x^2 + by^2 + cz^2 = 0$$

We could try to directly check if this equation has a non-trivial solution. The trivial is always there, so if there at least two in total, we're good:

nonTrivSolQ1[b_, c_] := Length[FindInstance[x^2 + b y^2 + c z^2 == 0, {x, y, z}, Integers, 2]] >= 2

But sometimes we get a false with an asterisk:

FindInstance::fwsol: Warning: FindInstance found only 1 instance(s), but it was not able to prove 2 instances do not exist.

And in some of these cases the false is wrong. We can use Legendre theorem to test solvability of the equation. In this case the solvability is equal to solvability of these two congruences:

$$u^2 \equiv -c (\textrm{mod}\ |b|)$$ $$v^2 \equiv -b (\textrm{mod}\ |c|)$$

However I have no better idea to test solvability here than to find instances again:

nonTrivSolQ2[b_, c_] := 
 Length[FindInstance[v^2 == -b, {v}, Modulus -> Abs[c]]] > 0 && 
  Length[FindInstance[v^2 == -c, {v}, Modulus -> Abs[b]]] > 0

This seems to work better, but is it safe that it never misses a solution when one exists? Or maybe there are other tools to test the solvability?

Edit

This seems a more reliable test than nonTrivSolQ2.

nonTrivSolQ3[b_, c_] := 
 Length@PowerModList[-b, 1/2, Abs[c]] > 0 && 
  Length@PowerModList[-c, 1/2, Abs[b]] > 0

Still this is "find the solution!" not "is there a solution?". Also, can I somehow use PowerMod and turn PowerMod::root: The equation x^2 = 10 (mod 14) has no integer solutions. into False?

$\endgroup$
  • 1
    $\begingroup$ The function that is meant to return confident results is Reduce: Reduce@Exists[{x, y, z}, Element[x | y | z, Integers], x^2 + b y^2 + c z^2 == 0 && (x != 0 || y != 0 || z != 0)]. Here it will fail on many b and c choices. But at least it gives a clear answer: "yes", "no", or "I don't know". $\endgroup$ – Szabolcs Mar 23 '17 at 16:47
  • $\begingroup$ I do not know if this is any different from FindInstance. But at least in principle it could use methods which don't require finding a specific instance. $\endgroup$ – Szabolcs Mar 23 '17 at 16:49
  • 1
    $\begingroup$ "...can I somehow use PowerMod..." - try Quiet[Check[PowerMod[10, 1/2, 14]; True, False, PowerMod::root]] $\endgroup$ – J. M. is away Mar 23 '17 at 17:19
  • $\begingroup$ math.stackexchange.com/questions/1513733/… $\endgroup$ – individ Mar 24 '17 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.