Lattices possess elegant mathematical properties which have been previously used in the literature to show that structured codes can be efficient in a variety of communication scenarios. We consider the family of single-transmitter multiple-receiver Gaussian channels where the source transmits a set of common messages to all the receivers (multicast scenario), and each receiver has coded side information, i.e., prior information in the form of linear combinations of the messages. This channel model is motivated by applications to multi-terminal networks where the nodes may have access to coded versions of the messages from previous signal hops or through orthogonal channels. The capacity of this channel is known and follows from the work of Tuncel (2006), which is based on random coding arguments. In this paper, following the approach introduced by Erez and Zamir, we show that lattice codes are capacity-optimal for this family of channels. The structured coding scheme proposed in this paper is derived from Construction A lattices designed over prime fields, and utilizes algebraic binning at the decoders to expurgate the channel code and obtain good lattice subcodes, for every possible set of linear combinations available as side information. © 2017 IEEE.