1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ $\left(1+\frac{b}{x}\right)^n \equiv 1$ $\endgroup$
    – wlad
    May 22, 2015 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$ May 22, 2015 at 20:06

1 Answer 1

2
$\begingroup$

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.

[edit]

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .