login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014117 Numbers n such that m^(n+1) == m (mod n) holds for all m. 39
1, 2, 6, 42, 1806 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

"Somebody incorrectly remembered Fermat's little theorem as saying that the congruence a^{n+1} = a (mod n) holds for all a if n is prime" (Zagier). The sequence gives the set of integers n for which this property is in fact true.

If i == j (mod n), then m^i == m^j (mod n) for all m. The latter congruence generally holds for any (m, n)=1 with i == j (mod k), k being the order of m modulo n, i.e., the least power k for which m^k == 1 (mod n). - Lekraj Beedassy, Jul 04 2002

Also, numbers n such that n divides denominator of the n-th Bernoulli number B(n) (cf. A106741). Also, numbers n such that 1^n + 2^n + 3^n + ... + n^n == 1 (mod n). Equivalently, numbers n such that B(n)*n == 1 (mod n). Equivalently, Sum_{prime p, (p-1) divides n} n/p == -1 (mod n). It is easy to see that for n > 1, n must be an even squarefree number. Moreover, the set P of prime divisors of all such n satisfies the property: if p is in P, then p-1 is the product of distinct elements of P. This set is P = {2, 3, 7, 43}, implying that the sequence is finite and complete. - Max Alekseyev, Aug 25 2013

In 2005, B. C. Kellner proved E. W. Weisstein's conjecture that denom(B_n) = n only if n = 1806. - Jonathan Sondow, Oct 14 2013

Squarefree terms of A124240. - Robert Israel and Thomas Ordowski, Jun 23 2017

LINKS

Table of n, a(n) for n=1..5.

Max Alekseyev, Jose María Grau and A. M. Oller-Marcen, On the congruence 1^n + 2^n + ... + n^n = p (mod n), arXiv:1602.02407 [math.NT], 2016.

John H. Castillo and Jhony Fernando Caranguay Mainguez, The set of k-units modulo n, arXiv:1708.06812 [math.NT], 2017.

J. Dyer-Bennet, A Theorem in Partitions of the Set of Positive Integers, Amer. Math. Monthly, 47(1940) pp. 152-4.

J. M. Grau, A. M. Oller-Marcen, and J. Sondow, On the congruence 1^m + 2^m + ... + m^m == n (mod m) with n|m, arXiv 1309.7941 [math.NT], 2013.

B. C. Kellner, The equation denom(B_n) = n has only one solution, preprint 2005.

J. Sondow and K. MacMillan, Reducing the Erdos-Moser equation 1^n + 2^n + … + k^n = (k+1)^n modulo k and k^2, arXiv:1011.2154 [math.NT], 2010; see Prop. 2.

E. W. Weisstein's Mathworld, Bernoulli Number

D. Zagier, Problems posed at the St Andrews Colloquium, 1996

FORMULA

a(n) = a(n-1)^2 + a(n-1) with a(0) = 1. - Raphie Frank, Nov 12 2012 [This is wrong, since the sequence has only five terms. - N. J. A. Sloane, Apr 11 2017]

a(n+1) = A007018(n) = A054377(n) = A100016(n) for n = 1, 2, 3, 4. - Jonathan Sondow, Oct 01 2013

MATHEMATICA

(* Checking up to n = 2000 *) r[n_] := Reduce[ Mod[m^(n+1) - m, n] == 0, m, Integers]; ok[n_] := Range[n]-1 === Simplify[ Mod[ Flatten[ m /. {ToRules[ r[n][[2]] ]}], n], Element[C[1], Integers]]; ok[1] = True; A014117 = {}; Do[ If[ok[n], Print[n]; AppendTo[ A014117, n] ], {n, 1, 2000}] (* Jean-François Alcover, Dec 21 2011 *)

Select[Range@ 2000, Function[n, Times @@ Boole@ Map[Function[m, PowerMod[m, n + 1, n] == Mod[m, n]], Range@ n] > 0]] (* Michael De Vlieger, Dec 30 2016 *)

CROSSREFS

Cf. A007018, A031971, A054377, A100016, A124240.

Sequence in context: A115961 A123137 * A242927 A054377 A230311 A276416

Adjacent sequences:  A014114 A014115 A014116 * A014118 A014119 A014120

KEYWORD

nonn,fini,full,nice

AUTHOR

David Broadhurst

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 20 13:30 EDT 2018. Contains 313917 sequences. (Running on oeis4.)