I've heard that if a number $$$n$$$ has quadratic surplus under a odd prime $$$p$$$ so it has around 50% accuracy to be a perfect square number.
Is it correct? How to prove?
If so,perhaps there exists a method to judge whether a big number $$$n$$$ is a perfect square number or not is that random amount of odd primes which are not divisors of $$$n$$$ and find Quadratic surplus of $$$n$$$ mod $$$p$$$. Failure appears means $$$n$$$ isn't a perfect square number.
Just emotionally comprehend it
Could you please give a proof? Thanks
I think the meaning was lost in translation. I think you mean $$$n$$$ is a quadratic residue mod $$$p$$$. This can be verified using quadratic reciprocity. If something is a square mod $$$p$$$ then obviously it will be quadratic residue mod $$$p$$$. If something is not a square it has has a 50 % chance of being a square $$$\mod p$$$ because 50 % of residues are squares $$$\mod p$$$. It will be at most 50% but it is smaller for small $$$n$$$. Remember this tells us nothing if prime checks for one number is independent of another prime check, and how many tests could a non square number pass.
If anyone could find how many primes could a square free number pass or if they are mostly independent I am interested in your solution.
Everule said '50% of residues are squares $$$\bmod p$$$', you can find detailed proof on this Chinese website. If you choose $$$p$$$ randomly, $$$n\bmod p$$$ will have a 50% chance of being a quadratic residue $$$\bmod p$$$
Your first sentence is true. What follows from it is that for a fixed p if you choose n randomly then n has ~50% chance of being a quadratic residue, what is a significantly different from your second sentence, where you fix n and choose random p. I suspect your second sentence is true as well though (and in fact this is the statement required to checking if a bignum is a square) and definitely can be assumed as "alright enough" on a cp competition, but I guess complexity of its proof could be anywhere between complex olympic problem to open problem
Nah mate, saying that "if a number has quadratic residue mod p then it has 50% of being a square" is a probabilistic blasphemy