See the first theorem here (proof given).
Use the factor theorem to show that if 2^p - 1, where p does not equal 3, is a prime number, then p is neither divisible by 4 or divisible by 3. {Alternatively, prove that if p is divisible by 4 or 3, the 2^p - 1 is divisible by some number other than +/- itself or +/-1.}
Well I can write it out in another way, not sure whether you'll find it easier. The formatting won't be very nice because LaTeX isn't quite working yet.
Multiples of 3
2^(3k) - 1 = (2^3)^k - 1 = 8^k - 1
Consider modulo 7.
8^k - 1 ≡ 1^k - 1 ≡ 0 (mod 7)
Thus the number is divisible by 7. If k = 1, then the number is 7 and thus prime, otherwise it is greater than 7 and thus composite.
Multiples of 4
2^(4k) - 1 = (2^4)^k - 1 = 16^k - 1
Consider modulo 15.
16^k - 1 ≡ 1^k - 1 ≡ 0 (mod 15)
Thus the number is divisible by 15 and always composite.