1
$\begingroup$

Let $a(n)$ be A001122, i.e., an integer sequence of primes with primitive root $2$.

I conjecture that iff $n$ is prime that belong to $\{a(n)\}$, then for $1 \leqslant k \leqslant n-1$ there always exists smallest nonnegative integer $m$ such that $n \mid (2^{m} k + 1)$ and the set of values of $m$ taken for each $k$ in range $1 \leqslant k \leqslant n-1$ is a permutation of $\{0,1,\dotsc,n-2\}$.

It also looks like other $m$ (following after the smallest) such that $n \mid (2^mk+1)$ for certain $k$ have the form $m + q(n-1), q \in \mathbb{N}$. In the same time, for all other $n$ there always exists at least one $k$ such that for any $m \geqslant 0$ we have $n \nmid (2^mk+1)$.

Here is the PARI/GP program to check it numerically:

\\ filter taken from the OEIS page isok1(n) = znorder(Mod(2, n)) == (n-1) \\ filter for checking my conjecture isok2(n) = {my(A, v1); v1 = vector(n-1, i, 0); for(i=1, n-1, A = 0; while(!((2^A*i+1)%n==0), A++); v1[i] = A); vecsort(v1) == vector(n-1, i, i-1)} my(z=2); for(k=1, 299, while(!(isok1(prime(z))), z++); print(isok2(prime(z))); z++)

Here are some examples:

 n = 3 (1,1) -> (2^1*1 + 1) mod 3 == 3 mod 3 == 0 (0,2) -> (2^0*2 + 1) mod 3 == 3 mod 3 == 0 (1,0) sorted is (0,1) n = 5 (2,1) -> (2^2*1 + 1) mod 5 == 5 mod 5 == 0 (1,2) -> (2^1*2 + 1) mod 5 == 5 mod 5 == 0 (3,3) -> (2^3*3 + 1) mod 5 == 25 mod 5 == 0 (0,4) -> (2^0*4 + 1) mod 5 == 5 mod 5 == 0 (2,1,3,0) sorted is (0,1,2,3) n = 11 (5,1) -> (2^5*1 + 1) mod 11 == 33 mod 11 == 0 (4,2) -> (2^4*2 + 1) mod 11 == 33 mod 11 == 0 (7,3) -> (2^7*3 + 1) mod 11 == 385 mod 11 == 0 (3,4) -> (2^3*4 + 1) mod 11 == 33 mod 11 == 0 (1,5) -> (2^1*5 + 1) mod 11 == 11 mod 11 == 0 (6,6) -> (2^6*6 + 1) mod 11 == 385 mod 11 == 0 (8,7) -> (2^8*7 + 1) mod 11 == 1793 mod 11 == 0 (2,8) -> (2^2*8 + 1) mod 11 == 33 mod 11 == 0 (9,9) -> (2^9*9 + 1) mod 11 == 4609 mod 11 == 0 (0,10) -> (2^0*10 + 1) mod 11 == 11 mod 11 == 0 (5,4,7,3,1,6,8,2,9,0) sorted is (0,1,2,3,4,5,6,7,8,9)

Conjecture has been tested up to $a(500) = 10789$ without counterexamples. Here I mean that I checked it for each term of $\{a(n)\}$ up to $n = 500$. It is an open problem to prove (or somehow check) that for all other $n$ there always exists at least one $k$ such that for any $m \geqslant 0$ we have $n \nmid (2^mk+1)$.

Is there a way to prove it? Is this result known in literature?

$\endgroup$
7
  • 5
    $\begingroup$ Looks like $A=\log_2(-1/B)$. As $B$ is non-zero modulo $p$, $-1/B$ is uniquely defined modulo $p$. $A$ is uniquely defined modulo $p-1$ because $2$ is assumed primitive. The permutations $f$ and $g$ are there simply to obfuscate. $\endgroup$ Commented Aug 12 at 10:38
  • $\begingroup$ @JyrkiLahtonen, thank you for comment! What do you mean? In my conjecture, $A_{f(i)}$ is a nonnegative integer $\leqslant n-2$ and $B_{g(i)}$ is a natural number $\leqslant n-1$. But what does your notation means? $\endgroup$ Commented Aug 12 at 10:47
  • 1
    $\begingroup$ Certainly, you just need one bijection $g:A\to B,$ which is defined as $g(k)=-2^{n-1-k}\bmod n.$ You can always assume $f(k)=k.$ $\endgroup$ Commented Aug 12 at 13:36
  • $\begingroup$ @ThomasAndrews, thank you for comment! To avoid misunderstanding, I have edited the question. Please check if you comment is still correct and write me about it. $\endgroup$ Commented Aug 12 at 13:44
  • 1
    $\begingroup$ Even that is way more complicated than you need to put it, but it is slightly better. This is true, but essentially trivial, since $2$ being a primitive root is equivalent, for odd $n$ at least, to the map $k\mapsto 2^k\bmod n$ being a bijection $\{0,\dots,n-2\}\to\{1,\dot,n-1\}.$ In your formulation he $+1$ can be replaced with $+b$ for any integer $0<b<n.$ $\endgroup$ Commented Aug 12 at 13:54

0

Reset to default

You must log in to answer this question.