A330279 Numbers k such that x^k == k (mod k + 1) has multiple solutions for 0 <= x < k.

27, 51, 65, 69, 75, 111, 123, 129, 147, 153, 171, 175, 185, 189, 195, 207, 231, 237, 243, 245, 267, 275, 279, 285, 291, 303, 309, 315, 321, 343, 363, 365, 369, 387, 395, 405, 411, 417, 425, 429, 435, 441, 447, 489, 495, 505, 507, 519, 531, 555, 567, 573, 591, 597

Offset: 1

Author

Christopher Cormier, Dec 09 2019

Keywords

• nonn

Comments

All odd numbers have k^k == k (mod k + 1), but only some have other solutions in the least residue system (e.g. 3^27 and 19^27 == 27 (mod 28)).

Odd numbers k such that k and A000010(k+1) are not coprime. - Robert Israel, Jul 30 2023

Examples

			27 is in the list because x^27 == 27 (mod 28) has three solutions: 3, 19, and 27.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Robert Israel et al, Even k such that x^k == -1 mod k has solutions

Crossrefs

Cf. A000010, A014117, A096008, A195637.

Programs

Maple

select(t -> igcd(t,numtheory:-phi(t+1))>1, [seq(i,i=1..1000,2)]); # Robert Israel, Jul 30 2023

Mathematica

ok[k_] := Length[Select[Range[0, k-1], PowerMod[#, k, k + 1] == k &, 2]] > 1; Select[ Range@ 600, ok] (* Giovanni Resta, Dec 10 2019 *)

PARI

isok(k) = sum(i=0, k-1, Mod(i, k+1)^k == k) > 1; \\ Michel Marcus, Dec 10 2019