Inductive proof for Bauer's theorem

199 Views Asked by At

Pre requisite

Hardy and Wright first prove the following theorem

$$\prod_{t \; \in \;t(p)} (x-t)=x^{p-1}-1 \pmod p, \tag 1$$

where $p$ is a prime number. $t(p)$ represents the set of numbers less than $p$ and co-prime to $p$. $t$ represents a number from the set $t(p)$.

Bauers Theorem

The authors later state the following Bauer's theorem

$$\prod_{t \; \in \;t(p^a)} (x-t)=(x^{p-1}-1)^{p^{a-1}} \pmod{p^a}, \tag 2$$ where $p$ again is a prime number.

Let $f_{p^a}(x)=\prod_{t \; \in \;t(p^a)}(x-t)$, then the authors give the proof for $(2)$ using induction. It can be seen that for $a=1$ $(2)$ reduces to $(1)$ and thus we get the base case. But for the inductive step the authors prove the following

$$f_{p^a}(x)=(f_{p^{a-1}}(x))^p \pmod{p^a} \tag 3$$

and say that $(3)$ along with base case completes the inductive proof for $(2)$. But how ? How can $(3)$ be used to prove $(2)$ ?

1

There are 1 best solutions below

1
On BEST ANSWER

By the induction hypothesis, we have

$$f_{p^{a-1}}(x) \equiv (x^{p-1} - 1)^{p^{a-2}} \pmod{p^{a-1}}.$$

That means

$$f_{p^{a-1}}(x) = (x^{p-1} - 1)^{p^{a-2}} + p^{a-1}\cdot q(x)$$

for some polynomial $q$. But then by binomial expansion

$$\bigl(f_{p^{a-1}}(x)\bigr)^p = \bigl((x^{p-1} - 1 )^{p^{a-2}}\bigr)^p + p^a\cdot q(x) \bigl((x^{p-1} - 1)^{p^{a-2}}\bigr)^{p-1} + \sum_{k = 2}^p \binom{p}{k} p^{k(a-1)}q(x)^k \bigl((x^{p-1} - 1)^{p^{a-2}}\bigr)^{p-k},$$

and we have $k(a-1) = a + (k-1)(a-1) - 1 \geqslant a$ for $k \geqslant 2$ (using $a \geqslant 2$), and thus what remains is

$$\bigl(f_{p^{a-1}}(x)\bigr)^p \equiv \bigl((x^{p-1} - 1)^{p^{a-2}}\bigr)^p = (x^{p-1} - 1)^{p^{a-1}} \pmod{p^a}.$$