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

Question

Let $a$, $b$ be distinct positive integers greater than $1$. Prove that there exist infinitely many prime numbers $p$ such that $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)$.

(Here $\mathrm{ord}_p(a)$ is the smallest integer $k>0$ such that $a^k\equiv1\pmod p$.)

This problem is from the 2018 Iranian Math Olympiad. I cannot find any sources for the official answer. I have tried to solve it, but it didn't work. The only thing that I found out is that if $p|\mathrm{gcd}(a-1,b-1)$, then $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)=1$.

Sorry for the lack of information. That is all I have to say.

How can I solve the orange problem? If any sources were known, please post the answers in the answer section here. Any answers, solutions or comments will be appreciated.

If this question cannot be answered, I will delete this post immediately.

Answer 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)$.

Answer 2

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.

Answer 3

Let $a = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{n}^{\alpha_{n}}$ and $b = q_{1}^{\beta_{1}} q_{2}^{\beta_{2}} \cdots q_{m}^{\beta_{m}}$ be the prime factorization of $a$ and $b$. Define $C$ the set of prime number such that $ord_{p}(a) = ord_{p}(b) = 1$.

Let $S = \{\ p_{1}, p_{2}, \ldots, p_{n}, q_{1}, q_{2}, \ldots, q_{m}\ \}$ and $\mathbb{P}$ the set of prime numbers. Note that if $p$ is a prime number such that $p \in (\mathbb{P} - S)$ then by Fermat's little theorem $a^{p-1} \equiv 1 \pmod{p}$ and $b^{p -1} \equiv 1 \pmod{p}$, hence it is not difficult to show that $ord_{p}(a) = ord_{p}(b) = 1$, i. e., $p \in C$. Therefore $(\mathbb{P} - S) \subset C$.

Finally, note that if $C$ is finite then $(\mathbb{P} - S)$ is finite and so $\mathbb{P} = S \cup (\mathbb{P} - S)$ is finite which contradicts Euclid's theorem.

Answer 4

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.

Answer 5

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.

Answer 6

WLOG $a<b$
Take an infinite set of prime numbers (strictly increasing) such that $p_1$ is sufficiently big and $$p_{i+1} \overset{\small\phi(a-b)\displaystyle\prod_{j=1}^{j=i}\phi(a^{p_j}-b)}{\huge\equiv\mathrel{\mkern-5mu}\equiv\mathrel{\mkern-5mu}\equiv\mathrel{\mkern-5mu}\equiv\mathrel{\mkern-5mu}\equiv\mathrel{\mkern-5mu}\equiv\mathrel{\mkern-5mu}}\hspace{5 pt} 1$$ Existence of such primes is assured due to small Dirichlet theorem that can be proved easily with $Ord$ function. (Not to be confused with the main Dirichlet theorem that is non-elementary)
Now we prove that there are infinitely many prime divisors of the infinite set $\{a^{p_i}-b\}$ that don't divide $a-b$:
Note that if $i>j$ and $q^{m} \mid gcd(a^{p_i}-b,a^{p_j}-b)$, then $$q^m \mid a^{p_j}-b \implies \phi(q^m)|\phi(a^{p_i}-b)\implies p_i \overset{\phi(q^m)}{\equiv\mathrel{\mkern-3mu}\equiv\mathrel{\mkern-3mu}\equiv} 1$$ $$, q^m |a^{p_i}-b\overset{q^m}{\equiv} a-b \implies q^m \mid a-b$$ So one can see that the if $p$ is a prime dividing $a-b$, then $V_p(\{a^{p_i}-b\})$ is bounded. Hence the claim.
So we can take a prime $q$ dividing $a^{p_i}-b$ with $gcd(q,a-b)=1$. One can see that $$Ord_q(b)=Ord_q(a^{p_i})$$ Hence if $Ord_q(b)\not=Ord_q(a)$, then $Ord_q(b)=p_iOrd_q(a) \implies p_i|Ord_q(b)|q-1$.
So all of the prime divisors $q$ of $a^{p_i}-b$ either divide $a-b$ or $q\overset{p_i}{\equiv}1$.
So $a^{p_i}-b=R_i \Pi (p_ik_i+1)^{\alpha _i}$ where $R_i$ divides $a-b$.
Taking modulo $p_i$ we have $p_i \mid a-b-R_i\implies a=b+R_i$ which is a contradiction with the initial assumption $a<b$. So for all $a^{p_i}-b$ there exist at least one prime divisor $q_i$ with $Ord_{q_i}(b)=Ord_{q_{i}}(a), q_i \nmid b-a$. Now for assuring of infinite such primes, assume (for the sake of contradiction) that there are finite such primes, namely $q_1,q_2,\dotsb q_t$. Back to the beginning of the problem, make another infinite set of primes, but with an additional condition : $$p_{i+1}\overset{q_i-1}{\equiv}1$$ For all $1\leqslant i\leqslant t$. The existence of these primes will again be assured by small Dirichlet theorem but this time all $\{a^{p_i}-b\}$'s will be coprime to all of the $q_i$'s since otherwise : $$q_i|a^{p_i}-b , p_{i}\overset{q_i-1}{\equiv}1 \implies a^{p_i}-b\overset{q_i}{\equiv}a-b \implies q_i|a-b$$ Which is a contradiction. So the new prime that this new sequence of primes generates as an answer will be different to all the former $q_i$'s. Contradiction with the assumption that $q_i$'s are the only answers. (Finite answers)
So there are infinitely many such primes and the proof is complete.