Sums of subsequences modulo prime powers (Q1103663)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sums of subsequences modulo prime powers |
scientific article |
Statements
Sums of subsequences modulo prime powers (English)
0 references
1988
0 references
Let \(S=(a_1,a_2,\ldots,a_m)\) be a sequence of residues modulo \(n\). For \(0\le j<n\) let \(E_n(S;j)\) denote the number of subsequences of \(S\) consisting of an even number of members whose sum is congruent to \(j\) modulo \(n\). Similarly, let \(O_n(S;j)\) denote the number of subsequences of \(S\) consisting of an odd number of members whose sum is congruent to \(j\) modulo \(n\). Suppose \(n=p^k\) is a prime power. For each \(1\le i\le m\) let \(b_i\) be the maximum power of \(p\) that divides \(a_i\). It is shown that \[ E_n(S;j)\equiv O_n(S;j)\pmod p\quad \text{ for every } 0\le j<n \tag{\(\ast\)} \] if and only if \(\sum^m_{i=1} b_i\ge n\). In particular, if \(m\ge n\), then (\(\ast\)) holds. This extends a recent result of \textit{D. R. Guichard} [Two theorems on the addition of residue classes. Discrete Math. 81, No. 1, 11--18 (1990; Zbl 0702.11007)] who proved, in a different way, the case \(p=2\) of the last statement.
0 references
congruences
0 references
addition of residue classes
0 references