Proof about two disjoint non-empty sets ## S ## and ## T ##

  • Thread starter Thread starter Math100
  • Start date Start date
  • Tags Tags
    Proof Sets
AI Thread Summary
The discussion focuses on proving the unique decomposition of the set G = {1, 2, ..., 22} into two disjoint non-empty subsets S and T, where S contains all quadratic residues modulo 23 and T contains all quadratic non-residues. It establishes that if g is an element of G, then g² must belong to S, leading to the conclusion that S cannot contain any quadratic non-residues. The proof demonstrates that the only valid sets are S = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18} and T = {5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22}. The discussion emphasizes the necessity of satisfying specific multiplicative properties for S and T, confirming that this decomposition is indeed the only solution.
Math100
Messages
813
Reaction score
229
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 \} ##.
 
Physics news on Phys.org
Math100 said:
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=22## numbers with ##k\in [1,11]## and ##m\in [11,21].##
Math100 said:
## 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 ##.
No. This is the wrong way of conclusion. You have to show this after you have defined ##S##.

The idea is as before:

We have a field ##\mathbb{Z}_{23}## with a multiplicative group ##\mathbb{Z}_{23}^*=\{1,2,\ldots,22\}.##
We are looking for a split ##\mathbb{Z}_{23}^*=S \cup T## with ##S,T\neq \emptyset## and ##S\cap T=\emptyset.##
Furthermore, ##S## has to be a multiplicative group: ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##

An assumption would be that ##k=|S|=|T|=m=11## and that ##S## contains all quadratic residues modulo ##23## and ##T## all quadratic non-residues. We already saw in a previous thread that there are equally many quadratic residues as there are quadratic non-residues in ##\mathbb{Z}_{23}^*.##

\begin{align*}
S&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic residue modulo }23\}\\
T&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic non-residue modulo }23\}
\end{align*}
We now have two candidates. Given these two definitions, we must next prove that all properties of ##S## and ##T## are fulfilled.

Math100 said:
This implies that ## S ## contains all quadratic residues modulo ## 23 ##.
See above. The other way around. We set ##S## as this set and have to prove the properties.

##\left(\dfrac{a}{23}\right)=a^{11}\pmod{23}=1## for quadratic residues:
\begin{matrix}
1^{11}\equiv 1\pmod{23}\, & \,2^{11}\equiv 1 \equiv \pmod{23}\, & \,3^{11}\equiv 1\pmod{23}\, & \,4^{11}\equiv 1\pmod{23}\\
6^{11}\equiv 1\pmod{23}\, & \,8^{11}\equiv 1 \equiv \pmod{23}\, & \,9^{11}\equiv 1\pmod{23}\, & \,12^{11}\equiv 1\pmod{23}\\
13^{11}\equiv 1\pmod{23}\, & \,16^{11}\equiv 1 \equiv \pmod{23}\, & \,18^{11}\equiv 1\pmod{23}\, &
\end{matrix}
Thus
\begin{align*}
S&=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}\\
T&=\mathbb{Z}_{23}^*-S.
\end{align*}
We also have ##S,T\neq \emptyset\, , \, S\cap T =\emptyset\, , \,S\cup T =\mathbb{Z}_{23}^*.## From
$$
\left(\dfrac{a}{23}\right)\cdot \left(\dfrac{b}{23}\right)=\left(\dfrac{ab}{23}\right)\, , \,\left(\dfrac{a}{23}\right)=1\,(a\in S)\, , \,\left(\dfrac{a}{23}\right)=-1\,(a\in T)
$$
we get ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##

We finally need to show that this is the only possible decomposition of ##\mathbb{Z}_{23}^*## with the given properties. For that matter, we assume a second decomposition
$$
\mathbb{Z}_{23}^*=A\cup B\, , \,A \cap B=\emptyset\neq A,B\, , \,A\cdot A,B\cdot B\subseteq A,A\cdot B\subseteq B
$$
and show that ##A=S.## (##B=T## follows automatically.)

Can you prove these two statements: ##A=S## and "automatically"?
 
fresh_42 said:
... ##m+k=22## numbers with ##k\in [1,11]## and ##m\in [11,21].##

No. This is the wrong way of conclusion. You have to show this after you have defined ##S##.

The idea is as before:

We have a field ##\mathbb{Z}_{23}## with a multiplicative group ##\mathbb{Z}_{23}^*=\{1,2,\ldots,22\}.##
We are looking for a split ##\mathbb{Z}_{23}^*=S \cup T## with ##S,T\neq \emptyset## and ##S\cap T=\emptyset.##
Furthermore, ##S## has to be a multiplicative group: ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##

An assumption would be that ##k=|S|=|T|=m=11## and that ##S## contains all quadratic residues modulo ##23## and ##T## all quadratic non-residues. We already saw in a previous thread that there are equally many quadratic residues as there are quadratic non-residues in ##\mathbb{Z}_{23}^*.##

\begin{align*}
S&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic residue modulo }23\}\\
T&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic non-residue modulo }23\}
\end{align*}
We now have two candidates. Given these two definitions, we must next prove that all properties of ##S## and ##T## are fulfilled.See above. The other way around. We set ##S## as this set and have to prove the properties.

##\left(\dfrac{a}{23}\right)=a^{11}\pmod{23}=1## for quadratic residues:
\begin{matrix}
1^{11}\equiv 1\pmod{23}\, & \,2^{11}\equiv 1 \equiv \pmod{23}\, & \,3^{11}\equiv 1\pmod{23}\, & \,4^{11}\equiv 1\pmod{23}\\
6^{11}\equiv 1\pmod{23}\, & \,8^{11}\equiv 1 \equiv \pmod{23}\, & \,9^{11}\equiv 1\pmod{23}\, & \,12^{11}\equiv 1\pmod{23}\\
13^{11}\equiv 1\pmod{23}\, & \,16^{11}\equiv 1 \equiv \pmod{23}\, & \,18^{11}\equiv 1\pmod{23}\, &
\end{matrix}
Thus
\begin{align*}
S&=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}\\
T&=\mathbb{Z}_{23}^*-S.
\end{align*}
We also have ##S,T\neq \emptyset\, , \, S\cap T =\emptyset\, , \,S\cup T =\mathbb{Z}_{23}^*.## From
$$
\left(\dfrac{a}{23}\right)\cdot \left(\dfrac{b}{23}\right)=\left(\dfrac{ab}{23}\right)\, , \,\left(\dfrac{a}{23}\right)=1\,(a\in S)\, , \,\left(\dfrac{a}{23}\right)=-1\,(a\in T)
$$
we get ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##

We finally need to show that this is the only possible decomposition of ##\mathbb{Z}_{23}^*## with the given properties. For that matter, we assume a second decomposition
$$
\mathbb{Z}_{23}^*=A\cup B\, , \,A \cap B=\emptyset\neq A,B\, , \,A\cdot A,B\cdot B\subseteq A,A\cdot B\subseteq B
$$
and show that ##A=S.## (##B=T## follows automatically.)

Can you prove these two statements: ##A=S## and "automatically"?
Aren't the two statements of ## A=S ## and ## B=T ## ("automatically") the same as proving what's already proven from the first decomposition: ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##? What's different in the second decomposition from the first decomposition? Instead of ## S ## and ## T ##, we have ## A ## and ## B ## now. Or is there another way to prove this?
 
Math100 said:
Aren't the two statements of ## A=S ## and ## B=T ## ("automatically") the same as proving what's already proven from the first decomposition: ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##? What's different in the second decomposition from the first decomposition? Instead of ## S ## and ## T ##, we have ## A ## and ## B ## now. Or is there another way to prove this?
If ##A=S## then ##B=\mathbb{Z}_{23}^*-A=\mathbb{Z}_{23}^*-S=T.##

But ##A=S## is not automatically the case. E.g. ##A## could be all even numbers, and ##B## all odd numbers. We have to rule out that such a decomposition fulfills the properties. And we have to rule it out for any decomposition with the given properties.

The proof begins with:

Assume ##G:=\mathbb{Z}_{23}^* =A\cup B## with ##A\cap B =\emptyset## and ##A,B\neq \emptyset## and ##A\cdot A \subseteq A\, , \,A\cdot B \subseteq B\, , \,B\cdot B\subseteq A.##

Since ##A\subseteq G=S\cup T## we have ##A=S## in which case we are done, ##A\subset S## or ##A\not\subset S.##

Note that all elements of ##G## are invertible modulo ##23.## This means that for every ##g\in G## and every non-empty, proper subset ##M\subset G## holds ##g\cdot M \subset G,## i.e. ##g\cdot M## is also a non-empty proper subset of ##G.## In other words: left-multiplication in a (multiplicative) group is a bijection.

If ##A\subset S ## then ##B\not\subset T.## There is thus a ##b\in B## that is not in ##T,## i.e. it is contained in ##S.## Thus ##b\cdot B \subseteq A \subseteq S## and ## b\cdot A\subset S\cdot S\subseteq S.## So ##b\cdot G\subseteq S## and ##G\subseteq b^{-1}\cdot S \subset G## which is a contradiction. This disproves ##A\subseteq S.##

Assume ##A\not\subset S.## Then there is a ##a\in A\cap T.## If ##A\subset T## then ##A\cdot A\subseteq A\subset T## and ##A\cdot A\subseteq T\cdot T\subseteq S## which is not possible. Hence ##A\cap T\neq \emptyset \neq A\cap S.## But if ##A## intersects both, ##S## and ##T## non-trivially, so does ##B.##

Hence we must rule out the following situation:
1669081623418.png


Can you do this?
 
fresh_42 said:
If ##A=S## then ##B=\mathbb{Z}_{23}^*-A=\mathbb{Z}_{23}^*-S=T.##

But ##A=S## is not automatically the case. E.g. ##A## could be all even numbers, and ##B## all odd numbers. We have to rule out that such a decomposition fulfills the properties. And we have to rule it out for any decomposition with the given properties.

The proof begins with:

Assume ##G:=\mathbb{Z}_{23}^* =A\cup B## with ##A\cap B =\emptyset## and ##A,B\neq \emptyset## and ##A\cdot A \subseteq A\, , \,A\cdot B \subseteq B\, , \,B\cdot B\subseteq A.##

Since ##A\subseteq G=S\cup T## we have ##A=S## in which case we are done, ##A\subset S## or ##A\not\subset S.##

Note that all elements of ##G## are invertible modulo ##23.## This means that for every ##g\in G## and every non-empty, proper subset ##M\subset G## holds ##g\cdot M \subset G,## i.e. ##g\cdot M## is also a non-empty proper subset of ##G.## In other words: left-multiplication in a (multiplicative) group is a bijection.

If ##A\subset S ## then ##B\not\subset T.## There is thus a ##b\in B## that is not in ##T,## i.e. it is contained in ##S.## Thus ##b\cdot B \subseteq A \subseteq S## and ## b\cdot A\subset S\cdot S\subseteq S.## So ##b\cdot G\subseteq S## and ##G\subseteq b^{-1}\cdot S \subset G## which is a contradiction. This disproves ##A\subseteq S.##

Assume ##A\not\subset S.## Then there is a ##a\in A\cap T.## If ##A\subset T## then ##A\cdot A\subseteq A\subset T## and ##A\cdot A\subseteq T\cdot T\subseteq S## which is not possible. Hence ##A\cap T\neq \emptyset \neq A\cap S.## But if ##A## intersects both, ##S## and ##T## non-trivially, so does ##B.##

Hence we must rule out the following situation:
View attachment 317547

Can you do this?
So to rule out the following situation in which you listed above, one example would be ## S\cap B=S ## if ## B=S ##?
 
##S=A\, , \,S=B\, , \,T=A\, , \,T=B## are already ruled out. We must basically show that the principal character and the Legendre-symbol are the only two characters (multiplicative functions) with ##\chi^2=1.##

The reason is that ##\mathbb{Z}_{23}^*## has ##22=2 \cdot 11## elements and there is only one normal subgroup of order two. That means such a case as in the picture cannot occur. But why exactly?
 
fresh_42 said:
##S=A\, , \,S=B\, , \,T=A\, , \,T=B## are already ruled out. We must basically show that the principal character and the Legendre-symbol are the only two characters (multiplicative functions) with ##\chi^2=1.##

The reason is that ##\mathbb{Z}_{23}^*## has ##22=2 \cdot 11## elements and there is only one normal subgroup of order two. That means such a case as in the picture cannot occur. But why exactly?
I still don't really understand. Can you please tell me why?
 
I'm not sure whether the tools I would use are the tools you are expected to use. My plan would be to define
$$
\chi\, : \,\mathbb{Z}_{23}^*=:G \longrightarrow \mathbb{C}^*=\mathbb{C}-\{0\}\; , \;\chi(g)=\begin{cases}1&\text{ if }g\in A\\-1&\text{ if }g\in B\end{cases}
$$
Then
\begin{align*}
\chi(1)&=\chi(1\cdot 1)=\chi(1)\cdot \chi(1)\Longrightarrow \chi(1)=1\Longrightarrow 1\in A\\
\chi(gAg^{-1})&=\chi(g)\chi(A)\chi(g^{-1})=\chi(g)\cdot 1\cdot\chi(g^{-1})=\chi(g\cdot g^{-1})=\chi(1)=1
\end{align*}
This shows that ##A=\operatorname{ker}\chi \trianglelefteq G## is a normal subgroup. The order of any subgroup divides the order of the group. We have only two such prime divisors: ##|G|=22=2\cdot 11.## Hence ##A## has either ##2## or ##11## elements. Now ##B\neq \emptyset## so there is a ##b\in B-\{1\}## such that ##b\cdot A \cup A=G.## The mapping ##a\longmapsto b\cdot a## is a bijection since ##b## is invertible. So ##bA## and ##A## must have equally many elements. Thus, ##|A|=11.##

The exact same considerations can be made for the Legendre symbol. So ##1\in S.## Thus we have an element ##1\in S\,\cap \,A.## So we have two normal subgroups ##A\trianglelefteq G## and ##S\trianglelefteq G## with equally many elements, namely ##11##, that also share one element, namely ##1\in G.## But there is only one cyclic subgroup of ##G## with ##11## elements, ##S=\mathbb{Z}_{11}.## So ##S=A## and ##T=B.##

If you aren't familiar with this basic group theory, then you have to find another way to make sure that there can't be two different partitions of ##G=S\,\cup\,T=A\,\cup \,B.##

My idea: Look at ##3##. Then either ##3\in A## or ##3\in B.## Rule out the latter and show that all powers of ##3## already generate ##S.##
 
Forget that complicated stuff above; though it brought me the easier solution.

We have shown everything but uniqueness. We have ##\mathbb{Z}_{23}^*=S\,\cup\,T## partitioned in quadratic residues ##S## and quadratic non-residues ##T##. Now, let us assume that there is another partition ##\mathbb{Z}_{23}^*=A\,\cup\,B## such that ##A\cdot A ,B\cdot B \subseteq A, A\cdot B\subseteq B.## Then ##1=1\cdot 1\in A## and ##A\cdot A\subseteq A.## Moreover, if ##b\in B## then ##b\cdot A\subseteq B## and ##A\,\cup\,B= \mathbb{Z}_{23}^*## because ##A## and ##b\cdot A## have equally many elements, i.e. ##B=b\cdot A.## To show that ##A \trianglelefteq \mathbb{Z}_{23}^* ## is a subgroup, it remains to show that inverses of elements of ##A## are in ##A## again. Suppose ##a^{-1}\in b\cdot A,## i.e. ##A\ni 1=a^{-1}\cdot a=b\cdot a'\cdot a \in B## which is impossible since ##A## and ##B## are disjoint.
\begin{matrix}
3\cdot 3\equiv 9\pmod{23}&3\cdot 9\equiv 4\pmod{23}&3\cdot 4\equiv 12\pmod{23}&3\cdot 12\equiv 13\pmod{23}\\
3\cdot 13\equiv 16\pmod{23}&3\cdot 16\equiv 2\pmod{23}&3\cdot 2\equiv 6\pmod{23}&3\cdot 6\equiv 18\pmod{23}\\
3\cdot 18\equiv 8\pmod{23}&3\cdot 8\equiv 1\pmod{23}
\end{matrix}
If ##3\in B## then ##3^{11}=1\in A\,\cup\,B## which is impossible. So ##\langle 3 \rangle \cong \mathbb{Z}_{11}\subseteq A\trianglelefteq \mathbb{Z}_{23}^*## creates a cyclic subgroup with eleven elements: ##\langle 3 \rangle=A=\{1,2,3,4,6,8,9,12,13,16,18\}=S.##

Sorry, the idea was finally shorter than the solution with all the technical details:
  • ##1\in A##
  • ##B=b\cdot A##
  • ## A^{-1}\subseteq A##
  • ##A\trianglelefteq \mathbb{Z}_{23}^*## is a subgroup.
  • ##\mathbb{Z}_{23}^*=A \,\cup\,B##
  • ##3\in A##
  • ##\langle 3 \rangle = A = S##
 
Last edited:
  • #10
fresh_42 said:
Forget that complicated stuff above; though it brought me the easier solution.

We have shown everything but uniqueness. We have ##\mathbb{Z}_{23}^*=S\,\cup\,T## partitioned in quadratic residues ##S## and quadratic non-residues ##T##. Now, let us assume that there is another partition ##\mathbb{Z}_{23}^*=A\,\cup\,B## such that ##A\cdot A ,B\cdot B \subseteq A, A\cdot B\subseteq B.## Then ##1=1\cdot 1\in A## and ##A\cdot A\subseteq A.## Moreover, if ##b\in B## then ##b\cdot A\subseteq B## and ##A\,\cup\,B= \mathbb{Z}_{23}^*## because ##A## and ##b\cdot A## have equally many elements, i.e. ##B=b\cdot A.## To show that ##A \trianglelefteq \mathbb{Z}_{23}^* ## is a subgroup, it remains to show that inverses of elements of ##A## are in ##A## again. Suppose ##a^{-1}\in b\cdot A,## i.e. ##A\ni 1=a^{-1}\cdot a=b\cdot a'\cdot a \in B## which is impossible since ##A## and ##B## are disjoint.
\begin{matrix}
3\cdot 3\equiv 9\pmod{23}&3\cdot 9\equiv 4\pmod{23}&3\cdot 4\equiv 12\pmod{23}&3\cdot 12\equiv 13\pmod{23}\\
3\cdot 13\equiv 16\pmod{23}&3\cdot 16\equiv 2\pmod{23}&3\cdot 2\equiv 6\pmod{23}&3\cdot 6\equiv 18\pmod{23}\\
3\cdot 18\equiv 8\pmod{23}&3\cdot 8\equiv 1\pmod{23}
\end{matrix}
If ##3\in B## then ##3^{11}=1\in A\,\cup\,B## which is impossible. So ##\langle 3 \rangle \cong \mathbb{Z}_{11}\subseteq A\trianglelefteq \mathbb{Z}_{23}^*## creates a cyclic subgroup with eleven elements: ##\langle 3 \rangle=A=\{1,2,3,4,6,8,9,12,13,16,18\}=S.##

Sorry, the idea was finally shorter than the solution with all the technical details:
  • ##1\in A##
  • ##B=b\cdot A##
  • ## A^{-1}\subseteq A##
  • ##A\trianglelefteq \mathbb{Z}_{23}^*## is a subgroup.
  • ##\mathbb{Z}_{23}^*=A \,\cup\,B##
  • ##3\in A##
  • ##\langle 3 \rangle = A = S##
Don't say sorry, it's okay. I am the one who should apologize, because many stuffs above are things I never learned, I have no knowledge in group theory. So these are all new to me. For example, ##A\trianglelefteq \mathbb{Z}_{23}^*## is a subgroup, I've never seen ## \trianglelefteq ## before. But it's always beneficial to know and learn the new stuffs.
 
Last edited:
  • #11
There seems to be too, a Combinatorial side to this. This may be call a matching or an SDR ( System of Distinct Representatives) .
 
  • #12
Math100 said:
Don't say sorry, it's okay. I am the one who should apologize, because many stuffs above are things I never learned, I have no knowledge in group theory. So these are all new to me. For example, ##A\trianglelefteq \mathbb{Z}_{23}^*## is a subgroup, I've never seen ## \trianglelefteq ## before. But it's always beneficial to know and learn the new stuffs.
The point with the group is the following. I have observed that ##S## is equal to the set of all powers of, say ##3## modulo ##23.## If we have a second partition ##G=A\,\cup\,B## then ##3## is either an element of ##A## or an element of ##B##. The powers of ##3## could hop between ##A## and ##B## all the time.

We show, that ##A## is a group, i.e. it contains the neutral element ##1##, is closed under multiplication, i.e. ##A\cdot A \subseteq A,## a fact that is given by the properties of the partition and is closed under inversion ##A^{-1}\subseteq A## which has to be shown.

Then we show that ##3\in A##. But now we know that ##A## is a group, so all powers of its elements are also within ##A,## no hopping between ##A## and ##B## allowed for powers of elements of ##A##. Hence ##\{3^n\pmod{23}\,|\,n\in \mathbb{N}\} = S \subseteq A.##

I think I have forgotten the final part. We know that ##S\subseteq A## but we need to show ##A\subseteq S## also. Assume that there is an element ##a\in A## which is not in ##S.## Then ##a\in A\,\cup\,T## and ##a\cdot S\subseteq T.## But ##a\cdot S## and ##T## have both ##11## elements, so ##a\cdot S=T.## Thus
$$
G=S\,\cup\,T=S\,\cup\,a\cdot S\subseteq A\,\cup\,a\cdot A\subseteq A
$$
which contradicts ##B\neq \emptyset.## There is therefore no element ##a\in A-S,## i.e. ##A=S.##
 
Back
Top