OFFSET
0,1
COMMENTS
The congruence in some sense characterizes the primes: all primes satisfy it automatically; and for any n, there are finitely many composites that satisfy it.
A composite c satisfies the congruence if and only if c = 2p for p a prime with (p-1) | (2^(n+2)+2); it follows that c <= 2^(n+3)+6; and moreover any c which satisfies the congruence for some n satisfies it for infinitely many n. (Any such c is in A100484.)
4 and 6 satisfy the congruence for any choice of n; they are the only such (composite) c.
LINKS
Scott Duke Kominers, Table of n, a(n) for n = 0..241 (rows n = 0..50)
A. Dujella and F. Luca, On a variation of a congruence of Subbarao, Journal of the Australian Mathematical Society 93 (2012), 85-90.
S. Gong and Scott Duke Kominers, On congruence conditions for primality, INTEGERS, 10 (2010), 313-317. [Note: Some elements missing from the table in this reference; corrected in "A flanking pattern" reference below.]
Scott Duke Kominers, A flanking pattern in a sum-of-divisors congruence, arXiv:2512.18424 [math.NT], 2025.
P. Lescot, A characterisation of prime numbers, The Mathematical Gazette, 80 (1996), 400-401.
M. V. Subbarao, On two congruences for primality, Pacific Journal of Mathematics, 52 (1974), 261-268.
EXAMPLE
The irregular triangle begins:
n: c
-------------------------------------------------------
0: 4, 6, 14;
1: 4, 6, 22;
2: 4, 6, 14, 38;
3: 4, 6;
4: 4, 6, 14, 46, 134;
5: 4, 6, 22, 262;
6: 4, 6, 14;
7: 4, 6;
8: 4, 6, 14, 38;
9: 4, 6, 22, 166;
10: 4, 6, 14, 2734, 8198;
11: 4, 6;
12: 4, 6, 14;
13: 4, 6, 22, 118, 454, 65542;
14: 4, 6, 14, 38, 46, 134, 398, 3974, 14566, 131078;
...
PROG
(PARI) isok(c, n) = my(p); !(c%2) && isprime(p=c/2) && !((2^(n+2)+2) % (p-1));
row(n) = select(x->isok(x, n), [4..2^(n+3)+6]); \\ Michel Marcus, Jan 08 2026
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Scott Duke Kominers, Jan 07 2026
STATUS
approved