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

  • $\begingroup$ It's cleaner to assume $\ a\ge 2.\ $ Even case $\ a=2\ $ is classic YES (quadratic reciprocity) hence one may assume $\ a\ge 3.$ $\endgroup$ – 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.

  • $\begingroup$ Far far easier than what I was thinking! $\endgroup$ – 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?


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.