Results 1 to 2 of 2

Thread: Quadratic residues

  1. #1
    Member
    Joined
    May 2008
    Posts
    140

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    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 $\displaystyle F$ be a finite field of odd order and $\displaystyle F^{\times}=F-\{0\}.$ we know that $\displaystyle F^{\times}$ is a cyclic group. there exist unique non-empty sets $\displaystyle S,T \subset \mathbb{F}^{\times}$ which satisfy the following conditions:

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

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

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

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

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

    thus $\displaystyle |S|=\frac{1}{2}|F^{\times}|,$ which proves the uniqueness of $\displaystyle S$ (and therefore the uniqueness of $\displaystyle 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 $\displaystyle S$ (and therefore $\displaystyle T$): suppose $\displaystyle F^{\times}=<\alpha>.$ then $\displaystyle S=<\alpha^2>$ and $\displaystyle T=F^{\times}-S.$
    Last edited by NonCommAlg; Jul 4th 2009 at 05:05 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Feb 11th 2011, 10:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jul 23rd 2009, 11:25 AM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: Jul 17th 2009, 08:26 PM
  4. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 27th 2008, 06:45 PM
  5. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2007, 11:14 AM

Search Tags


/mathhelpforum @mathhelpforum