cp's OEIS Frontend

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

%I A014117 #121 May 30 2025 01:13:52
%S A014117 1,2,6,42,1806
%N A014117 Numbers n such that m^(n+1) == m (mod n) holds for all m.
%C A014117 "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.
%C A014117 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
%C A014117 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
%C A014117 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
%C A014117 Squarefree numbers n such that b^n == 1 (mod n^2) for every b coprime to n. Squarefree terms of A341858. - _Thomas Ordowski_, Aug 05 2024
%C A014117 Conjecture: Numbers n such that gcd(d+1, n) > 1 for every proper divisor d of n. Verified up to 10^696. - _David Radcliffe_, May 29 2025
%H A014117 M. A. Alekseyev, J. M. Grau, and A. M. Oller-Marcen. Computing solutions to the congruence 1^n + 2^n + ... + n^n == p (mod n). Discrete Applied Mathematics, 2018. doi:<a href="http://doi.org/10.1016/j.dam.2018.05.022">10.1016/j.dam.2018.05.022</a> arXiv:<a href="http://arxiv.org/abs/1602.02407">1602.02407</a> [math.NT], 2016-2018.
%H A014117 John H. Castillo and Jhony Fernando Caranguay Mainguez, <a href="https://arxiv.org/abs/1708.06812">The set of k-units modulo n</a>, arXiv:1708.06812 [math.NT], 2017.
%H A014117 Yongyi Chen and Tae Kyu Kim, <a href="https://arxiv.org/abs/2103.04883">On Generalized Carmichael Numbers</a>, arXiv:2103.04883 [math.NT], 2021.
%H A014117 J. Dyer-Bennet, <a href="http://www.jstor.org/stable/2304216">A Theorem in Partitions of the Set of Positive Integers</a>, Amer. Math. Monthly, 47(1940) pp. 152-4.
%H A014117 L. Halbeisen and N. Hungerbühler, <a href="https://hal.archives-ouvertes.fr/hal-01109575">On generalised Carmichael numbers</a>, Hardy-Ramanujan Society, 1999, 22 (2), pp.8-22. (hal-01109575)
%H A014117 J. M. Grau, A. M. Oller-Marcen, and Jonathan Sondow, <a href="http://arxiv.org/abs/1309.7941">On the congruence 1^m + 2^m + ... + m^m == n (mod m) with n|m</a>, arXiv 1309.7941 [math.NT], 2013; Monatsh. Math., 177 (2015), 421-436.
%H A014117 B. C. Kellner, <a href="http://bernoulli.org/~bk/denombneqn.pdf">The equation denom(B_n) = n has only one solution</a>, preprint 2005.
%H A014117 Don Reble, <a href="/A014117/a014117.pdf">A014117 and related OEIS sequences</a> (shows there are no other terms)
%H A014117 Jonathan Sondow and K. MacMillan, <a href="http://arxiv.org/abs/1011.2154">Reducing the Erdos-Moser equation 1^n + 2^n + … + k^n = (k+1)^n modulo k and k^2</a>, arXiv:1011.2154 [math.NT], 2010; see Prop. 2; Integers, 11 (2011), article A34.
%H A014117 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BernoulliNumber.html">Bernoulli Number</a>
%H A014117 D. Zagier, <a href="https://mathshistory.st-andrews.ac.uk/EMS/Zagier/Problems/">Problems posed at the St Andrews Colloquium, 1996</a>
%F A014117 For n <= 5, a(n) = a(n-1)^2 + a(n-1) with a(0) = 1. - _Raphie Frank_, Nov 12 2012
%F A014117 a(n+1) = A007018(n) = A054377(n) = A100016(n) for n = 1, 2, 3, 4. - _Jonathan Sondow_, Oct 01 2013
%t A014117 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 *)
%t A014117 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 *)
%o A014117 (Python)
%o A014117 [n for n in range(1, 2000) if all(pow(m, n+1, n) == m for m in range(n))] # _David Radcliffe_, May 29 2025
%Y A014117 Squarefree terms of A124240. - _Robert Israel_ and _Thomas Ordowski_, Jun 23 2017
%Y A014117 Cf. A007018, A031971, A054377, A100016, A242927, A341858.
%K A014117 nonn,fini,full,nice
%O A014117 1,2
%A A014117 _David Broadhurst_