Prove that there exist infinitely many prime numbers $p$ such that $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)$.

Solution 1:

Let $a > b\ge 2$ and $p_1,\ldots,p_j$ be a list of primes containing the primes dividing $a$. Let $c > a+b$ and $N = \prod_{i=1}^j (p_i-1) p_i^c$. For a prime power $q^r \equiv 1 \bmod N$, if $p_i \nmid b$ then $b^{q^r}-a \equiv b-a {\scriptstyle\ \not \equiv \ 0}\bmod p_i^c$, if $p_i | b$ then $b^{q^r}-a \equiv -a {\scriptstyle\ \not \equiv \ 0}\bmod p_i^c$.

Let $h =\prod p_i^{v_{p_i}(\textstyle b^{q^r}-a)}= (\prod_{p_i | b} p_i^{v_{p_i}(a)}) (\prod_{p_i \nmid b} p_i^{v_{p_i}(b-a)} )$ $\scriptstyle(\text{note it doesn't depend on } q)$ and

$$\frac{b^{q^r}-a}{h} = \prod Q_l^{e_l} \qquad \qquad \scriptstyle (\text{which is coprime with } p_1\ldots p_j)$$

$b^{q^r}-a \equiv 0 \bmod Q_l, a \not \equiv 0 \bmod Q_l$ implies $\text{order}(a \bmod Q_l) \ |\ \text{order}(b \bmod Q_l)$.

If also $\gcd(q,Q_l-1) = 1$ then $\text{order}(a \bmod Q_l)= \text{order}(b \bmod Q_l)$.

Assume $\forall l, \gcd(q,Q_l-1) \ne 1$, then $q | Q_l-1, Q_l = m_l q+1$ and $$\frac{b^{q^r}-a}{h} = \prod (m_lq+1)^{e_l} \equiv 1 \bmod q$$ Thus it suffices to choose $q \nmid b-a-h$, $q \nmid N, r = \phi(N)$ to obtain $\frac{b^{q^r}-a}{h} \not \equiv 1 \bmod q$ so that for some $Q_l | \frac{b^{q^r}-a}{h} $ we'll have $ \gcd(q,Q_l-1) = 1$ and $\text{order}(a \bmod Q_l)= \text{order}(b \bmod Q_l)$.

Add $Q_l$ to the $p_i$ and repeat to generate infinitely many primes such that $\text{order}(a\bmod P)=\text{order}(b\bmod P)$.

Solution 2:

Without loss of generality assume that $b>a$. Let $p_1,p_2,...,p_k$ be all prime numbers that divide $b-a$ or $b$.

We shall prove by induction that there are infinitely many distinct prime numbers $P_1,P_2,...$ different from $p_1,p_2,...,p_k$ such that for every $ i, ord_{P_i}(a)=ord_{P_i}(b)$.

Assume that there exists $n$ distinct prime numbers $P_1,P_2,...,P_n$, different from $p_1,p_2,...,p_k$ such that for every $ i \leq n, ord_{P_i}(a)=ord_{P_i}(b)$. Note that $n$ can be $0$, which means we can assume that there are no $P_i$ satisfy the condition from the beginning.

Let $c> a+b$ be a positive integer . Let $Q = \prod_{j=1}^k (p_j-1) p_j^c \prod_{i=1}^n (P_i-1) P_i^c$. If $n=0$ then $Q = \prod_{j=1}^k (p_j-1) p_j^c$

Let $q$ be a large prime such that $q > Q,c,p_1,p_2,...,p_k,P_1,P_2,...,P_n$. Then $gcd(Q,q)=1$, hence $q^{\phi(Q)} \equiv 1 \pmod Q$

Consider the positive integer $a^{q^{\phi(Q)}}-b$. Then for every $i \leq n, a^{q^{\phi(Q)}}-b \equiv a-b \ { \not \equiv 0 } \pmod {P_i^c}$

For every $i \leq k$, if $p_i \nmid a$ then $a^{q^{\phi(Q)}}-b \equiv a-b \pmod {p_i^c}$. Since $v_{p_i}(b-a)<c$ so $v_{p_i}(b-a)=v_{p_i}(a^{q^{\phi(Q)}}-b)$. If $p_i | a$ then $a^{q^{\phi(Q)}}-b \equiv -b \pmod {p_i^c} \Rightarrow v_{p_i}(b)=v_{p_i}(a^{q^{\phi(Q)}}-b)$. In short, for every $i \leq k, v_{p_i}(b)=v_{p_i}(a^{q^{\phi(Q)}}-b)$.

Let $d =\prod p_i^{v_{p_i}(a^{q^{\phi(Q)}}-b)}= (\prod_{p_i | a} p_i^{v_{p_i}(b)}) (\prod_{p_i \nmid a} p_i^{v_{p_i}(b-a)})$.

Then $d$ is a constant and $\frac{a^{q^{\phi(Q)}}-b}{d}$ is coprime with $p_1,p_2,...,p_k,P_1,P_2,...,P_n$.

If for every prime $P$ that divides $\frac{a^{q^{\phi(Q)}}-b}{d}, q \ | \ P-1$, then $$\frac{a^{q^{\phi(Q)}}-b}{d} \equiv 1 \pmod q \Leftrightarrow a^{q^{\phi(Q)}}-b \equiv a-b \equiv d \pmod q \Leftrightarrow q \ | \ d+b-a$$

However $q \nmid d+b-a$ since $q > Q > d+b-a > 0$, therefore there must be a prime $P_{n+1}$ that divides $\frac{a^{q^{\phi(Q)}}-b}{d}$, different from $p_1,p_2,...,p_k,P_1,P_2,...,P_n$,

and $gcd(P_{n+1}-1,q)=1$, hence $gcd(ord_{P_{n+1}}(a),q)=gcd(ord_{P_{n+1}}(b),q)=1$

Since $b \equiv a^{q^{\phi(Q)}} \pmod {P_{n+1}}$ then $$b^{ord_{P_{n+1}}(a)} \equiv 1 \pmod {P_{n+1}} \Rightarrow ord_{P_{n+1}}(b)|ord_{P_{n+1}}(a)$$ $$a^{{q^{\phi(Q)}}{ord_{P_{n+1}}(b)}} \equiv 1 \pmod {P_{n+1}} \Rightarrow ord_{P_{n+1}}(a)|q^{\phi(Q)}{ord_{P_{n+1}}(b)} \Rightarrow ord_{P_{n+1}}(a)|ord_{P_{n+1}}(b)$$ hence $ord_{P_{n+1}}(a)=ord_{P_{n+1}}(b)$.

Continuing the process above, it can be seen that there are infinitely many distinct prime numbers $P_1,P_2,...$ different from $p_1,p_2,...,p_k$ such that for every $ i, ord_{P_i}(a)=ord_{P_i}(b)$.

This answer is quite similar to @reuns 's, I am really sorry. Any comments or edits suggested will be appreciated.

Solution 3:

HINT.-If $$a^k\equiv1\pmod p\\b^k\equiv1\pmod p$$ and you want to find some other prime $q$ such that $$a^l\equiv1\pmod q\\b^l\equiv1\pmod q$$ because of $a^l=a^k\times a^{l-k}$, take for $n=1,2,3,\cdots$ the powers $a^{k+n}$ and $b^{k+n}$ till you have the numbers $a^{k+n}-1$ and $b^{k+n}-1$ non coprimes. (Note that if always this two numbers are coprimes then the proposition is false). Example: $$3^5\equiv1\pmod {11}\\4^5\equiv1\pmod {11}$$ and $$3^6=2^3\cdot7\cdot13+1\\4^6=3^2\cdot5\cdot7\cdot13+1$$ Thus you get two other examples whith $(3,4)$. You have $$3^6\equiv1\pmod q\\ 4^6\equiv1\pmod q$$ for the values $q=7$ and $13$.

It should be clear that not always the new prime will appear so fast.

Solution 4:

This is a partial answer only, showing that there is at least one prime $p$ with $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)$.

Choose a prime $q$ large enough to have $ab\not\equiv 2\pmod q$. As a result,$(ab)^q-1\not\equiv 1\pmod q$, showing that there is prime $p\mid (ab)^q-1$ with $p\not\equiv1\pmod q$; that is, with $(q,p-1)=1$. In view of $a^qb^q\equiv 1\pmod p$, this implies $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)$.

Showing that there are infinitely many primes $p$ with the property in question seems trickier.