Results 1 to 2 of 2

Math Help - 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 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.
    Last edited by NonCommAlg; July 4th 2009 at 06: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: February 11th 2011, 11:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 23rd 2009, 12:25 PM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: July 17th 2009, 09:26 PM
  4. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 07:45 PM
  5. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2007, 12:14 PM

Search Tags


/mathhelpforum @mathhelpforum