

A014117


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


42




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, and 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.
Yongyi Chen and Tae Kyu Kim, On Generalized Carmichael Numbers, arXiv:2103.04883 [math.NT], 2021.
J. DyerBennet, A Theorem in Partitions of the Set of Positive Integers, Amer. Math. Monthly, 47(1940) pp. 1524.
L. Halbeisen and N. Hungerbühler, On generalised Carmichael numbers, HardyRamanujan Society, 1999, 22 (2), pp.822. (hal01109575)
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.
Eric Weisstein's World of Mathematics, Bernoulli Number
D. Zagier, Problems posed at the St Andrews Colloquium, 1996


FORMULA

For n <= 5, a(n) = a(n1)^2 + a(n1) with a(0) = 1.  Raphie Frank, Nov 12 2012
a(n+1) = A007018(n) = A054377(n) = A100016(n) for n = 1, 2, 3, 4.  Jonathan Sondow, Oct 01 2013


MATHEMATICA

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 A349193
Adjacent sequences: A014114 A014115 A014116 * A014118 A014119 A014120


KEYWORD

nonn,fini,full,nice


AUTHOR

David Broadhurst


STATUS

approved



