3
$\begingroup$

(When I use an $=$, I am referring to a congruence relation.)

I am curious is anybody can point me in the right direction for solving the following congruence relation ($a$,$b$ of course both integers)

$a^b=b^a \mod (a+b)$

I have tried rewriting this in a few forms, such as let $b=a+n$ and finding more likely scenarios for this to occur. However, I dont even know really how to approach writing a solution!

If anybody can just point me in the right direction, if I'm looking for abstract algebra terms, or some other form of math all together, that's all I really need!

Although, if you do have a solution, I would love to see that as well!

  • 0
    @Bill Yes you are right. So you can only do that if $(a,b) = 1$. But even then, it's not clear how to continue (or what to do if (a,b) = d > 1).2012-10-22

2 Answers 2

2

Let's suppose $ab \neq 0$ and define $d:=\text{gcd}(a,b)$, so that $a=dA, b=dB$, then $a^b \equiv b^a \pmod{a+b}$ if and only if $d^{d(B-A)}A^{dB}\equiv B^{dA}\pmod{A+B}$; by contruction $\text{gcd}(A,B)=1$, so that the above relation is true if and only if $(A^{-B}B^A)^d \equiv d^{d(B-A)} \pmod{A+B}$.

The general case now seems a bit untractable; for now, let's see a particular case: $d=1$ and $A+B$ is a power of a prime $p\ge 3$, let's say $p^k$, with $k\ge 1$.

We have to solve $A^{-B}B^A \equiv 1 \pmod{p^k}$ with $A+B=p^k$; if $p\mid A$ then $p\mid p^k-A=B$, against the assumption $\text{gcd}(A,B)=1$. It means that, if a solution exists, then $p\nmid AB$. Define $g$ a generator in $\mathbb{Z}/p^k\mathbb{Z}$, and $\alpha$ the unique integer in $[1,\varphi(p^k)]$ such that $A \equiv g^{\alpha} \pmod{p^k}$. Then we have to verify $g^{-\alpha(p^k-g^{\alpha})}(p^k-g^{\alpha})^{g^{\alpha}}\equiv 1\pmod{p^k}$.

Case1: $2\nmid A=g^{\alpha}$. It's necessary and sufficient to verify that $-\alpha(p^k-g^{\alpha})-\alpha g^{\alpha} \equiv 0 \pmod{\varphi(p^k)}$, that is equivalent to $p-1 \mid \alpha$.

Case2: $2\mid A=g^{\alpha}$. It's necessary and sufficient to verify that $-\alpha(p^k-g^{\alpha})+\alpha g^{\alpha} \equiv 0 \pmod{\varphi(p^k)}$ that is equivalent to $2\alpha g^{\alpha}\equiv \alpha p^{k-1}\pmod{\varphi(p^k)}$. If $k\ge 2$ then $p\mid p^{k-1}\mid \varphi(p^k)$ and $p\mid \alpha p^{k-1}$, then $p\mid 2\alpha g^{\alpha}$, but $p\ge 3$ and $g^{\alpha}=A$ is coprime with $B$, i.e. $p\nmid AB$, so we must have $p^{k-1}\mid \alpha$. There exists $\gamma \in \{1,2,\ldots,p-1\}$ such that $\alpha=p^{k-1}\gamma$ and the above relation is equivalent to $2\gamma g^{p^{k-1}\gamma} \equiv \gamma \pmod{p-1}$. Clearly $\gamma$ must be even, since it particular such relation holds mod $2$, so it's equivalent to $\gamma g^{p^{k-1}\gamma} \equiv \frac{1}{2}\gamma \pmod{\frac{1}{2}(p-1)}$. Now, even supposing $\text{gcd}(p-1,\gamma)=1$ we can't do much more, since the solution structure will depend from the value of $k$, $p$ and the factorization of $\frac{1}{2}(p-1)$.

That's all I did, for now..

2

Not a solution, but perhaps a reduction to a somewhat simpler looking equation:

Suppose $\gcd(a,\phi(a+b))=1$. Choose $c$ so $b\equiv ac\pmod{\phi(a+b)}$. Then $a^{ac}\equiv (ac)^a\pmod{a+b}$ so $a^c\equiv ac\pmod{a+b}$ Assuming further $\gcd(a,b)=1$, we have $a^{c-1}\equiv c\pmod{a+b}$