When thinking about solving the diophantine $x^n-y^n=1001$ I noticed that my knowledge about the prime factorisation of $x^n-y^n$ does not suffice to attack such diophantines in general. Note I'm talking about

More specifically I got interested in the solvability of the congruence $$(x+b)^n\equiv x^n\pmod p \tag1\label1$$ in $x$, when $b,n,p$ are fixed. (Let's assume $p$ is prime; I guess most results will generalise to composite moduli using CRT and/or Hensel's Lemma.)

  • What are some theorems regarding solutions of \eqref{1}?
  • Is it true that if \eqref{1} is solvable for $b_1$ and $b_2$, then it is solvable for $b_1b_2$?
    (This question is motivated by the problem I started with, because there $b$ would be a divisor of a given number.) If not, under what non-trivial circumstances does it hold?

There exactly $\frac{p-1}{\gcd(n,p-1)}$ non-zero $n$th power residues modulo $p$, so intuitively solvability of \eqref{1} gets more likely as $\gcd(n,p-1)$ gets larger.

  • 1
    $\begingroup$ $\left(1+\frac{b}{x}\right)^n \equiv 1$ $\endgroup$ – ogogmad May 22 '15 at 20:02
  • $\begingroup$ @user3491648 Ah yes; seems a very silly question now. So \eqref{1} is solvable iff $\gcd(n,p-1)>1$ (assuming $b\not\equiv0$). $\endgroup$ – Bart Michels May 22 '15 at 20:06

We are working in $\mathbb Z / p\mathbb Z$.

$$(x + b)^n = x^n \iff \left(1 + \frac{b}{x}\right)^n = 1 \iff u^n = 1$$ for $u = 1 + \frac{b}{x}$.

Writing $u = g^k$ for the generator $g$ produces $$kn \equiv 0 \pmod{p - 1}$$

and so on.


We get that $p - 1 \mid kn$, so $k$ is any multiple of $\frac{\operatorname{lcm}(n, p-1)}{n}$.

This determines $u$ and then $x$.


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.