In the remark below the statement of Euler's criterion in the paper you linked to,

Frei [17], p. 57, points out that Grube only proved one direction of this criterion and says, “whether [this criterion] is also sufficient is still an open problem”

which explains why you might get false positives.

In the remark below the statement of Euler's criterion in the paper you linked to, notice that Grube, who tried to correct Euler's original "proof" of this criterion, actually only provided a correct version in one direction -

Frei [17], p. 57, points out that Grube only proved one direction of this criterion and says, “whether [this criterion] is also sufficient is still an open problem”

which explains why you might get false positives.