Physical Sciences and Mathematics Commons^™

Enumeration Problems For A Linear Congruence Equation, Tian-Xiao He, Wun-Seng Chou, Peter Shiue

Tian-Xiao He

Let m ≥ 2 and r ≥ 1 be integers and let c Є Zm = {0, 1, …,m ─ 1}. In this paper, we give an upper bound and a lower bound for the number of unordered solutions x1, …, xn Є Zm of the congruence x1 + x2 + ••• + xr ≡ c mod m. Exact formulae are also given when m or r is prime. This solution number involves the Catalan number or generalized Catalan number in some special cases. Moreover, the enumeration problem has interrelationship with the restricted integer partition.