CircularPairpK

Let $k\geq 3$ be a positive integer. Let $p$ be a prime. The task of the following function is to determine directly whether $p$ is in the Modisett Primes $\mathcal P_k$. Namely, $p\in\mathcal P_k$ if and only if one of the following is true: (1) $p$ divides $k$, (2) for some $s\in\mathbb N$, $k$ is a factor of $p^s-1$ and the finite field $(F_{p^s},\Phi)$ where $\Phi$ is the multiplicative subgroup of $F^*_{p^s}$ is of order $k$.

=python IsCircular:= function(p, k) local i,j,a,b,c,d,e,n,s,t,zeta,C,W; # p has to be a prime before we go on if not(IsPrime(p)) or (p < 0) or (k < 3) then Print("Usage: IsCircular( p, k )\nwhere p is a prime and k an integer >= 3."); return; fi; # A Ferrero pairs (p^s, k) satisfies k divides (p^s - 1) # When p divides k, no Ferrero pair (p^s, k) to be found # By definition, p is in P_k if k mod p = 0 then return(false); fi; zeta:= E(k); C:= List([1..k-1], i-> zeta^0-zeta^i); for i in [1..k-2] do if k mod i = 0 then a:= C[i]; for j in [1..k-2] do b:= C[j]; for s in [j+1..k-1] do c:= C[s]; for t in [1..k-1] do d:= C[t]; if (i <> j) and (i <> s) and (t <> j) and (t <> s) and not(k mod t = 0) then n:= Norm(a*d-b*c); if n mod p = 0 then return(false); fi; fi; od; od; od; fi; od; return(true); end;

For example, we know that $\mathcal P_{14}=\{2, 7, 29, 43, 71, 113, 127, 197, 211, 239, 281, 337, 379, 491, 547, 659, 701, 1051, 1093, 1289\}$, and using the above function, we have =python GAP> IsCircular(43,14); false GAP> IsCircular(23,14); true

The following code using MAPLE may be used when $k$ divides $p-1$. It is in general faster as all computations are in integers modulo $p$.

=python with(numtheory); isCircular := proc (p, k) local u, v, s, t, f, T, z, Fin; T := true; z := 2; Fin := true; while `mod`(order(z, p), k) <> 0 do z = z+1 end do; z := `mod`(Power(z, order(z, p)/k), p); ## z is of order k modulo p print("order of ", z, "is", k); for u to k-1 do for v from u+1 to k do for s from v to k do for t to k do if u <> s and v <> t and s <> t then f := `mod`(((`mod`(Power(z, u), p))-1)*((`mod`(Power(z, t), p))-1) -((`mod`(Power(z, s), p))-1)*((`mod`(Power(z, v), p))-1), p); T := T and f <> 0; if `not`(T) then return T end if end if end do end do end do end do; return T end proc;