Efficient way to check if large number is divisible by 3

Question

If

M_p=2^p-1 is prime ⇒

⇒ 2^p-2⋮6 or 2^p⋮6 ⇒

⇒ 2^p-1-1⋮3 or 2^p-1⋮3 ⇒

⇒ 2ⁿ-1⋮3 or 2ⁿ⋮3, n=p-1

In order to pick huge values for p to test if M_p is a prime number, I believe this is a good preliminary test before going with the computationally expensive Lucas-Lehmer test.

But what is the fastest, most efficient way to test if two numbers, 2ⁿ-1 and 2ⁿ, are divisible by 3.

Other info that we can use from this is that n always ends in 0, 2, 6 or 8 (because p=n+1 is a prime). Maybe it helps in some way.

Thank you!

Answer 1

$2^n$ is never divisible by 3, by the fundamental theorem of arithmetic.

$2^n - 1$ is divisible by 3 iff $n$ is even, by Fermat's Little theorem / Euler's theorem.

Answer 2

$2^n$ doesn't have the least chance to be divisible by $3$. As for $2^p-2$, you can compute modulo $3$: $$2^p-2\equiv(-1)^p+1=0\mod 3$$ Thus a Mersenne prime has the form $6k+1$.

(you didn't mention it, but I suppose you're looking at Mersenne numbers, which require $p$ to be prime to have a chance to be prime too. I supposed $p$ is an odd prime).