Some prime number puzzle

One of my friends asked me to solve a basic puzzle. The results I found after solving the same made me to write a blog. Yeah, first the puzzle.

Prove that p^2 - 1 is always divisible by 24 for p being prime and p>=5

The solution is fairly simple. The factors of LHS is p-1, p+1. One of them is divisible by 2 and the other by 4 (Since, p is odd and out of two consecutive even primes one of them will be divisible by 4). Out of every three consecutive natural numbers, one of them should be divisible by 3. Since p is prime, either of the factors is divisible by 3. And hence the proposition is true.
After this, another colleague told me that prime numbers, greater than 3, can be expressed as 6K+1 or 6k-1. (It is not a sufficient condition, in the sense, all numbers of the given forms needs to be prime). After spending some time, i found out that all the numbers modulo 6 can be expressed as 6q+r and r can range from 0 to 5. Given this, one can arrive at the conclusion that two sets of natural number forms 6q+1, 6q-1 (same as 6q +5) cannot be directly expressed as product of two direct factors. And hence, the prime numbers can fall into the class either of the number forms. So, the hypothesis is valid. I was just hunting for other numbers which will be forming such number forms (classes) that can be used for primality testing. I have to devise some sort of strategy to find some other number, which will generate two classes. (Quiet obviously, 2 3 and 4 are already considered). If someone can point me to a good read on the same, it will be awesome.
Later, i moved on to read about Sexy Primes and Twin primes in wiki. The articles were awesome and i loved it :). Also, if possible try reading about Surreal Numbers (just google for it and download a nicely written pdf on the same. this is purely for pleasure reading).