e.g. Let p=3, then there exist x=5 such that 5^2=1(mod 3).

In this case, 5 is not +1 or -1, but p=3 is still a prime. :P

Just to find a large prime number....

Starting from 2, generate a set of subsequent numbers like this:

a1 = 2
a2 = a1 + 1
a3 = a1*a2 + 1
a4 = a1*a2*a3 + 1
.
.
.
an = a1*...*a(n-1) + 1

This set of numbers should all be primes, but it doesn't contain all the prime numbers in order.