- #1

- 750

- 199

- Homework Statement
- The set ## \left \{ 1, 2, ..., 22 \right \} ## is to be split into two disjoint non-empty sets ## S ## and ## T ## in such a way that:

(i) the product (mod ## 23 ##) of any two elements of ## S ## lies in ## S ##;

(ii) the product (mod ## 23 ##) of any two elements of ## T ## lies in ## S ##;

(iii) the product (mod ## 23 ##) of any element of ## S ## and any element of ## T ## lies in ## T ##.

Prove that the only solution is

## S=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \} ##,

## T=\left \{ 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 \right \} ##.

- Relevant Equations
- If ## A ## and ## B ## are disjoint, then their union ## A\cup B ## contains ## m+k=(p-1)/2 ## integers in the interval ## [1, (p-1)/2] ##.

Proof:

Let ## p ## be an odd prime and ## G=\left \{ 1, 2, ..., p-1 \right \} ## be the set which can be expressed as the

union of two nonempty subsets ## S ## and ## T ## such that ## S\neq T ##.

Observe that ## p-1=22\implies p=23 ##.

Let ## g\in G ##.

Since ## g ## is either an element of ## S ## or ## T ##, it follows that ## g^{2}\in S ##.

This implies that ## S ## contains all quadratic residues modulo ## 23 ##.

Suppose for the sake of contradiction that there exists ## x\in S ## for ## (x|p)=-1 ##.

Note that there exists ## y\in T ##, so we have ## (y|p)=-1 ##.

Thus ## xy\in T ##, but ## (xy|p)=1 ##, which is a contradiction, so ## S ## cannot contain any quadratic non-residues modulo ## 23 ##.

Therefore, the only solution is ## S=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}, T=\left \{ 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 \right \} ##.

Let ## p ## be an odd prime and ## G=\left \{ 1, 2, ..., p-1 \right \} ## be the set which can be expressed as the

union of two nonempty subsets ## S ## and ## T ## such that ## S\neq T ##.

Observe that ## p-1=22\implies p=23 ##.

Let ## g\in G ##.

Since ## g ## is either an element of ## S ## or ## T ##, it follows that ## g^{2}\in S ##.

This implies that ## S ## contains all quadratic residues modulo ## 23 ##.

Suppose for the sake of contradiction that there exists ## x\in S ## for ## (x|p)=-1 ##.

Note that there exists ## y\in T ##, so we have ## (y|p)=-1 ##.

Thus ## xy\in T ##, but ## (xy|p)=1 ##, which is a contradiction, so ## S ## cannot contain any quadratic non-residues modulo ## 23 ##.

Therefore, the only solution is ## S=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}, T=\left \{ 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 \right \} ##.