Thread: Quadratic residues

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?

Originally Posted by Cairo

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 be a finite field of odd order and we know that is a cyclic group. there exist unique non-empty sets which satisfy the following conditions:

1) and

2)

3)

4)

Proof: first note that 1) & 3) implies that and thus by 4) we have for all thus by 2), is a subgroup of now fix see that and

thus which proves the uniqueness of (and therefore the uniqueness of ), 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 (and therefore ): suppose then and