A341858 -id:A341858 - cp's OEIS frontend

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

1, 2, 6, 42, 1806

Offset: 1

"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 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
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

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:10.1016/j.dam.2018.05.022 arXiv:1602.02407 [math.NT], 2016-2018.
John H. Castillo and Jhony Fernando Caranguay Mainguez, The set of k-units 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. Dyer-Bennet, A Theorem in Partitions of the Set of Positive Integers, Amer. Math. Monthly, 47(1940) pp. 152-4.
L. Halbeisen and N. Hungerbühler, On generalised Carmichael numbers, Hardy-Ramanujan Society, 1999, 22 (2), pp.8-22. (hal-01109575)
J. M. Grau, A. M. Oller-Marcen, and Jonathan Sondow, On the congruence 1^m + 2^m + ... + m^m == n (mod m) with n|m, arXiv 1309.7941 [math.NT], 2013; Monatsh. Math., 177 (2015), 421-436.
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)
Jonathan 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; Integers, 11 (2011), article A34.
Eric Weisstein's World of Mathematics, Bernoulli Number
D. Zagier, Problems posed at the St Andrews Colloquium, 1996

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

Cf. A007018, A031971, A054377, A100016, A242927, A341858.

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 *)

[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

For n <= 5, a(n) = a(n-1)^2 + a(n-1) 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

A229289 Primes p of the form p = 2^k * m + 1, where (i) m is squarefree and odd, (ii) all primes that divide m are in the sequence, and (iii) k is 0, 1, or 2.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 23, 29, 31, 43, 47, 53, 59, 61, 67, 71, 79, 107, 131, 139, 157, 173, 211, 263, 269, 277, 283, 311, 317, 331, 347, 349, 367, 373, 421, 431, 461, 463, 547, 557, 599, 643, 659, 661, 683, 691, 709, 733, 743, 787, 827, 853, 859, 863, 911, 941

Offset: 1

José María Grau Ribas, Oct 05 2013

nonn

Taking m=1 in the definition we get the primes 2, 3, 5.
If n is in A226960, then n is a product of terms of this sequence.
If k is only allowed to be 0 or 1, we get 2, 3, 7, 43 and no more. - Jianing Song, Feb 21 2021
Also prime factors of terms in A341858. It is conjectured that this sequence is infinite. - Jianing Song, Feb 22 2021

Ray Chandler, Table of n, a(n) for n = 1..1000

Cf. A227007, A226960, A007814, A229290, A229291, A289355, A341858.
For the complement, see A289355.
Proper subsequence of A066651.

fa = FactorInteger; free[n_] := n == Product[fa[n][[i, 1]], {i, Length[fa[n]]}] ; Os[b_, 1] = True; Os[b_, b_] = True; Os[b_, n_] := Os[b, n] = PrimeQ[n] && free[(n - 1)/b^IntegerExponent[n - 1, b]] &&IntegerExponent[n - 1, b] < 3 && Union@Table[Os[b, fa[n - 1][[i, 1]]], {i, Length[fa[n - 1]]}] == {True};G[b_] := Select[Prime[Range[1000]], Os[b, #] &];G[2]

is(n)=if(!isprime(n),return(0)); if(n<13,return(1)); my(k=valuation(n-1,2), m=n>>k, f); if(k>2,return(0)); f=factor(m); if(lcm(f[,2])>1, return(0)); for(i=1,#f~, if(!is(f[i,1]), return(0))); 1 \\ Charles R Greathouse IV, Oct 28 2013

Revised definition from Charles R Greathouse IV, Nov 13 2013

Terms corrected by José María Grau Ribas, Nov 14 2013

A341857 a(n) = psi(n^2)/n, psi = A002322.

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 6, 2, 6, 2, 10, 1, 12, 3, 4, 4, 16, 3, 18, 1, 2, 5, 22, 2, 20, 6, 18, 3, 28, 2, 30, 8, 10, 8, 12, 3, 36, 9, 4, 2, 40, 1, 42, 5, 12, 11, 46, 4, 42, 10, 16, 3, 52, 9, 4, 6, 6, 14, 58, 1, 60, 15, 6, 16, 12, 5, 66, 4, 22, 6, 70, 6, 72, 18, 20, 9

Offset: 1

Jianing Song, Feb 21 2021

nonn

It is easy to show that n divides psi(n) for all n.
For k >= 2, n^k divides psi(n^(k+1)) if and only if n is not of the form 2*(p_1)^(e_1)*(p_2)^(e_2)*...*(p_m)^(e_m), where p_i are distinct odd primes not congruent to 1 modulo 2^k.
It seems that every positive integer occurs in this sequence. The first occurrence of each k is given by A341860.

			psi(220^2) = psi(2^4 * 5^2 * 11^2) = lcm(psi(2^4), psi(5^2), psi(11^2)) = lcm(4, 20, 110) = 220, so a(220) = psi(220^2)/220 = 220/220 = 1.

Jianing Song, Table of n, a(n) for n = 1..10000

Cf. A002322, A341860.

Indices of 1 are given by A341858.

Array[CarmichaelLambda[#^2]/# &, 100] (* Paolo Xausa, Mar 11 2024 *)

a(n) = A002322(n^2)/n \\ See A002322 for its program

For odd n > 1, a(2n) = a(n)/2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

A229289 Primes p of the form p = 2^k * m + 1, where (i) m is squarefree and odd, (ii) all primes that divide m are in the sequence, and (iii) k is 0, 1, or 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A341857 a(n) = psi(n^2)/n, psi = A002322.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula