

A014117


Numbers n such that m^(n+1) == m (mod n) holds for all m.


40




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 nth 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, (p1) 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 p1 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


LINKS

Table of n, a(n) for n=1..5.
M. A. Alekseyev, J. M. Grau, A. M. OllerMarcen. Computing solutions to the congruence 1^n + 2^n + ... + n^n == p (mod n). Discrete Applied Mathematics, 2018. doi:10.1016/j.dam.2018.05.022 arXiv:1602.02407 [math.NT], 20162018.
John H. Castillo and Jhony Fernando Caranguay Mainguez, The set of kunits modulo n, arXiv:1708.06812 [math.NT], 2017.
J. DyerBennet, A Theorem in Partitions of the Set of Positive Integers, Amer. Math. Monthly, 47(1940) pp. 1524.
J. M. Grau, A. M. OllerMarcen, and J. Sondow, On the congruence 1^m + 2^m + ... + m^m == n (mod m) with nm, arXiv 1309.7941 [math.NT], 2013, Monatsh. Math., 177 (2015), 421436.
B. C. Kellner, The equation denom(B_n) = n has only one solution, preprint 2005.
Don Reble, A014117 and related OEIS sequences (shows there are no other terms)
J. Sondow and K. MacMillan, Reducing the ErdosMoser equation 1^n + 2^n + … + k^n = (k+1)^n modulo k and k^2, arXiv:1011.2154 [math.NT], 2010; see Prop. 2; Integers, 11 (2011), article A34.
E. W. Weisstein's Mathworld, Bernoulli Number
D. Zagier, Problems posed at the St Andrews Colloquium, 1996


FORMULA

a(n) = a(n1)^2 + a(n1) 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}] (* JeanFranç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

Squarefree terms of A124240.  Robert Israel and Thomas Ordowski, Jun 23 2017
Cf. A007018, A031971, A054377, A100016, A242927.
Sequence in context: A250309 A115961 A123137 * A242927 A054377 A230311
Adjacent sequences: A014114 A014115 A014116 * A014118 A014119 A014120


KEYWORD

nonn,fini,full,nice


AUTHOR

David Broadhurst


STATUS

approved



