An alternative factorization

Note that $p = 101$ is a prime. Hence, $\mathbb{Z}_p$ is a field.

Also, note that Fermat's theorem shows that $1,2,\dots,100$ are all roots of the following equation in $\mathbb{Z}_p$ : $x^{100} = 1$

As the degree of the polynomial is $100$ , the above roots are the only roots.

As we're in a field, we conclude that the following holds in the field : $x^{100} - 1 = \prod_{i = 1}^{100} (x - i) = \prod_{i = 1}^{100} (x+i)$

Also, this is the unique factorization (up to a permutation of the factors).

Hence, $a_i \equiv i \pmod p \quad \forall i, (*)\\\implies \sum_{i = 1}^{100} a_i \geq 5050 \\\text{Equality holds when } a_i = i$

---

Note: The equation $(*)$ should be the following to be more accurate : $\{(a_i \text{ mod } p) : i \in \mathbb{N} ;\, i \leq 100\} = \mathbb{Z}_p - \{0\}$

Surprisingly, we can say that ${a}_{i}=i$ . That is,

$\displaystyle { x }^{ 100 }-1\equiv \prod _{ i> 0 }^{ 100 }{ (x+i) } \pmod{101}$

Observe that $x=0$ gives $-1$ in modulo $101$ . One can use Fermat's Little Theorem, that ${x}^{p-1}\equiv1 \pmod{p}$ to show that for $x\neq0$ we get $0$ mod 101. This is essentially because if we take a nonzero $x$ then

$\{x,2x,...(p-1)x \}=\{1,2,3...(p-1) \}$

Taking the product of all elements in both sets and dividing by $(p-1)!$ gives ${x}^{p-1}\equiv1\pmod{p}$ . So, we want a root for all $0<x<101$ mod 101 which can clearly be done by setting ${a}_{i}=i$ , due to each $x$ having a unique additive inverse mod 101. Using Wilson's theorem, $(p-1)!\equiv -1 \pmod{p}$ so $x=0$ also works. Sum all the ${a}_{i}$ :

$\sum _{ i>0 }^{ 100 }{ { a }_{ i } } =\frac { (100)(101) }{ 2 } =5050$

We cannot add to this factorization without increasing the sum of ${a}_{i}$ : if the sum does not increase, any factors we add must be $x$ which invalidates the factorization at $x=0$ . If we have $(x+k)$ then, well, you've just added $k$ to your minimum and it isn't very minimal anymore. :)