Say we wanted to check the Beal conjecture ["If $A^x+B^y=C^z$, where $[A, B, C, x, y, z \in N] \wedge [x, y, z \gt 2] \to $ A, B and C must have a common prime factor", from the official site]. What is the most efficient way of solving it by brute-forcing?
- First, define a set of possible solutions which meet the requirements, then test all these solutions [i.e. find a triple $A, B, C$ of numbers which have no common prime factors, find a triple $a, b, c >2$, then test if $A^x + B^y = C^z$]?
- First, find solutions for the equation, then check if they meet the requirements [i.e. solve $A^x + B^y + C^z$, then test if the numbers have no prime factors, then test if $a, b, c > 2$]?
I would let $S$ be the set of numbers of the form $A^x$ with $x > 2$ in $[1,\ldots,N]$, find $(S + S) \cap S$ (thus solutions of $A^x + B^y = C^z$), then check if $\mathrm{lcd}(A,B)$ and $C$ are coprime (using Euclid's algorithm, not factoring). Of course, assuming the conjecture is true, you won't be "solving it", just verifying that there are no counterexamples up to $N$.