Infinitely many primes that solves a congruence

Question

Let $a\ge1$ and $b\ge2$. Prove that there are infinitely many primes $m$ such that $$x^a\equiv b(\mathrm{mod}\,m)...(1)$$ has solution.

Do you have some hints?

I thought on using Chinese Remainder Theorem, but it implies something more: if $m_1,...,m_r$ are such primes then there is a UNIQUE $x$ that solves (1) for $m=m_i$. But in my problem there is no a unique $x$.

Answer 1

Translate this back to the language of divisibility. You're asking to find primes $m$, arbitrarily large, such that

$$m \mid x^a - b.$$

But you can choose any $x$ you want! So now ask yourself: can the numbers of the form $x^a - b$ ($a$ and $b$ fixed) just keep magically happen to always be divisible by the same finite set of primes?

Let's think about this from a different direction too. What if I gave you a finite set of primes? Let's say 2, 3, and 5 for concreteness. What kinds of numbers can you make?

In fact, let's play a game with this set of primes. Every time I give you an $x$, you have to give me back a new number made only with the prime factors 2, 3, and 5, and it has to be larger than any number you've given me before.

Key question: regardless of how you answer, how fast does the sequence you give me grow?

Answer 2

Given such $b$ and $a$, choose some $x$ and let $m$ be a prime that divides $x^a-b$. If you already have $m_1, \ldots, m_n$, you can ensure that $x^a-b$ is not divisible by any of these be taking $x \equiv 1 \mod m_j$ if $m_j$ divides $b$ and $x \equiv 0 \mod m_j$ if not.