How to prove or disprove $n$ is prime? Let $n$ be an odd number such that
$$2^{\frac{n-1}{2}}\equiv -1 \pmod{n}$$
How do I prove or disprove $n$ must is prime? 
This problem is from when I solved another problem. Thank you 
 A: The basic method for fast exponentiation is to first find the base 2 expansion of $1638$, i.e., notice that $1638=2+2^2+2^5+2^6+2^9+2^{10}$.
On the other hand, $2^2\equiv 4 \pmod{3277}$, $2^{2^2}\equiv 16 \pmod{3277}$, $2^{2^3}\equiv 256 \pmod{3277}$ and $2^{2^4}\equiv -4 \pmod{3277}$, $2^{2^5}\equiv 16 \pmod{3277}$, $2^{2^6}\equiv 256 \pmod{3277}$, $2^{2^7}\equiv -4 \pmod{3277}$, $2^{2^8}\equiv 16 \pmod{3277}$, $2^{2^9}\equiv 256 \pmod{3277}$, $2^{2^{10}}\equiv -4 \pmod{3277}$. Note that to get each term, I'm just squaring the previous term, so this is a pretty quick calculation.
Therefore, $2^{1638}\equiv 2^{2+2^2+2^5+2^6+2^9+2^{10}}\equiv (4)(16)(16)(256)(256)(-4)\equiv -1 \pmod{3277}$.
A: There are three kinds of solution to this kind of thing - primes, pseudo primes, and carmichael's numbers.
If you solve something like $3^{\frac{n-1}n} = -1 \pmod{n}$, and this fails, then $n$ is a pseudoprime to 2, but not 3.  
If you solve this, and get a positive result for $3$ as well, then you could be dealing with a carmicahel-number, a product of three or more primes $p_n$, where $p_n-1$ divides the number less one.  An example is $601\times 1201 \times 1801$.  
There are instances like $43\times 127$, which has period that divides 42 for all bases $2^a 5^b$.  
If you know some clever tricks, you can hunt around for $a\text{^^}{\frac {n+1}2} = -2$, where the ^^ operator gives $p\text{^^}n= a^n+a^{-n}$, and $p\text{^^}0 = 2, p\text{^^1}=p$.  This is the way they hunt Messerine primes, where $p=4, n=2^x$.  
