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

• Jun 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$?
• Jun 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?
• Jun 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?
• Jun 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?
• Jun 25th 2010, 04:08 PM
jamix
Chip....See next post below.

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}$.
• Jun 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}$
• Jun 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?
• Jun 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!
• Jun 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$
• Jun 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}^*$
• Jun 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)$