# How do you embed $Z_5 \times Z_7$ into $Z_{2^8}$?

Basically, the real question which I thought was better asked that way is what are the ways to represent all ordered pairs of elements $(x,y)$ where $x\in Z_5$ and $y\in Z_7$ in a byte of memory? I.e. There needs to be atleast 5*7 = 35 code words. I'm working on a way right now, but if someone's already shown all the ways, please post a link. Ways that are useful arithmetically are better. I.e. if adding two bytes has some meaningful result on their embeded pairs.

-
I'm fairly certain unsigned bytes usually act like elements of $Z_{2^8}$. – Enjoys Math Mar 24 '12 at 0:31

Embed first $Z_5$ into $Z_8$ and $Z_7$ into $Z_8$. Then simply embed $Z_8 \times Z_8$ into $Z_{2^6} \hookrightarrow Z_{2^8}$

If you are looking for all ways, keep in mind that $Z_5 \times Z_7$ is "the same" as $Z_{35}$. Chinese Reminder Theorem gives you a way to identify them as groups, and then you forget the group structure...So your problem asks you how to embed $Z_{35}$ into $Z_{2^8}$...

-
I think that's what I need, $Z_{35}$. What's the mapping look like between the two groups? I really need to learn algebra :D – Enjoys Math Mar 24 '12 at 0:41
@Dan: It's not a map of groups. – Hurkyl Mar 24 '12 at 1:22
@Dan: the generator of $Z_{35}$ corresponds to the element $(1,1)$ of $Z_5\times Z_7$. It is both an additive and a multiplicative homomorphism. – Arturo Magidin Mar 24 '12 at 2:38
@DanDonnelly: For $\mathbb Z_5 \times \mathbb Z_7 \to \mathbb Z_{35}$, just view the elements of $\mathbb Z_{35}$ as pairs $(a,b), a \in \mathbb Z_5, b \in \mathbb Z_7$ You will need the CRT to make the correspondence $28 \leftrightarrow (3,0)$ – Ross Millikan Mar 24 '12 at 2:47
Since you don't care about the group structure, if you identify $Z_n$ as $0,1,2,..., n-1$, then the map $(a,b) \to 7a+b$ is a bijection from $Z_5 \times Z_7 to Z_{35}$. – N. S. Mar 24 '12 at 4:21

Probably the most straightforward way to do this would be to use the first 4 bits to keep track of the elements of $\mathbb{Z}_5$ and the next 4 bits to keep track of $\mathbb{Z}_7$. So $(3,5) \mapsto 0011\;0101_2$ etc.

Just so you know. In terms of arithmetic, $\mathbb{Z}_5 \times \mathbb{Z}_7$ cannot be embedded in $\mathbb{Z}_{2^8}$ (as groups under addition). Lagrange's theorem tells us that the order of a subgroup must divide the order of the group and $35$ doesn't divide evenly into $2^8$. In fact the only group homomorphism from $\mathbb{Z}_5 \times \mathbb{Z}_7$ to $\mathbb{Z}_{2^8}$ is the trivial one which sends everything to zero.

-