An interesting property of Primes

Any prime number greater than 3 exhibits the following wonderful property that I observed. It is:

Let p be a prime number(p>3), then it can always be represented in the following format,

p = 2^n + q

where n is a positive integer, and q is another prime less than p.

I have approached a proof, but could not complete it. Here is my approach in details.

Proof-

We know that prime numbers can be of two types, viz. (6k+1) or (6k-1).
Now, if we observe the equation carefully, we cannot obtain bot p and q of the same format. i.e. If both are (6k+1), then the equation looks like:

(6k+1)=2^n + (6m+1) where k>m.

But it is not valid for any k,m,n, since the left hand side is a multiple of 3, which the right hand side isn't. Similarly both (6k-1) is also not possible.

So, only possible cases are, p=(6k+1), q=(6m-1) and p=(6k-1), q=(6m+1).

case I(p=6k+1 and q=6m-1) -

Now, we consider the relation that (4^p - 1) is always a multiple of 3, for any positive integer p. This can be proved with the help of simple induction.

thus, 4^p - 1 = 3a
or, 4^p - 1 = 3(k-m) [where k>m and k,m are positive integers]
or, 2^2p = 3(k-m) + 1
or, 2^(2p+1) = 6(k-m) + 2
or, (6k+1) = 2^(2p+1) + (6m-1)

we can take n=(2p-1) to obtain the result as (6k+1) = 2^n + (6m-1).

Now, for some integer k,(6k+1) is a prime, and since there is always a prime of the format (6k-1) preceding the primes of the order (6k+1), so we can get primes on both side of the equation.

But, the problem that I encountered here is, (4^p - 1) does not give all the multiples of 3. It only gives some specific multiples, e.g. 3,15,63,255 etc. And so, (k-m) can also attain some specific integer values, i.e. 1,5,21,85 etc.[We exclude the case 7=2+5 since it is trivial]

So, what we have to prove is that, for this available values of (k-m) we will find integers k,m such that (6k+1) and (6k-1) both are primes. I haven't been able to prove this thing yet.

case II(p=6k-1 and q=6m+1) -

This case is similar to the previous case, only difference is that here the relation we assume is [2^(2p-1) + 1] is always a multiple of 3 for all positive integers p. The rest of the process is absolutely similar to the previous case. At the end of this case, we will again reach the same problem, where (k-m) can attain some specific integer values, and for those specific values we need to show that we can obtain k,m for which both (6k-1) and (6m+1) will be primes.


If someone finds a solution or a hint from here, please post in comments. I will be highly obliged.