A204187 a(n) = Sum_{m=1..n-1} m^(n-1) modulo n.

0, 1, 2, 0, 4, 3, 6, 0, 6, 5, 10, 0, 12, 7, 10, 0, 16, 9, 18, 0, 14, 11, 22, 0, 20, 13, 18, 0, 28, 15, 30, 0, 22, 17, 0, 0, 36, 19, 26, 0, 40, 21, 42, 0, 21, 23, 46, 0, 42, 25, 34, 0, 52, 27, 0, 0, 38, 29, 58, 0, 60, 31, 42, 0, 52, 33, 66, 0, 46, 35, 70, 0

Offset

1,3

Comments

a(n) = n - 1 if n is 1 or a prime, by Fermat's little theorem. It is conjectured that the converse is also true; see A055032 and A201560 and note that a(n) = n-1 <==> A055032(n) = 1 <==> A201560(n) = 0.

As of 1991, Giuga and Bedocchi had verified no composite n < 10^1700 satisfies a(n) = n - 1 (Ribemboim, 1991). - Alonso del Arte, May 10 2013

References

Steve Dinh, The Hard Mathematical Olympiad Problems And Their Solutions, AuthorHouse, 2011, Problem 6 of Hong Kong Mathematical Olympiad 2007 (find a(7)), page 134.

Richard K. Guy, Unsolved Problems in Number Theory, A17.

Paulo Ribemboim, The Little Book of Big Primes. New York: Springer-Verlag (1991): 17.

Links

Ivan Neretin, Table of n, a(n) for n = 1..10000

John Clark, On a conjecture involving Fermat's Little Theorem, Thesis, 2008, University of South Florida.

Hong Kong Mathematics Olympiad (2007-2008), Final Event 2 (Group), problem 2, p. 437.

Bernard Schott, Proof that a(n)=n/2 if n is of the form 4k+2.

Index to sequences related to Olympiads.

Formula

a(p) = p - 1 if p is prime, and a(4n) = 0.

a(n) + 1 == A201560(n) (mod n).

a(n) = n/2 iff n is of the form 4k+2 (conjectured). - Ivan Neretin, Sep 23 2016

a(4*k+2) = 2*k+1; for a proof see corresponding link. - Bernard Schott, Dec 29 2021

Example

Sum(m^3, m = 1 .. 3) = 1^3 + 2^3 + 3^3 = 36 == 0 (mod 4), so a(4) = 0.

Mathematica

Table[Mod[Sum[i^(n - 1), {i, n - 1}], n], {n, 75}] (* Alonso del Arte, May 10 2013 *)

Prog

(PARI) a(n) = lift(sum(i=1, n, Mod(i, n)^(n-1))); \\ Michel Marcus, Feb 23 2020
(Python)
def a(n): return sum(pow(m, n-1, n) for m in range(1, n))%n
print([a(n) for n in range(1, 73)]) # Michael S. Branicky, Jan 02 2022

Crossrefs

Cf. A055023, A055030, A055031, A055032, A201560.

Cf. A191677 (zeros).

Sequence in context: A241384 A140254 A340187 * A095202 A343923 A291937

Adjacent sequences: A204184 A204185 A204186 * A204188 A204189 A204190

Keyword

nonn,easy

Author

Jonathan Sondow, Jan 12 2012

Status

approved