A216090 Numbers n such that k^(n-1) == k (mod n) for every k = 1, 2, ..., n-1.

1, 2, 6, 10, 14, 22, 26, 30, 34, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 134, 142, 146, 158, 166, 178, 182, 194, 202, 206, 214, 218, 226, 254, 262, 274, 278, 298, 302, 314, 326, 334, 346, 358, 362, 382, 386, 394, 398, 422, 446, 454, 458, 466, 478, 482

Offset

1,2

Comments

Subsequence of, but different from A197930, for example A197930(11) = 42 with 42 distinct residues, but the set R of the residues k^41 mod 42 is R = {1, 32, 33, 16, 17, 6, …, 9, 10, 41} for k = 1, 2, …, 41 instead R = {1, 2, 3, …, 40, 41}. Terms of A197930 that are not in this sequence: 42, 78, 110, 114, 138, 170, …

Squarefree numbers n such that A002322(n) divides n-2. Contains all doubled odd primes and all doubled Carmichael numbers. - Thomas Ordowski, Apr 23 2017

Links

Paolo P. Lava, Table of n, a(n) for n = 1..1000

Example

a(4) = 10 because x^9  == 1, 2, ..., 9  (mod 10) with 9 distinct residues such that:
1^9 = 1 == 1 (mod 10);
2^9 = 512 == 2 (mod 10);
3^9 = 19683 == 3 (mod 10);
4^9 = 262144 == 4 (mod 10);
5^9 = 1953125 == 5 (mod 10);
6^9 = 10077696 == 6 (mod 10);
7^9 = 40353607 == 7 (mod 10);
8^9 = 134217728 == 8 (mod 10);
9^9 = 387420489 == 9 (mod 10).

Maple

with(numtheory):for n from 1  to 500 do:j:=0:for i from 1 to n do: if irem(i^(n-1), n)=i then j:=j+1:else fi:od:if j=n-1 then printf(`%d, `, n):else fi:od:

Mathematica

f[n_] := And @@ Table[PowerMod[k, n - 1, n] == k, {k, n - 1}]; Select[Range[500], f] (* T. D. Noe, Sep 03 2012 *)

Prog

(PARI) isok(n) = {for (k=1, n-1, if (Mod(k, n)^(n-1) != Mod(k, n), return (0)); ); return (1); } \\ Michel Marcus, Apr 23 2017
(Python)
from sympy.ntheory.factor_ import core
from sympy import primefactors
def ok(n):
    if n<3: return True
    if core(n) == n:
        for p in primefactors(n):
            if (n - 2)%(p - 1): return False
        return True
    return False
print([n for n in range(1, 501) if ok(n)]) # Indranil Ghosh, Apr 23 2017

Crossrefs

Subsequence of A192109.

Terms > 2 form a subsequence of A050990.

Cf. A197929, A197930, A197943.

Sequence in context: A039956 A197930 A192109 * A342641 A118369 A226829

Adjacent sequences: A216087 A216088 A216089 * A216091 A216092 A216093

Keyword

nonn

Author

Michel Lagneau, Sep 01 2012

Status

approved