login
a(n) is the least k > n such that the remainder when n^k is divided by k is n.
1

%I #20 May 25 2021 20:07:33

%S 2,3,5,5,7,7,11,9,11,11,13,13,17,15,17,17,19,19,23,21,23,23,29,25,28,

%T 27,29,29,31,31,37,33,37,35,37,37,41,39,41,41,43,43,47,45,47,47,53,49,

%U 53,51,53,53,59,55,59,57,59,59,61,61,67,63,67,65,67,67,71,69,71,71,73,73

%N a(n) is the least k > n such that the remainder when n^k is divided by k is n.

%C a(n-1) = n for n = {2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,...} = 2 together with odd numbers n > 1.

%C a(n) coincides with A082048(n) up to n = 24.

%C a(n) is the smallest number k > n such that n^k == n (mod k). Conjecture: a(n) is the smallest number k > n such that n^(k-1) == 1 (mod k). Thus a(n) is coprime to n. - _Thomas Ordowski_, Aug 03 2018

%H Harvey P. Dale, <a href="/A126762/b126762.txt">Table of n, a(n) for n = 1..996</a>

%t Table[Min[Select[Range[101],PowerMod[n,#,# ]==n&]],{n,1,100}]

%t lkgn[n_]:=Module[{k=1},While[PowerMod[n,k,k]!=n,k++];k]; Array[lkgn,80] (* _Harvey P. Dale_, May 25 2021 *)

%Y Cf. A128149 = Least k such that n^k (mod k) = n-1. Cf. A128172 = Least k such that n^k (mod k) = n+1. Cf. A036236, A078457, A119678, A119679, A127816, A119715, A119714, A127817, A127818, A127819, A127820, A127821, A128154, A128155, A128156, A128157, A128158, A128159, A128160. Cf. A082048 = least number greater than n having greater smallest prime factor than that of n.

%K nonn

%O 1,1

%A _Alexander Adamchuk_, Feb 17 2007

%E Name clarified by _Thomas Ordowski_, Aug 03 2018