Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(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!

share|improve this question
    
You can rewrite the equality as $a^b \equiv (-b)^b \equiv (-1)^b \cdot b^b \equiv b^a \mod (a+b)$ or $b^{a - b} \equiv (-1)^b \mod (a+b)$. I'm not sure if that helps. –  TMM Oct 22 '12 at 20:48
    
@TMM To cancel $\rm\:b\:$ as you did requires $\rm\: 1 = (b,a+b) = (b,a).\ \ $ –  Bill Dubuque Oct 22 '12 at 21:59
    
@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$). –  TMM Oct 22 '12 at 22:29

2 Answers 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..

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.