Euler's Criterion provides a method to determine if an integer is a quadratic residue modulo a prime number, using the relationship between the integer and the prime's Legendre symbol. It states that for a non-zero integer 'a' and an odd prime 'p', 'a' is a quadratic residue modulo 'p' if and only if a^((p-1)/2) is congruent to 1 modulo 'p'.