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

Printable View

June 25th 2010, 11:09 AM
jamix

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}) = (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$ ?
June 25th 2010, 12:27 PM
chiph588@

Quote:

Originally Posted by jamix

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}) = (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?
June 25th 2010, 12:50 PM
jamix

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?
June 25th 2010, 03:34 PM
chiph588@

Quote:

Originally Posted by jamix

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?
June 25th 2010, 04:08 PM
jamix

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}$ .
June 25th 2010, 04:21 PM
jamix

Quote:

Originally Posted by chiph588@

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}$
June 25th 2010, 06:16 PM
chiph588@

Quote:

Originally Posted by jamix

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}) = (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?
June 25th 2010, 07:12 PM
jamix

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!
June 25th 2010, 08:16 PM
chiph588@

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$
June 25th 2010, 09:20 PM
simplependulum

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}^*$
June 26th 2010, 12:00 AM
jamix

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)$