8
$\begingroup$

Suppose that $n$ is a natural number and $b$ is one coprime to it such that $b^n\equiv 1\pmod n$. Does it follow that, if $b^x-x\equiv b^y-y\pmod n$, then $x\equiv y\pmod n$?

This is inspired by the comments on a previous answer I wrote, which got me thinking about fixed points on exponentiation. Toying around in Mathematica, I noticed that $$x\mapsto 9^x-x\pmod{1000}$$ is an injective function. In fact, I noticed that if we replace $9$ by any other number coprime to $1000$, this still holds. Toying around further, I noticed that the list of numbers $n$ other than $1000$ such that all coprime bases $b$ had this property starts the same way as this sequence in OEIS, which is exactly the sequence of $n$ such that $b^n\equiv 1\pmod n$ for $b$ coprime to $n$. I can't prove the lists are equal (but they seem to be), but I can see that $b^n\equiv 1\pmod n$ is a necessary condition for $x\mapsto b^x-x$ to be injective (as it's not even well-defined otherwise).

The only insight I have into the problem is that it clearly holds if $b=1$ or $-1$. The latter can be argued as if $(-1)^n\equiv 1\pmod n$ then $n$ is even and $x\mapsto (-1)^x-x$ maps evens to odds and vice versa and is a linear function with unit ($-1$) coefficient of $x$ over those domains - and hence is bijective. I feel like there may be some generalization of this approach by partitioning $(\mathbb Z/n\mathbb Z,+)$ into $\text{ord}_n(b)$ cosets (where $\text{ord}$ is the multiplicative order of $b$ mod $n$), but I have been unsuccessful in finding it if it exists. To be sure, restricting the map in question to a single such coset yields a bijection between it and another coset (as $b^{x}-x$ and $b^{x+\text{ord}_n(b)}-x-\text{ord}_n(b)$ are equal mod $\text{ord}_n(b)$) - but I can't prove that two distinct cosets do not map to the same place, as this requires considering the map over the larger domain where it is less well-behaved.

I am primarily interested in the answer to this question, regardless of technique, however I would be especially interested in knowing if the methods I sketched can be gainfully extended to a proof.

$\endgroup$
2
$\begingroup$

We can realize the proof sketch in the question as a proof by induction on $n$. The statement holds trivially for $n=1$. Next, choose any $b$ and $n$ such that $b^n\equiv 1\pmod n$. If we let $k$ be the multiplicative order of $b$ mod $n$, we can clearly see that $k$ divides $n$, as $b^x\equiv 1$ only for multiples of $k$, and further that $k<n$, as $k$ is the order of the multiplicative subgroup group generated by $b$, and this must divide the order of the multiplicative group mod $n$, which is less than $n$.

Now suppose that $$b^x-x\equiv b^y-y\pmod n.\tag{1}$$ Notice that this implies the weaker statement that $b^x-x\equiv b^y-y \pmod k$. However, since $b^k\equiv 1\pmod k$ and $k<n$, we can apply the inductive hypothesis and conclude that $x\equiv y\pmod k$. However, this implies $b^x\equiv b^y\pmod n$. Subtracting equation (1) from this yields $x\equiv y\pmod n$, as desired.

| cite | improve this answer | |
$\endgroup$

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.