Quadratic residues

Cairo · #1 $Old$ July 4th, 2009, 10:05 AM

The set {1,2,...16} is to be split into two disjoint non-empty sets S and T in such a way that;

the product (mod 17) of any two elements of S lies in S;
the product (mod 17) of any two elements of T lies in S;
the product (mod 17) of any elements of S and any element of T lies in T.

Prove that the ONLY solution is

S={1,2,4,8,9,13,15,16} and T={3,5,6,7,10,11,12,14}.

I'd also like to know if there is a way to generalise this?

NonCommAlg · #2 $Old$ July 4th, 2009, 04:19 PM

Quote:

Originally Posted by Cairo $View Post$

The set {1,2,...16} is to be split into two disjoint non-empty sets S and T in such a way that;

the product (mod 17) of any two elements of S lies in S;
the product (mod 17) of any two elements of T lies in S;
the product (mod 17) of any elements of S and any element of T lies in T.

Prove that the ONLY solution is

S={1,2,4,8,9,13,15,16} and T={3,5,6,7,10,11,12,14}.

I'd also like to know if there is a way to generalise this?

Generalization:

let $F$ be a finite field of odd order and $F^{\times}=F-\{0\}.$ we know that $F^{\times}$ is a cyclic group. there exist unique non-empty sets $S,T \subset \mathbb{F}^{\times}$ which satisfy the following conditions:

1) $S \cap T = \emptyset$ and $S \cup T=F^{\times},$

2) $a,b \in S \Longrightarrow ab \in S,$

3) $a,b \in T \Longrightarrow ab \in S,$

4) $a \in S, \ b\in T \Longrightarrow ab \in T.$

Proof: first note that 1) & 3) implies that $1 \in S$ and thus by 4) we have $a^{-1} \in S,$ for all $a \in S.$ thus by 2), $S$ is a subgroup of $F^{\times}.$ now fix $a \in S, \ b \in T.$ see that $aS=S$ and $bS=T.$

thus $|S|=\frac{1}{2}|F^{\times}|,$ which proves the uniqueness of $S$ (and therefore the uniqueness of $T$ ), because we know that a cyclic group cannot have two subgroups of the same order. Q.E.D.

Remark: the above proof also gives the set $S$ (and therefore $T$ ): suppose $F^{\times}=<\alpha>.$ then $S=<\alpha^2>$ and $T=F^{\times}-S.$