cp's OEIS Frontend

The multiplicative order of 3 modulo a(n) is A385226(n).

Without 2, contained in primes congruent to 1 or 11 modulo 12 (primes p such that 3 is a quadratic residue modulo p; A097933), and contains primes congruent to 11 modulo 12 (A068231).

Conjecture: this sequence has density 1/3 among the primes.

Union of 2, 3, A068231 (primes congruent to 11 modulo 12), primes p == 1 (mod 4) such that 3^((p-1)/4) == 1 (mod p). - Jianing Song, Jun 22 2025

Complement of A045317 relative to A000040. - Vincenzo Librandi, Sep 19 2012

Is there a simpler characterization of these primes?

Answer from Don Reble, Oct 25 2018: (Start)

Let POT(x) be the largest power of 2 which divides x (A006519).

Apart from the initial 2, this sequence consists of those primes P such that

2 <= POT(the order of 3 modulo P) <= POT(P-1)/8.

The condition "2 <=" ensures that P divides some 3^k+1, and the condition "<= POT(P-1)/8" is so that 3 has an eighth root modulo P. A062117 is the order of 3 modulo prime(n). (End)

Comments from Richard Bumby, Nov 12 2018: (Start)

When considering methods for finding square roots mod p one is led to filtering the nonzero elements by the power of 2 dividing the multiplicative order of the element. The lowest level -- elements of odd order -- have easily computed square roots, and the square roots of other elements can be found if you can discover at least one element at a higher level.

To say that "x^8 = 3 has no solution mod p" is to say that 3 is in one of the top three levels and that there are more than 3 levels (so that 8 divides p-1).

To say that primes "divide numbers of the form 3^k + 1" is to say that -1 is a power of 3 mod p, or that 3 is not at the lowest level. If there are only four levels (9 mod 16), these statements are equivalent. Otherwise, the two statements are different. An interesting case has 3 at the second level, so that (-3) has odd order allowing cube roots of unity to be found quickly.

I was told that Odoni had some results on finding the number of primes with k levels for which a given number (e.g., 3) is at level j, but I never tracked down a reference. If the asymptotic behavior is what one would expect, A045318 and A301916 are really far from being "almost the same", except in the trivial sense of "zero density". (End)