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.

In this post, I asked how to prove $n\mid \phi(2^n-1),(n\in \mathbb N)$. @Amr and @Abhra Abir Kundu proved more: they proved that $n\mid \phi(a^n-1),(a,n\in \mathbb N).$ The method is very nice. I quote Amr's answer in the following:

Consider $U(2^n-1)$. Clearly $2\in U(2^n-1)$. It can also be shown easily that the order of $2$ in the group $U(2^n-1)$ is $n$. By Lagrange's theorem $|2|=n$ divides $|U(2^n-1)|=\phi(2^n-1)$.

Now I want to prove a similar problem:

If $a,b,n\in \mathbb N,a>b,$ then $n\mid \phi(a^n-b^n).$

Inspired by their answers, I try to do something:

First, we assume that $GCD(a,b)=1.$ Let $ak\equiv b\pmod {a^n-b^n},k\in\mathbb N.$ Then $a^nk^n\equiv b^n\equiv a^n\pmod {a^n-b^n},a^n(k^n-1)\equiv 0\pmod {a^n-b^n},k^n\equiv 1 \pmod {a^n-b^n}.$

Consider $U(a^n-b^n)$. Clearly $k\in U(a^n-b^n)$. If we can show that the order of $k$ in the group $U(a^n-b^n)$ is $n$. By Lagrange's theorem $|k|=n$ divides $|U(a^n-b^n|=\phi(a^n-b^n)$.

Howerver, I can only prove that $k^n\equiv 1 \pmod {a^n-b^n},$ it doesn't $\implies|k|=n.$

Any help would be grateful!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Continuing where you stopped: We can assume without loss of generality that $a \perp b$. [If $a =d a_1,\ b = d b_1$ then $\phi(a^n - b^n) = \phi(d^n(a_1^n - b_1^n))$ is divisible by $ \phi(a_1^n - b_1^n)$.] We know that $k = a/b$ has the property that $k^n \equiv 1$, and if we can show that $k^m \not \equiv 1$ for $m < n$ then we are done.

So, suppose that $k^m \equiv 1$, $0 < m < n$. Then: $$a^m \equiv k^m b^m \equiv b^m$$ In other words, $a^n-b^n | a^m - b^m$. But, if $n > m$, then $a^n - b^n > a^m - b^m$, as can be checked with basic analysis. [Take $f(x) = a^n - b^n$ with $a < b$; then $f'(x) = (\ln a) a^x - (\ln b)b^x > 0$.] Thus, we reach a contradiction, since the bigger number cannot divide the smaller one. This finishes the proof.

Hence, essentially the same trick works as mentioned previously.

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.