# Infinitely many primes that solves a congruence

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

• It's cleaner to assume $\ a\ge 2.\$ Even case $\ a=2\$ is classic YES (quadratic reciprocity) hence one may assume $\ a\ge 3.$ – Wlod AA Sep 2 at 2:06

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.

• Far far easier than what I was thinking! – RghtHndSd Sep 2 at 2:17

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?