I have seen this question here, however, what interested me the most is the partial answer which uses $Fermat's \ little \ theorem$, but as you can see there, he didn't continue proving that the power is the least to satisfy the property. Therefore, I will be glad for an elementary answer, and a full answer for this question that uses $Fermat's \ little \ theorem$. Thanks a lot!
- By the way, I hope that I didn't do something wrong by posting this post. I am not that familiar with the rules here.
Best Answer
Note: Everything throughout this solution is with use of Fermat Little Theorem and Order. The rest is basic knowledge. 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.