How to completely factor $x^{\varphi(a)} - 1$ when $\gcd(a,x)=1$?

82 Views Asked by At

In what follows, let $\varphi(a)$ be the Euler's totient function of $a \in \mathbb{N}$.

Euler's Theorem (of which Fermat's Little Theorem is a special case) states that

For any modulus $a$, and any integer $x$ coprime to $a$, one has $$x^{\varphi(a)} \equiv 1 \pmod a.$$

In particular, when $\gcd(a,x)=1$, we have $$x^{\varphi(a)} - 1 = ab.$$

Edited

Here is my question in this post:

Is there a closed form (and perhaps, completely factored expression) for $b$ in terms of $x$ and $a$?

MY OWN THOUGHTS ON THE PROBLEM

I was thinking that, maybe, something similar to the factorization $$x^m - 1 = (x - 1)(x^{m-1} + x^{m-2} + \ldots + x + 1)$$ holds for $$x^{\varphi(a)} - 1 = ab,$$ but I also know that my hunch may be wrong.

1

There are 1 best solutions below

8
On

Your suggested factorization holds.

Furthermore, remember that the expression is zero for any $x$ that is co-prime with $a$.
Therefore for any $k$ that is co-prime with $a$, we have that $(x-k)$ is a factor of $(x^{\varphi(a)}-1)$.

More specifically, if $a$ is a prime, then: $$x^{\varphi(a)}-1 \equiv x^{a-1}-1 \equiv \prod_{\gcd(k,a)=1} (x-k) \pmod a$$