Assume $a$ has order $k$ modulo $n$, and $k $ | $φ(n)$. Prove that $k $ | $φ(a^k - 1)$

73 Views Asked by At

Let $n ≥ 1$ and let $a$ be an integer such that $gcd(a, n) = 1$.
Assume $k ≥ 1$ and $a ≥ 2$
$φ$ is Euler's phi function

This is my solution:

I know that $a^k \equiv 1$ (mod $n$)

From this information I can conclude that
$n$ | $a^k - 1$

I can then write
$a^k - 1$ as $nt$ for some integer $t$.

I know that $φ$ is a multiplicative function, so I write
$φ(a^k - 1) = φ(nt) = φ(n)φ(t)$

It is given that $k$ | $φ(n)$ so I know that $k$ | $φ(n)φ(t)$

It then follows that $k$ | $φ(a^k - 1)$

Is this a valid proof?

1

There are 1 best solutions below

0
On

As Casteels points out in the comments, you can't conclude $\phi(n \cdot t) = \phi(n) \cdot \phi(t)$ because $\phi$ is not completely multiplicative, but you can still prove that $\phi(n) \space\vert\space \phi(n \cdot t)$ using the formula $\phi(\prod p_{i}^{e_i}) = \prod [p_i^{e_i-1} \cdot (p_i-1)]$.