login
Smallest prime p such that the multiplicative order of 4 modulo p is 2*n, or 0 if no such prime exists.
4

%I #18 Nov 24 2024 13:59:59

%S 3,17,31,73,151,433,631,337,127,241,331,601,4421,673,3061,257,1429,

%T 1657,1103,3121,2143,1321,18539,1777,2351,37441,2971,2857,3191,17401,

%U 683,15809,17029,9929,38431,1801,11471,63689,49999,13121,17467,21169,83077,25609,5581,5153,26227

%N Smallest prime p such that the multiplicative order of 4 modulo p is 2*n, or 0 if no such prime exists.

%C First prime p such that the expansion of 1/p has period (p-1)/(2*n) in base 4. Also the first prime p such that {k/p : 1 <= k <= p-1} has 2*n different cycles when written out in base 4.

%C Since ord(a^m,k) = ord(a,k)/gcd(m,ord(a,k)) for gcd(a,k) = 1, we have that (p-1)/ord(4,p) = ((p-1)/ord(2,p)) * gcd(2,ord(2,p)) is always even. Here ord(a,k) is the multiplicative order of a modulo k.

%H Jean-François Alcover, <a href="/A372797/b372797.txt">Table of n, a(n) for n = 1..1000</a>

%e In the following examples let () denote the reptend. The prime numbers themselves and the fractions are written out in decimal.

%e The base-4 expansion of 1/3 is 0.(1), so the reptend has length 1 = (3-1)/2. Also, the base-4 expansions of 1/3 = 0.(1) and 2/3 = 0.(2) have two cycles 1 and 2. 3 is the smallest such prime, so a(1) = 3.

%e The base-4 expansion of 1/17 is 0.(0033), so the reptend has length 4 = (17-1)/4. Also, the base-4 expansions of 1/17, 2/17, ..., 16/17 have four cycles 0033, 0132, 1023 and 1122. 17 is the smallest such prime, so a(2) = 17.

%e The base-4 expansion of 1/31 is 0.(00133), so the reptend has length 5 = (31-1)/6. Also, the base-4 expansions of 1/31, 2/31, ..., 30/31 have three cycles 00201, 01203, 02211, 03213, 11223 and 13233. 13 is the smallest such prime, so a(3) = 13.

%t a[n_] := a[n] = For[p = 2, True, p = NextPrime[p], If[MultiplicativeOrder[4, p] == (p-1)/(2n), Return[p]]];

%t Table[Print[n, " ", a[n]]; a[n], {n, 1, 100}] (* _Jean-François Alcover_, Nov 24 2024 *)

%o (PARI) a(n,{base=4}) = forprime(p=2, oo, if((base%p) && znorder(Mod(base,p)) == (p-1)/(n * if(issquare(base), 2, 1)), return(p)))

%Y Cf. A082654, A216371.

%Y In other bases: A101208, A101209, A372798, A372799, A054471, A372800.

%K nonn

%O 1,1

%A _Jianing Song_, May 13 2024