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
    0 references
    0 references

    Identifiers