[seqfan] Re: A closed-form expression

[israel at math.ubc.ca]

See A182816.

To have b^n-b = b (b^(n-1)-1) == 0 (mod n), for each prime power p^k 
dividing n we need either p^k | b or p^k | b^(n-1)-1. The number of bases b 
(mod p^k) for which b^(n-1)==1 is gcd(p-1,n-1) when p is coprime to n. So 
we should have a(n) = product_{p^k|n} (1 + gcd(p-1,n-1)).

Cheers, 
Robert

On Sep 5 2018, Tomasz Ordowski wrote:

>Dear SeqFans!
>
>Let a(n) = number of bases b < n such that b^n == b (mod n).
>
>1, 2, 3, 2, 5, 3, 7, 2, 3, 4, 11, 4, 13, 3, 9, 2, 17, 3, 19, 5, 9, ...

Should be 1, 2, 3, 2, 5, 4, 7, 2, 3, 4, 11, 4, 13, 4, 9, 2, 17, 4, 19, 4, 9.

>For n = 6; 0^6 == 0 (mod 6), 1^6 == 1 (mod 6), and 3^6 == 3 (mod 6).

You forgot 4^6 == 4 (mod 6). 

>Note that, for n > 1, a(n) = n if and only if n is a prime or a Carmichael
>number.
>
>For n > 1, a(n) > A063994(n) = number of bases b mod n for which b^(n-1) ==
>1 (mod n).
>
>Is there any formula for a(n) similar to https://oeis.org/A063994 ?
>
>Best regards,
>
>Thomas
>
>--
>Seqfan Mailing list - http://list.seqfan.eu/
>
>