Since it means thus . Therefore, is a quadradic residue modulo . Thus, there is a solution to . Therefore, . Therefore, we see that divides . However, can still be prime if . However, if then which would mean that is not prime. The only way, therefore, for it to be prime is when .