Taha1381 wrote: Prove that for any natural numbers$a,b$ there exist infinity many prime numbers $p$ so that $Ord_p(a)=Ord_p(a)$(Proving that there exist infinity prime numbers $p$ so that $Ord_p(a) \ge Ord_p(b)$ will get a partial mark) Do you mean $Ord_p(a)=Ord_p(b)$? Also, I'm not sure if this is correct, but can't you just choose a large $p$ such that $p$ is larger than $a$ and $b$, which would make $Ord_p(a)=Ord_p(b)=0$?

NikoIsLife wrote: Taha1381 wrote: Prove that for any natural numbers$a,b$ there exist infinity many prime numbers $p$ so that $Ord_p(a)=Ord_p(a)$(Proving that there exist infinity prime numbers $p$ so that $Ord_p(a) \ge Ord_p(b)$ will get a partial mark) Do you mean $Ord_p(a)=Ord_p(b)$? Yes edited

I have a quite non-elementry proofs for both parts the main problem uses Zsigmondy's theorem which is not easy to prove at all(and unfortunatly not acceptable in Iran third round but a n elementry proof exists using cyclotomic polynomials)but the proof is quite similar to the easy version.I will post the solution of easy version seeking for someone solve the main problem in an elementry way. Consider the sequence $\{ b^k-a \}$ for all large enough $k$ so that all the terms become positive. By kobayashi's theorem there are infinity primes dividing one term of this sequence it is easy to see all such primes satisfy the condition. Remark: The use of Kobayashi's theorem can be eliminated. The method of the alternate proof is similar to the proof of schur's theorem.However Kobayashi's theorem is not that complicated to prove itself.

NikoIsLife wrote: Also, I'm not sure if this is correct, but can't you just choose a large $p$ such that $p$ is larger than $a$ and $b$, which would make $Ord_p(a)=Ord_p(b)=0$? I think you misunderstood the notation of order modulo $n$.Your proof is indeed wrong since the order is always positive.

Taha1381 wrote: NikoIsLife wrote: Also, I'm not sure if this is correct, but can't you just choose a large $p$ such that $p$ is larger than $a$ and $b$, which would make $Ord_p(a)=Ord_p(b)=0$? I think you misunderstood the notation of order modulo $n$.Your proof is indeed wrong since the order is always positive. Oh, I'm sorry. I thought that $Ord_p(a)$ meant the highest power of $p$ which divides $a$.

Taha1381 wrote: I have a quite non-elementry proofs for both parts the main problem uses Zsigmondy's theorem which is not easy to prove at all(and unfortunatly not acceptable in Iran third round but a n elementry proof exists using cyclotomic polynomials)but the proof is quite similar to the easy version.I will post the solution of easy version seeking for someone solve the main problem in an elementry way. Consider the sequence $\{ b^k-a \}$ for all large enough $k$ so that all the terms become positive. By kobayashi's theorem there are infinity primes dividing one term of this sequence it is easy to see all such primes satisfy the condition. Remark: The use of Kobayashi's theorem can be eliminated. The method of proof is similar to the proof of schur's theorem.However Kobayashi's theorem is not that complicated to prove itself. if you take $b^p-a$ for large primes p there is a $q|b^p-a$ and $(p,q-1)=1$ (because if this not true you must have $b^p-a=1 mod \,p$ use Fermat theorem)it is clear then $ord_p a=ord_p b$.you must prove there are infinite primes q with these condition and you can prove it easily by Dirichlet theorem:take a p which is not equal to $p_i\, mod \,q_i$(you can do the last part without Dirichlet but it is a little harder)

alip wrote: Taha1381 wrote: I have a quite non-elementry proofs for both parts the main problem uses Zsigmondy's theorem which is not easy to prove at all(and unfortunatly not acceptable in Iran third round but a n elementry proof exists using cyclotomic polynomials)but the proof is quite similar to the easy version.I will post the solution of easy version seeking for someone solve the main problem in an elementry way. Consider the sequence $\{ b^k-a \}$ for all large enough $k$ so that all the terms become positive. By kobayashi's theorem there are infinity primes dividing one term of this sequence it is easy to see all such primes satisfy the condition. Remark: The use of Kobayashi's theorem can be eliminated. The method of proof is similar to the proof of schur's theorem.However Kobayashi's theorem is not that complicated to prove itself. if you take $b^p-a$ for large primes p there is a $q|b^p-a$ and $(p,q-1)=1$ (because if this not true you must have $b^p-a=1 mod \,p$ use Fermat theorem)it is clear then $ord_p a=ord_p b$.you must prove there are infinite primes q with these condition and you can prove it easily by Dirichlet theorem:take a p which is not equal to $p_i\, mod \,q_i$(you can do the last part without Dirichlet but it is a little harder) Can you show your proof without Dirichlet for the last part and also how this implies the primes found by this way are distinct?

Taha, can you post your full proof? Thanks.

Yes Taha please post your solution with zsigmondy theorem... Thanks... Can someone tell me what is kobayashi's theorem?

Anaskudsi wrote: Yes Taha please post your solution with zsigmondy theorem... Thanks... Can someone tell me what is kobayashi's theorem? My solution for the main problem seems incorrect since it got $0$ at the exam.My solution for the sub-problem is clear enough I think.For knowing what kobayashi's theorem is just search the aops

Ok, Thanks...

What's $\text{ord}_p(n)$?

smallest number $k$ such that $n^k \equiv 1 \bmod p$

Bump

The following solution is built on hints given to me by Faraz Ghahremani from his own solution in the actual contest. Firstly without loss of generality assume $a<b$. Build a sequence of primes $\{p_i\}$ with $p_1$ being arbitrary and large enough and $$p_{i+1} \equiv 1 \mod \phi((a-b)^2)\Pi_{j=1}^{j=i} \phi(a^{p_j}-b) , p_{i+1} >2(b-a)$$the existence of such a sequence is consequent of Dirichlet's theorem (This also has an elementary proof using cyclotomic polynomials and order). Firstly note that if $i>j$, $q^{m} \mid gcd(a^{p_i}-b,a^{p_j}-b)$ then $$q^m \mid a^{p_j}-b \implies p_i \equiv 1 \mod \phi(q^m) \implies 0 \equiv a^{p_i}-b \equiv a-b \mod q^m \implies q^m \mid a-b$$Also it can be seen that the exponent $m$ of a prime dividing $a-b$ in $a^p_i-b$ factorisation is not more than such exponent in $b-a$ so we can take a prime $q$ dividing $a^{p_i}-b$ with $gcd(q,b-a)=1$ and observe that $$Ord_q(b) \mid p_iOrd_q(a), Ord_q(a) \mid Ord_q(b)$$This implies if $Ord_q(b)\neq Ord_q(a)$ then $Ord_q(b)=p_iOrd(a)$ hence $p_i \mid q-1$ so the factorisation of $a^{p_i}-b$ is $$a^{p_i}-b=D_i \Pi (p_ik_i+1)^{\alpha _i}$$where $D_i \mid (a-b)$ taking modulo $p_i$ we have $p_i \mid a-b-D_i$ this implies $a=b+D_i$ a contradiction. So for all $a^{p_i}-b$ there exist at least one prime divisor $q_i$ with $Ord(b)=Ord(a) \mod q_i, q_i \nmid b-a$ we have already proved these primes are distinct hence the conclusion.

For the case $\text{ord}_p(a) \geq \text{ord}_p(b)$. Let $p > 6$ be a prime number, by Zsigmondy Theorem we have $q \in \mathbb{P} $ such that $a^p \equiv b^p \pmod q $ and $a^i \not \equiv b^i \pmod q $ for all positive integer $i \leq p-1 $. Lemma : $q=pk+1$ for some $k \in \mathbb{N}$. Proof : We have $ (ab^{-1} )^p \equiv 1 \pmod q $, we have $ \text{ord}_p(ab^{-1} ) \mid \gcd(p,\varphi(q))=\gcd(p,q-1)= \left\{1,p \right\} $, because $\text{ord}_p(ab^{-1} ) \neq 1 $, we must have $\text{ord}_p(ab^{-1} )=p$ and, $ p \mid q-1 \Leftrightarrow q=pk+1 $. Assume $ p \nmid \text{ord}_p(a),\text{ord}_p(b) $ thus we must have $ \text{ord}_p(a),\text{ord}_p(b) \mid k $, thus, $$a^k \equiv b^k \equiv 1 \pmod q \Leftrightarrow (ab^{-1})^k \equiv 1 \pmod q \Leftrightarrow p \mid k $$Thus we have $k=k_1p $ for some $k_1 \in \mathbb{N} $, thus we must have $\text{ord}_p(a),\text{ord}_p(b) \mid k_1 $, we have $\text{ord}_p(ab^{-1}) \mid k_1 \Leftrightarrow p \mid k_1\Leftrightarrow k_1 =k_2p $, we can keep repeating this process, by infinite descent, we cannot have such $k$. Thus we must have either $ p \mid \text{ord}_p(a)$, or $p \mid \text{ord}_p(b) $. Assume WLOG $\text{ord}_p(a)=xp $ for some $x \in \mathbb{N} $, thus $a^{xp} \equiv b^{xp} \equiv 1 \pmod q $. thus $\text{ord}_p(a) \geq \text{ord}_p(b)$. Because there is infinitely many primes, then there are infinitely primes such that $ \text{ord}_p(a) \geq \text{ord}_p(b) $. For the equality case iff: $p \mid \text{ord}_p(a),\text{ord}_p(b) $, but I can't seem to prove it, any ideas ?

@above How do we know there exists infinitely many prime such that $\text{ord}_p(a)=xp$? It is possible that the primes satisfying $\text{ord}_p(b)=xp $ is infinite but $\text{ord}_p(a)=xp$ is finite.

WLOG $1<a<b$. Assume for contradiction there exist finitely such primes, call this set $S$. Let $U(n)=\prod\limits_{p\in S} p^{\nu_p(n)}$. Let $q$ be a prime greater than all elements of $S$. This means the divisors of $a^q-b$ are either 1 mod $q$ or in $S$; otherwise, $ord_q(b)=ord_q(a)$ because $ord_q(a)\in \{ord_q(b), q ord_q(b)\}$. Note $a-b<0$. Therefore, $a^q-b\equiv U(a^q-b) \equiv q-(b-a) (\bmod\; q)$. Therefore, for all $q$, $U(a^q-b)\ge q-(b-a)$. Now I claim we can select $q$ st $U(a^q-b)$ is bounded, which solves the problem because it is unbounded. Also, for all sufficiently large $q$ there exists $U(a^{q+N}-b)=U(a^q-b)$ if $\varphi(\frac{U(a^q-b)}{\gcd(a^q,b)}) |N$: to see this note the primes dividing both $a$ and $b$ have limited powers. The conclusion follows by picking $r>2U(a^q-b)^2, r\equiv q(\bmod\; N)$, which exists by Dirichlet's theorem. For an elementary solution, if we let $V(n)=\prod\limits_{p\in S, p\nmid a} p^{\nu_p(n)}$, then we must have $V(a^r-b) \ge \frac{r}{C}-1$ for some constant $C$. However, note $V(a-b)=V(a^{1+N}-b)$ if $N$ is divisible by $\varphi(V(a-b)) \cdot \prod\limits_{p\in S} p)$ because $a^{1+N}-b \equiv a-b (\bmod\; V(a-b))\prod\limits_{p\in S} p)$. With cyclotomic polynomials we can prove there are infinitely many primes that are $1$ mod $\varphi(V(a-b)) \cdot \prod\limits_{p\in S} p)$ so we are done.