13
$\begingroup$

Let $n$ and $a$ be positive integers with $a > 1$. I need to show that $n$ divides $\phi(a^n -1)$.

Here, $\phi$ denotes the Euler totient function.

Could any one give me a hint?

$\endgroup$
2

6 Answers 6

18
$\begingroup$

A group theoretic solution can be given, (though this solution requires some advanced concepts yet it is very elegant and beautiful).

Let $m= a^n-1$.

Consider the group $G = (\mathbb{Z} / m\mathbb{Z})^*$ or rather $(\mathbb{Z}_m)^*$.

This group has $\phi(m)$ elements or rather the order of the group is $\phi(m)$.

Let $\bar a \in \mathbb{Z} / m \mathbb{Z}$ be the remainder class of the integer $a$ modulo $m$. Then, $\bar a \in G$, as $\gcd(a,m) = \gcd(a,a^n-1)=1$.

Consider the subgroup $H=\left<\bar a\right>$ that is the subgroup generated by $\bar a$.

Now $a^n\equiv 1 \mod m$ (where $m=a^n-1$ and $n$ is the smallest integer with this property), but no positive integer $i<n$ satisfies $a^i \equiv 1 \mod m$ (since $a^i - 1$ is a positive integer smaller than $m$). This implies that order of $H$ equals $n$.

Now as the order of a subgroup always divides the order of a group we have $n\mid\phi(a^n-1)$ .

$\endgroup$
0
9
$\begingroup$

Hint:

$$a^n\equiv 1\pmod {a^n-1}$$ and $$a^d\not\equiv 1\pmod {a^n-1}$$ if $0<d<n$ (why?).

$\endgroup$
8
$\begingroup$

Hint for proving that $n \mid \phi(a^n - 1)$ for all integers $n > 0$ and $a > 1$:

  1. Find the smallest positive integer $i$ with the property that $$ a^i\equiv1\pmod{a^n-1}.$$
  2. Now you know the order of the coset $\overline{a}$ in the group $G=\mathbb{Z}_{a^n-1}^*$. Apply Lagrange's theorem.
$\endgroup$
1
  • $\begingroup$ Dear Jyrki! Nice and simple group-theoretic proof! +1 $\endgroup$
    – RFZ
    Jan 7, 2018 at 16:29
8
$\begingroup$

You can apply Euler's Theorem like this: $${a}^{\phi\left(m^n-1\right)}\equiv 1 \pmod{m^n-1}$$ Also, you can use this fact: $$\left(x^a-1,x^b-1\right)=x^{\left(a,b\right)}-1$$

$\endgroup$
2
  • $\begingroup$ Hello Issac Yiu! Welcome to MSE! $\endgroup$ Aug 11, 2019 at 5:34
  • $\begingroup$ ...lol,hahahaha $\endgroup$
    – MafPrivate
    Aug 11, 2019 at 6:00
2
$\begingroup$

$a$ has multiplicative order $n$ in the ring of integers modulo $a^n - 1$, but this order must divide the order of the group of units modulo $a^n - 1$.

$\endgroup$
0
2
$\begingroup$

Claim 1: $\text{ord}_{a^{n}-1}(a) = n$

Proof:

Let $x = \text{ord}_{a^{n}-1}(a)$. Then $a^x-1 \equiv 0 \pmod {a^{n}-1}$. If $0 < x < n$, then $a^{x} < a^n$ so we are done.

Claim 2: $n| \phi(a^{n}-1)$.

Proof:

We know that $a^{ \phi(a^{n}-1)} \equiv 1 \pmod { a^{n}-1}$ since $\gcd(a, a^{n}-1) = 1$. Now since the order of $a$ is $n$, it immediately follows that $n| \phi(a^{n}-1)$.

$\endgroup$

You must log in to answer this question.

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