# If $\mathrm{ord}_p(b)\mid \mathrm{ord}_p(a)$ for all sufficiently large prime p, is $b$ necessarily a power of $a$

arithmeticgroup-theorymodular arithmeticnumber theoryprime numbers

Let $$a$$ and $$b$$ be integers, and denote by $${\rm ord}_p(a)$$ the $$\textbf{multiplicative order}$$ of $$a$$ modulo $$p$$.

Assume that there exists a constant $$K$$ such that for all prime $$p>K$$, $${\rm ord}_p(b)$$ divides $${\rm ord}_p(a)$$.
Is it that $$b$$ is a power of $$a$$?

I came up with this question, but I don't know if it's true or false, and I have no idea how to deal with it. Could you help me?

Thanks.

The (nontrivial) answer seems to be yes. Assume $$a,b \geq 2$$ to make matters simpler. The proof is a bit complex and it can probably be improved – I think that we can deal with sign issues by using a little bit more caution.

Let $$k \geq 3$$ be any large prime number (not dividing by any of the nonzero valuations at any prime of $$a$$ or $$b$$), and consider the number fields $$K_a$$ and $$K_b$$, where $$K_x$$ is the Galois closure of $$R_x=\mathbb{Q}(x^{1/k})$$. Now, $$K_x$$ is the tensor product of $$R_x$$ and $$C=\mathbb{Q}(e^{2i\pi/k})$$.

A large enough prime $$p$$ is totally split in $$K_x$$ iff it is split in $$R_x$$ and $$C$$, iff it is congruent to $$1$$ mod $$k$$ and $$a$$ is a $$p$$-th power mod $$k$$, iff $$X^k-x$$ splits simply in $$\mathbb{F}_p$$.

So, assume that $$p$$ is a large prime that splits completely in $$K_a$$. Then $$k|p-1$$ and $$a$$ is a $$k$$-th power mod $$p$$. Thus $$\mathrm{ord}_p(a)$$ divides $$\frac{p-1}{k}$$. Thus the same holds for $$\mathrm{ord}_p(b)$$, and thus (as $$k|p-1$$) $$b$$ is a $$k$$-th power in $$\mathbb{F}_p$$ and thus $$p$$ splits totally in $$K_b$$.

It follows by Cebotarev that $$K_b \subset K_a$$ and by dimension that $$K_b=K_a$$. In other words, $$R_b$$ is a subextension of $$K_a$$ (of degree $$p$$). Now, the Galois group of $$K_a$$ over $$\mathbb{Q}$$ can easily be shown to be the semi-direct product of $$\mathbb{F}_k$$ and $$\mathbb{F}_k^{\times}$$ (the latter acting on the former by multiplication), so it has cardinality $$k(k-1)$$.

How many subgroups of index $$k$$ does it have? Well, such a subgroup $$H$$ has order $$k-1$$, so its intersection with $$Gal(K_a/C) \cong \mathbb{F}_k$$ is trivial, so its projection to $$Gal(C/\mathbb{Q}) \cong \mathbb{F}_k^{\times}$$ is injective, hence an isomorphism and $$H$$ is cyclic, generated by its unique element above a fixed generator of $$Gal(C/\mathbb{Q})$$.

It follows that there are exactly $$k$$ extensions $$H$$ of index $$k$$, and thus $$K_a$$ has exactly $$k$$ subextensions of degree $$k$$ over $$\mathbb{Q}$$. Moreover, it’s easy to see that the $$\mathbb{Q}(a^{1/k}e^{2il\pi/k})$$, $$0 \leq l < k$$, all fit this description and are pairwise distinct (otherwise two of them are equal and it follows that one extension isomorphic to $$R_a$$ contains a $$k$$-th root of unity, which impossible by dimension since $$k-1$$ doesn’t divide $$k$$), and that the only one which is a subset of $$\mathbb{R}$$ is $$R_a$$. Thus $$R_b=R_a$$.

Let, for an automorphism $$\sigma$$ and $$x=a,b$$, $$m(\sigma)$$ be the number in $$\mathbb{F}_k^{\times}$$ such that $$\sigma(e^{2i\pi/k})=e^{2i\pi m(\sigma)/k}$$, and $$n_x(\sigma)$$ be the number in $$\mathbb{F}_k$$ such that $$\sigma(x^{1/k})x^{-1/k}=e^{2i\pi n_x(\sigma)/k}$$.

In $$Gal(K_a/C)$$, it’s easy to see that $$\sigma \longmapsto n_x(\sigma)$$ is an isomorphism, and thus $$n_b=sn_a$$ for an integer $$k > s \geq 1$$.

Therefore, if $$x= b^{1/k}a^{-s/k} \in R_a=R_b$$, the stabilizer in $$Gal(K_a/\mathbb{Q})$$ of $$x$$ contains $$Gal(K_a/C)$$ (so is divisible by $$k$$) and $$Gal(K_a/R_a)$$ (so is divisible by $$k-1$$) so is all of $$Gal(K_a/\mathbb{Q})$$, thus $$b^{1/k} \in \mathbb{Q}a^{s/k}$$. Thus $$b/a^s$$ is a $$k$$-th power in $$\mathbb{Q}$$.

In other words, consider the vectors $$v_a=(v_p(a))_{p}$$ of $$p$$-adic valuations of $$a$$ for all primes $$p$$, and the same vector $$(v_p(b))_{p}$$. We know that these vectors have finite support and are collinear mod every large prime number: it follows (using, say, determinants) that they are collinear in $$\mathbb{Q}$$.

In other words, we can find pairwise coprime positive integers $$n,m$$ and an integer $$t$$ such that $$b=t^n, a=t^m$$.

Then, if $$p$$ is a large prime, $$\mathrm{ord}_p(b)=\frac{\mathrm{ord}_p(t)}{\mathrm{ord}_p(t) \wedge n}$$. Using a similar argument for $$a$$, it follows that for almost every prime, $$\mathrm{ord}_p(t) \wedge n$$ is a multiple of $$\mathrm{ord}_p(t) \wedge m$$. But these two numbers are coprime, so there are finitely many primes $$p$$ such that the multiplicative order of $$t$$ mod $$p$$ is divisible by a prime dividing $$m$$.

But if $$m>1$$, this is in gross contradiction to Zsigmondy’s theorem (or, here, a LTE-based elementary statement saying that if $$p$$ is a prime divisor of $$m$$, there are infinitely many prime numbers dividing $$t^{p^l}-1$$ for some $$l \geq 1$$). So $$t=a$$, QED.

Edit: I know it’s been a year, but I realized that the argument could be made clearer. So let $$a,b \geq 2$$ be such that the multiplicative order of $$b$$ mod $$p$$ divides that of $$a$$ for almost all primes $$p$$. We want to show that $$b$$ is a power of $$a$$.

First, assume that $$a,b$$ are multiplicatively dependent, ie there are positive integers $$r,s,t$$ with $$s,t$$ coprime such that $$a=r^s$$, $$b=r^t$$. For $$n \geq 10$$, then $$r^{sn}-1$$ has a primitive prime divisor $$p$$ by Zsigmondy, so that $$r^{tn}-1$$ is also divisible by $$p$$. Thus $$p$$ divides the gcd of $$r^{tn}-1$$ and $$r^{sn}-1$$, which is $$r^n-1$$. But as $$p$$ is primitive, $$n \geq sn$$, so $$s=1$$ and $$b$$ is a power of $$a$$.

So we can assume that $$a,b$$ are multiplicatively independent. In other words, there is a large prime $$k$$ and primes $$s,t$$ such that $$k$$ doesn’t divide $$v_s(a)v_t(b)-v_t(a)v_s(b)$$ (in particular, $$a,b$$ are not $$k$$-th powers).

Let $$C=\mathbb{Q}(\mu_k)$$, $$R_x=\mathbb{Q}(x^{1/k})$$ and $$K_x=R_xC$$ for $$x=a,b$$. Note that $$K_a,K_b$$ are Galois over $$\mathbb{Q}$$.

As $$C$$ and $$R_x$$ have coprime degrees over $$\mathbb{Q}$$ ($$k-1$$ and $$k$$, respectively), $$C \otimes R_x \rightarrow K_x$$ is an isomorphism. Moreover, a prime number $$p$$ splits totally in $$K_x$$ iff it splits totally in $$C$$ and $$R_x$$, iff $$k|p-1$$ and $$x$$ is a $$k$$-th power mod $$p$$, iff $$k|p-1$$ and the order of $$x$$ mod $$p$$ divides $$\frac{p-1}{k}$$. In particular, for almost every $$p$$, if $$p$$ splits totally in $$K_a$$, then $$p$$ splits totally in $$K_b$$.

By Cebotarev, since $$K_a$$ and $$K_b$$ are Galois over $$\mathbb{Q}$$ with the same degree, this implies that $$K_b \subset K_a$$ hence $$K_b=K_a$$.

By Kummer theory (as $$K_x/C$$ is cyclic of Galois group $$\mathbb{F}_k$$), this implies that there are integers $$0 \leq x,y < k$$ not both zero such that $$a^xb^y$$ is a $$k$$-th power in $$C$$.

Taking norms, we see that $$a^{(k-1)x}b^{y(k-1)}$$ is the $$k$$-th power of a rational number. So $$k|xv_s(a)+yv_s(b)$$, $$k|xv_t(a)+yv_t(b)$$, which contradicts the assumption on $$k,s,t$$.