27
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I'm also quite curious to see an answer to see. As of today, it remains unanswered on AoPS forums, too (which, in my opinion, has more olympiad-oriented people than here). $\endgroup$ – TBTD Jun 18 at 20:05
  • 2
    $\begingroup$ John, there you go. artofproblemsolving.com/community/c6h1701907p10936846 $\endgroup$ – TBTD Jun 18 at 23:37
  • 1
    $\begingroup$ By the way, one side note. The OP there in AoPS, I remember sometimes him misquoting problems (often translation issue, from Persian to English). So, be aware that such thing might exist $\endgroup$ – TBTD Jun 18 at 23:38
  • 1
    $\begingroup$ If $q | b^k-a$ then $ord_q(a) | ord_q(b) $. If you can take $q$ such that $gcd(k,q-1) = 1$ then $ord_q(a) = ord_q(b)$ $\endgroup$ – reuns Jun 19 at 22:52
  • 2
    $\begingroup$ I strongly recommend to post this problem on MathOverFlow. This should be reachable with slightly more advanced toolset. $\endgroup$ – TBTD Jun 20 at 15:31
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Your answer starts with "Assume $\gcd(a,b)=1$", but you never discuss what happens if $\gcd(a,b) \neq 1$. Also, the first part of your argument says "Take a prime $q \nmid b-a-1$". However, if $b = a + 1$, then $b - a - 1 = 0$ so there are no primes $q$ which satisfy the condition. $\endgroup$ – John Omielan Jun 20 at 19:46
  • 1
    $\begingroup$ Thank you for your solution. I suggest that instead of using Dirichlet's theorem, you can use the number $Q=q^{\phi (N)}$ and consider $b^Q-a$. Then the answer may be more suitable for an Olympiad question? $\endgroup$ – apple Jun 23 at 12:30
  • $\begingroup$ Can you please clarify the part $q\nmid b-a-h$? Note that $h$ also depends on $q$. $\endgroup$ – Sungjin Kim Jun 24 at 15:58
  • 1
    $\begingroup$ @i707107 $h$ doesn't depend on $q$ only on $a,b,p_1 \ldots p_j$. We have $b-a-h \ne 0$ because $p^{v_p(a)}$ (the $p$ of the restriction at the beginning) divides $h,a$ but not $b$ $\endgroup$ – reuns Jun 25 at 9:11
  • 1
    $\begingroup$ Apple's idea is that for any $r$ we can look at $$\frac{b^{q^r}-a}{h}, \qquad q^r\equiv 1 \bmod N$$ most of the argument will stay the same as in the case $r=1$ and that freedom on $r$ will help to find $q$ such that $\frac{b^{q^r}-a}{h} \not \equiv 1 \bmod q$ $\endgroup$ – reuns Jun 25 at 15:23
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can you explain more about the calculation $v_{p_i}$, I cannot follow that part. $\endgroup$ – Sungjin Kim Jun 21 at 20:25
  • 2
    $\begingroup$ @i707107 I used the LTE theorem, a very well-known theorem. You can see here for proofs. $\endgroup$ – color Jun 22 at 4:03
  • 1
    $\begingroup$ @i707107 I changed my answer a lot but I got a simple case where everything works fine. I didn't study color's answer, if someone sees how he does / does not solve the "$b-a-h=0$ problem" $\endgroup$ – reuns Jun 22 at 18:47
  • 2
    $\begingroup$ Thank you. Your solution seems similar to reuns's. I suggest that instead of using Dirichlet's theorem, you can use the number $Q^{\phi (N)}$. Then the answer may be more suitable for an Olympiad question? Your solution seems similar to reuns's. $\endgroup$ – apple Jun 23 at 12:31
  • $\begingroup$ @apple Thanks. I will edit my solution later. $\endgroup$ – color Jun 23 at 12:33
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ There is a problem in the step where you say that $a^{p-1} \equiv 1 \pmod p$ and $b^{p-1} \equiv 1 \pmod p$ implies $ord_p(a) = ord_p(b) = 1$. This is not necessarily true, because $ord_p(a)$ is the smallest possible exponent $x$ such that $a^x \equiv 1 \pmod p$. So in general it is possible that $ord_p(a)$ and $ord_p(b)$ are different divisors of $p-1$. For example, $2^{7-1} \equiv 1 \pmod 7$ and $3^{7-1} \equiv 1 \pmod 7$, but $ord_7(2) = 3 \neq 6 = ord_7(3)$. $\endgroup$ – Tob Ernack Jun 21 at 3:14
  • 1
    $\begingroup$ Also note that $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)=1$ means $a \equiv b \equiv 1 \pmod p$, so $p \mid a - 1$ and $p \mid b - 1$. For $a, b \gt 1$, this is only true for the finite # (if any) of primes $p$ which divide both $a - 1$ and $b - 1$. $\endgroup$ – John Omielan Jun 21 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.