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

Author

Jonathan Sondow, Jan 12 2012

Keywords

• nonn
• easy

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

Examples

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

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.

Crossrefs

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

Cf. A191677 (zeros).

Programs

Mathematica

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

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

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