The prime numbers p and q and the integer a are chosen such that p>2 and a≢ (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.