Results 1 to 11 of 11

Math Help - Group order of Z_p + Z_p*(sqrt(n))

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    Group order of Z_p + Z_p*(sqrt(n))

    If anyone can shed some light on the problem below (even if your unsure of the answer), your help would be much appreciated.

    Let n be a positive non-square integer and p a prime number.

    Consider the set S = Z_p + Z_p \cdot \sqrt{n}

    In this set, we define multiplication as follows:

    A \cdot B = (a_1 + b_1\cdot \sqrt{n}) \cdot (a_2 + b_2\cdot \sqrt{n}) = <br /> <br />
(a_1 \cdot a_2 + n \cdot b_1 \cdot b_2) Z_p  + ((a_1 \cdot b_2 + b_1 \cdot a_2)Z_p) \cdot  \sqrt{n}

    The questions I'm interested in are the following:

    1) Does this set contain primitive elements regardless of (p,n)? That is, does there always exist some element a such that a^{p^2 - 1} \equiv 1 mod(S).

    2) If the answer to the above is in the negative, then when is the multiplicative order of S less than p^2 - 1? When is it equal to p^2 - 1?
    Last edited by jamix; June 25th 2010 at 11:11 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by jamix View Post
    If anyone can shed some light on the problem below (even if your unsure of the answer), your help would be much appreciated.

    Let n be a positive non-square integer and p a prime number.

    Consider the set S = Z_p + Z_p \cdot \sqrt{n}

    In this set, we define multiplication as follows:

    A \cdot B = (a_1 + b_1\cdot \sqrt{n}) \cdot (a_2 + b_2\cdot \sqrt{n}) = <br /> <br />
(a_1 \cdot a_2 + n \cdot b_1 \cdot b_2) Z_p  + ((a_1 \cdot b_2 + b_1 \cdot a_2)Z_p) \cdot  \sqrt{n}

    The questions I'm interested in are the following:

    1) Does this set contain primitive elements regardless of (p,n)? That is, does there always exist some element a such that a^{p^2 - 1} \equiv 1 mod(S).

    2) If the answer to the above is in the negative, then when is the multiplicative order of S less than p^2 - 1? When is it equal to p^2 - 1?
    What is  S ? Is it arbitrary?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148
    I forgot to put in the indexes.

    We have S_n,_p = Z_p + Z_p \cdot \sqrt{n}

    where n is a positive non-square integer and p is a prime number.

    Does it make sense now?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by jamix View Post
    I forgot to put in the indexes.

    We have S_n,_p = Z_p + Z_p \cdot \sqrt{n}

    where n is a positive non-square integer and p is a prime number.

    Does it make sense now?
    No, How do you perform mod S?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2008
    Posts
    148
    Chip....See next post below.

    So I've been thinking about this some more...

    A good first step to solving this is to first determine the number of invertible elements in S_{n,p}. The reason being that an group can only have a primitive element if every nonzero element has an inverse. That is |S^{*}| = p^2 - 1.


    Anyway the following below shows that we can never have |S^{*}| = p^2 - 1 for this type of set:

    For x = (a_1 + b_1 \cdot \sqrt{n}) we want to show that there exists an element y = a_2 + b_2 \cdot \sqrt{n} such that x \cdot y \equiv 1 mod(S_{n,p}).

    In order for this to happen, y must satisfy the following with x.

    i)

    a_1 \cdot b_2 + b_1 \cdot a_2 \equiv 0

    ii)

    a_1 \cdot a_2 + n \cdot b_1 \cdot b_2 \equiv 1

    Using equation i), we have b_2 \equiv a_1^{-1} \cdot -b_1 \cdot a_2.

    Subbing the above into ii) for b_2 gives us the following:

    a_1 \cdot a_2 - b_1^{2} \cdot a_2 \cdot a_1^{-1} \cdot n \equiv 1

    Multiplying both sides by a_1 gives

    a_1^{2} \cdot a_2 - b_1^{2} \cdot a_2 \cdot n \equiv a_1

    Letting C_1 \equiv a_1^{2} -b_1^{2} \cdot n


    The above can be written as C_1 \cdot a_2  \equiv a_1

    Clearly from the above we cannot have a_1 \equiv 0 (as this would imply b_1 \equiv 0).

    Furthermore, we cannot have C_1 \equiv a_1^{2} -b_1^{2} \cdot n \equiv 0.

    As there exist nonzero elements which will not satisfy C_1 \cdot a_2  \equiv a_1, its clear that |S^{*}| < p^2 - 1. But this implies that there are no primitive elements in S_{n,p}.
    Last edited by jamix; June 25th 2010 at 04:23 PM. Reason: Added info
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by chiph588@ View Post
    No, How do you perform mod S?
    After you've done the multiplication x \cdot y = A + B \cdot \sqrt{n}, you calculate it mod(S_{n,p}) by reducing both A and B over mod(p).

    For instance, suppose x = 7 + 11 \cdot \sqrt{5} and y = 4 + 6 \cdot \sqrt{5} are elements in S_{5,23}.

    Then x \cdot y \equiv (7 + 11 \cdot \sqrt{5}) \cdot (4 + 6 \cdot \sqrt{5}) \equiv (7 \cdot 4 + 11 \cdot 6 \cdot 5) + (7 \cdot 6 + 11 \cdot 4) \cdot \sqrt{5} \equiv 358 + 86 \cdot \sqrt{5} \equiv 13 + 17 \cdot \sqrt{5}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by jamix View Post
    If anyone can shed some light on the problem below (even if your unsure of the answer), your help would be much appreciated.

    Let n be a positive non-square integer and p a prime number.

    Consider the set S = Z_p + Z_p \cdot \sqrt{n}

    In this set, we define multiplication as follows:

    A \cdot B = (a_1 + b_1\cdot \sqrt{n}) \cdot (a_2 + b_2\cdot \sqrt{n}) = <br /> <br />
(a_1 \cdot a_2 + n \cdot b_1 \cdot b_2) Z_p  + ((a_1 \cdot b_2 + b_1 \cdot a_2)Z_p) \cdot  \sqrt{n}

    The questions I'm interested in are the following:

    1) Does this set contain primitive elements regardless of (p,n)? That is, does there always exist some element a such that a^{p^2 - 1} \equiv 1 mod(S).

    2) If the answer to the above is in the negative, then when is the multiplicative order of S less than p^2 - 1? When is it equal to p^2 - 1?
    Doesn't  a=1 work?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2008
    Posts
    148
    Yeah, but its not primitive.

    I forgot to add the line that in addition to a^{p^2 - 1} \equiv 1, we cannot have a^{M} \equiv 1 for M < p^2 - 1. The definition of a primitive element, is that a^{n} goes through all of the elements of S_{n,p} except for 0.

    In my second to last post I showed that no such element can exist since S^* < p^2 - 1. The next question to ask now is to determine just how large S^{*} can be? This will place an upper bound on the maximal order of any element of S_{n,p}.

    .................................................. ..

    There should be some theory already developed on this. This stuff belongs in the field of Algebraic Number Theory. Sets such as S_{n,p} where used in that wonderful proof described on wiki (which you linked to in the other thread) on the Lucas-Lehmer test!
    Last edited by jamix; June 25th 2010 at 07:13 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Actually I think  S is a field.

     S=\mathbb{Z}_p(\sqrt{n})\cong\mathbb{Z}_p[x]/\langle x^2-n \rangle

    This means  |S^\times|=|S|-1=p^2-1 .

    As a sanity check, consider  \left(\mathbb{Z}_3(\sqrt{2})\right)^\times
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Jan 2009
    Posts
    715
    In Galois Theory , he ( himself) proved the primitive element theorem , so you only need to show it is a Galois field ,  x^2 - n = 0 and all the elements can be expressed in the form  a + bx  ~,~ a,b \in \mathbb{Z}_p . Be caution ,  x^2 - n must be irreducible over  \mathbb{Z}_p or in other words ,  n is quadratic non-residue in modulo  p .


    Besides , you can use the bijection :  f: S \to \mathbb{Z}_{p^2}  (a+b\sqrt{n})f = a+pb so what you need to show is the existence of primitive elements in  \mathbb{Z}_{p^2}^*
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2008
    Posts
    148
    That doesn't sound right. The existence of a primitive element implies that every nonzero element is invertible yes?

    On the other hand, the element 0+ \sqrt{n} doesn't have an inverse in S_{n,p} for any prime integer p.

    This is especially true if there were a bijection with Z_{p^2} since the maximum order of any element in this set is p \cdot (p-1)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. element of order II, in 2n order group
    Posted in the Advanced Algebra Forum
    Replies: 14
    Last Post: December 14th 2011, 09:32 AM
  2. Order of Group. Direct Product of Cyclic Group
    Posted in the Advanced Algebra Forum
    Replies: 9
    Last Post: November 19th 2011, 01:06 PM
  3. Prove that a group of order 375 has a subgroup of order 15
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 13th 2010, 11:08 PM
  4. Group of order pq must have subgroups of order p and q.
    Posted in the Advanced Algebra Forum
    Replies: 19
    Last Post: September 15th 2009, 12:04 PM
  5. Replies: 11
    Last Post: January 6th 2008, 09:33 AM

Search Tags


/mathhelpforum @mathhelpforum