Vom Block zur Präfixdifferenz

Für $i<j$ gilt $S_j-S_i=a_{i+1}+\cdots+a_j$. Gleiche Präfixreste liefern deshalb einen teilbaren Block.

Entweder ist eine Präfixsumme selbst durch $n$ teilbar, oder alle $n$ Präfixsummen liegen in nur $n-1$ Nichtnullrestklassen.