If n is prime the jacobi symbol is the legendre symbol, which is 1 if x is a square mod n, and -1 otherwise. Raise a square to the (n-1)/2 and you are raising something else to the n-1, which becomes 1, just like the legendre symbol. Raise a nonsquare to the (n-1)/2 and get -1; so it all works out.
Conversely, suppose the equation holds at least half the time, yet n is not prime. Let n have a factor of pk, for k > 1. The group of units includes a cycle of order pk-1, in parallel with other cycles. An x chosen at random will be nonzero in this cycle most of the time. Even if pk is as small as 32, x is nonzero in this cycle 2/3 of the time. Raising to the (n-1)/2 multiplies this value by -1/2, which permutes all the values in the cycle. The result isn't going to be 0, which would be necessary for x(n-1)/2 = ±1 mod n. The test fails most of the time. Thus n is squarefree.
Squaring the jacobi test gives the pseudoprime test, which passes at least half the time. The chinese remainder theorem tells us a uniform distribution mod n implies, and comes from, a uniform distribution mod p for each prime factor p in n. If less than half the values of x lead to 1 mod p, then less than half the values of x lead to 1 mod n. So at least half the values mod p, raised to the n-1, yield 1.
Suppose p-1 does not divide n-1. Raising everything to the n-1 mod p produces at most (p-1)/2 instances of 1. This is technically less than half. Therefore each p-1 divides evenly into n-1. This implies n is one of those pesky carmichael numbers.
Suppose (n-1)/(p-1) is even. After n-1 is cut in half, it is still sufficient to drive x up to a value of 1 mod p. This can only equal 1 mod n (rather than -1). When the jacobi test succeeds, it succeeds with 1. However, have the jacobi symbols come out -1. This causes the test to fail at least half the time. Therefore (n-1)/(p-1) is odd for each prime p dividing n.
Let p and q be two primes dividing n. Raising x to the (n-1)/2 and looking mod p or q has the effect of telling us whether x is a square mod p or mod q. All combinations appear in a uniform distribution. Half the time x will be a square under one prime and a nonsquare under the other. The result is a value that is 1 mod one prime and -1 mod the other. This cannot equal ±1 mod n. The test fails at least half the time.
In summary, a composite number fails the jacobi test half the time. We have a probabilistic algorithm with specific error constraints. If the jacobi test succeeds on 20 randomly selected values of x, then n is composite with probability below 1 in a million. If you want more certainty, run the test another 20 times, and n is composite with probability below 1 in a trillion. It doesn't take long to attain near certainty.
The test suggests we make sure x and n are coprime at the outset, but this is not necessary, because x raised to any power will share a common factor with n, and will not be ±1. So we can skip this step, which is a waste of time anyways, since n consists of very large primes, and you're not going to stumble onto one of these by accident.
Note that the test is efficient for large values of n. Modular exponentiation is tractable, and the jacobi symbol [x\n] is computed easily using the gcd algorithm.