Sums of subsequences modulo prime powers
type: Item
instance of: scholarly article
title: Sums of subsequences modulo prime powers
zbMATH Open document ID: 0646.10003
DOI: 10.1016/0012-365X(88)90032-5
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11A07
Mathematics Subject Classification ID: 11B75
zbMATH DE Number: 4053709
zbMATH Keywords: congruences
zbMATH Keywords: addition of residue classes
author: Noga Alon
reviewed by: Noga Alon
MaRDI profile type: Publication
cites work: Two theorems on the addition of residue classes
full work available at URL: 0012-365x(88)90032-5
OpenAlex ID: W2034420538
description: scientific article; zbMATH DE number 4053709