Two polynomials congruence modulo $p$

121 Views Asked by At

This is a result that I found in a compettion. But I didn't known it is false or true.

Let $n$ be a positive integer and $p$ be a prime divisor of $n$. Prove that if $$x^{\varphi(n)}-1\equiv (x^{p-1} - 1)^{\frac{\varphi(n)}{p-1}}\pmod{p}$$ for all $x\in\mathbb{Z}$, then $\dfrac{\varphi(n)}{p-1}$ is a power of $p$.

Note: $\varphi(n)$ is the number of integers between 1 and $n$ that are relatively prime to $n$.

1

There are 1 best solutions below

1
On

For $p=2$ the assertion is false, for if $n=14$, then $\varphi(n)=\varphi(n)/(p−1)=6$ is not a power of $p=2$ but $x^{\varphi(n)}−1\equiv x−1\equiv (x^{p−1}−1)^{\varphi(n)/(p−1)}\pmod p$ for all $x\in\Bbb Z$.

Assuming $p>2$, let $n=p^em$, $e>0$ and $p\nmid m$ so that $\varphi(n)=p^{e-1}(p-1)\varphi(m)$.

If $x\equiv 0\pmod p$, then the assumption $$x^{\varphi(n)}-1\equiv(x^{p-1}-1)^{\varphi(n)/(p-1)}\pmod p$$ gives $$-1\equiv(-1)^{\varphi(n)/(p-1)}\pmod p$$ from which follows $2\nmid\varphi(m)$.

If $q>2$ is a prime divisor of $m$, then $2\mid(q-1)\mid\varphi(m)$, a contradiction which proves $m=2^r$ for some $r\geq 0$. If $r>0$, then $\varphi(m)=2^{r-1}$ and this proves $r\leq 1$, that's $\varphi(m)=1$. Then $\varphi(n)/(p-1)=p^{e-1}$ thus proving our assertion.