8
$\begingroup$

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!

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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