The prime numbers $p$ and $q$ and the integer $a$ are chosen such that $p> 2$ and $a \not\equiv 1$ (mod $q$), but $a^p \equiv 1$ (mod $q$). Prove that $(1 + a^1)(1 + a^2)...(1 + a^{p - 1})\equiv 1$ (mod $q$) .
Problem
Source: 2020 Estonia TST 4.3
Tags: number theory, remainder
19.11.2020 00:26
It's $\equiv$ to...
19.11.2020 01:55
Because $a^k$ with $0<k<p$ also satisfies $(a^k)^p\equiv 1\pmod{q}$ it follows that these are the roots of the polynomial $P(x)=\frac{x^p-1}{x-1}=1+x+...+x^{p-1}$ (we have to exclude the root $1$). Therefore $(1+a^1)\cdots(1+a^{p-1})\equiv (-1)^{p-1}P(-1)=1+(-1)+...+(-1)^{p-1}=1$ (because $p$ is odd)
13.11.2021 07:04
cadaeibf wrote: Because $a^k$ with $0<k<p$ also satisfies $(a^k)^p\equiv 1\pmod{q}$ it follows that these are the roots of the polynomial $P(x)=\frac{x^p-1}{x-1}=1+x+...+x^{p-1}$ (we have to exclude the root $1$). Therefore $(1+a^1)\cdots(1+a^{p-1})\equiv (-1)^{p-1}P(-1)=1+(-1)+...+(-1)^{p-1}=1$ (because $p$ is odd) More specifically, one has $P(a^k)=\frac{(a^k)^p-1}{a^k-1} \equiv 0 \pmod p$. Therefore, $P(x) \vdots x-a^k$ for all $0<k<p$. It follows that $P(x)=(x-a^1)(x-a^2)....(x-a^{p-1})$. Plugging $x=-1$ finishes the proof.