13

Let $p$ be a prime. Is there a classification of the numbers $k \geq 1$ such that $\gcd(k,p^k-1)=1$? If not, can we at least produce an explicit infinite subset? What is known about these $k$?

For the lack of a better name, let me call $k$ good for $p$ if $\gcd(k,p^k-1)=1$. Many numbers are good for $p=2$. This seems to be related but not identical to the OEIS sequence A049093. If $p>2$, all good numbers for $p$ are odd. Most odd numbers are good for $3$; for $k \leq 1000$ the only $24$ exceptions are 39, 55, 117, 165, 195, 253, 273, 275, 351, 385, 429, 495, 507, 585, 605, 663, 715, 741, 759, 819, 825, 897, 935, 975. There is no OEIS sequence for these. For $p=5$ it is similar, but for $p > 5$ the story becomes different.

Background. I have found an equational proof that $p^k$-rings with $p=0$ are commutative when $\gcd(k,p^k-1)=1$ (see Equational proofs of Jacobson's Theorem). Now, I wonder how many cases I have already covered.

Martin Brandenburg
  • 61,443

1 Answers1

14

It is easier to describe non-good (bad) numbers with respect to a given prime $p$. For each such number $k$, there exists a prime $q$ such that $q\mid k$ and $q\mid (p^k - 1)$. It follows that $k$ is multiple of $m_p(q):=q\cdot \mathrm{ord}_q(p)$, where $\mathrm{ord}_q(p)$ is the multiplicative order of $p$ modulo $q$ (which is a divisor of $q-1$). Hence, the set of bad $k$ is formed by the union $$\bigcup_{q\in\mathbb{P}\atop q\ne p} m_p(q) \mathbb{N}^+.$$

UPDATE#2. It also follows that

  • for any odd $k$, there exists a prime $p$ such that $k$ is good for $p$;

  • any even $k$ is bad for all primes $p\geq 3$ since $2\mid \gcd(k,p^k-1)$;

Max Alekseyev
  • 30,425
  • 1
    A nice answer. ######

    BTW, instead of p-non-good name, more logical and much nicer would be name p-bad.

     – Wlod AA Oct 03 '23 at 23:05
  • 1
    Very nice! What can we then say about the density of the bad numbers? – Martin Brandenburg Oct 03 '23 at 23:17
  • 3
    @WlodAA: I've changed non-good to bad per popular request :) – Max Alekseyev Oct 03 '23 at 23:37
  • Max, great, wonderful! ########## Mathematicians and others should be trained in poetry though at the same time they should ignore a great majority of poets and literary critics. – Wlod AA Oct 04 '23 at 00:15
  • 1
    @MaxAlekseyev what are uniformly bad numbers? You mean for all p? – Martin Brandenburg Oct 04 '23 at 09:22
  • Regarding the update: when $k$ is bad for all primes, why is $k$ divisible by $q(q-1)$ for some odd prime $q$? I was assuming that it follows from the first result since "generically" some prime $p$ will generate $(\mathbb{Z}/q\mathbb{Z})^{\times}$, but this argument is not precise at all. I cannot make it work. Where should the $q$ come from? – Martin Brandenburg Oct 04 '23 at 23:33
  • @MartinBrandenburg: Let $k$ be not divisible by any $q(q-1)$. Then, for any prime divisor $q|k$ consider a primitive root $r_q$ modulo $q$, and combine them by CRT into some $r$ modulo $\mathrm{rad}(k)$. By Dirichlet theorem, there is a prime $p\equiv r\pmod{\mathrm{rad}(k)}$. It's easy to check that $k$ is good for $p$. – Max Alekseyev Oct 04 '23 at 23:53
  • I don't understand the final density calculation. If you have a union of arithmetic progressions containing $0$ with pairwise coprime common differences $d_1, \dots, d_k$ then it is true that their union has density $(1-1/d_1) \cdots (1-1/d_k)$, by CRT. The converse is true too: if the union has density given by the product then $d_1, \dots, d_k$ are pairwise coprime, and the integers $q(q-1)$ are not pairwise coprime! – Sean Eberhard Oct 05 '23 at 09:46
  • @MaxAlekseyev Thanks! (So my intuition for the proof was correct, after all.) I would write the proof without the pseudo-contradiction. But I have troubles with the prime $2$. Assume that $k$ is bad for all primes. Construct $p$ as in your comment. Then $k$ is bad for $p$, so there is a prime $q \mid k$ with $q \mid p^k - 1$. Then one can show indeed $q-1 \mid k$. So we are done if $q > 2$. But what do we do when $q = 2$? – Martin Brandenburg Oct 05 '23 at 10:51
  • Apart from the problem with the case $q=2$, this arguement shows the existence of primes $p_k$ such that $k$ is bad for all primes iff $k$ is bad for $p_k$, right? – Martin Brandenburg Oct 05 '23 at 10:55
  • @SeanEberhard: Good point, thanks! I messed up what I thought is a bound with an exact value. The latter can be computed with inclusion-exclusion, but it turns out not relevant anymore (see update#2). – Max Alekseyev Oct 05 '23 at 13:36
  • 1
    @MartinBrandenburg: Yes, prime $2$ "destroys" the nice picture. I was keeping it out of play, and my update#1 was wrong in that respect. Please see update#2. – Max Alekseyev Oct 05 '23 at 13:38