# 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 $\displaystyle n$ be a positive non-square integer and $\displaystyle p$ a prime number.

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

In this set, we define multiplication as follows:

$\displaystyle 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 $\displaystyle (p,n)$? That is, does there always exist some element $\displaystyle a$ such that $\displaystyle 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 $\displaystyle p^2 - 1$? When is it equal to $\displaystyle 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 $\displaystyle n$ be a positive non-square integer and $\displaystyle p$ a prime number.

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

In this set, we define multiplication as follows:

$\displaystyle 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 $\displaystyle (p,n)$? That is, does there always exist some element $\displaystyle a$ such that $\displaystyle 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 $\displaystyle p^2 - 1$? When is it equal to $\displaystyle p^2 - 1$?

What is $\displaystyle S$? Is it arbitrary?
• Jun 25th 2010, 12:50 PM
jamix
I forgot to put in the indexes.

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

where $\displaystyle n$ is a positive non-square integer and $\displaystyle 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 $\displaystyle S_n,_p = Z_p + Z_p \cdot \sqrt{n}$

where $\displaystyle n$ is a positive non-square integer and $\displaystyle 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 $\displaystyle S_{n,p}$. The reason being that an group can only have a primitive element if every nonzero element has an inverse. That is $\displaystyle |S^{*}| = p^2 - 1$.

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

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

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

i)

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

ii)

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

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

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

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

Multiplying both sides by $\displaystyle a_1$ gives

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

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

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

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

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

As there exist nonzero elements which will not satisfy $\displaystyle C_1 \cdot a_2 \equiv a_1$, its clear that $\displaystyle |S^{*}| < p^2 - 1$. But this implies that there are no primitive elements in $\displaystyle 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 $\displaystyle x \cdot y = A + B \cdot \sqrt{n}$, you calculate it $\displaystyle mod(S_{n,p})$ by reducing both $\displaystyle A$ and $\displaystyle B$ over $\displaystyle mod(p)$.

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

Then $\displaystyle 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 $\displaystyle n$ be a positive non-square integer and $\displaystyle p$ a prime number.

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

In this set, we define multiplication as follows:

$\displaystyle 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 $\displaystyle (p,n)$? That is, does there always exist some element $\displaystyle a$ such that $\displaystyle 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 $\displaystyle p^2 - 1$? When is it equal to $\displaystyle p^2 - 1$?

Doesn't $\displaystyle 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 $\displaystyle a^{p^2 - 1} \equiv 1$, we cannot have $\displaystyle a^{M} \equiv 1$ for $\displaystyle M < p^2 - 1$. The definition of a primitive element, is that $\displaystyle a^{n}$ goes through all of the elements of $\displaystyle S_{n,p}$ except for 0.

In my second to last post I showed that no such element can exist since $\displaystyle S^* < p^2 - 1$. The next question to ask now is to determine just how large $\displaystyle S^{*}$ can be? This will place an upper bound on the maximal order of any element of $\displaystyle 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 $\displaystyle 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 $\displaystyle S$ is a field.

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

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

As a sanity check, consider $\displaystyle \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 , $\displaystyle x^2 - n = 0$ and all the elements can be expressed in the form $\displaystyle a + bx ~,~ a,b \in \mathbb{Z}_p$ . Be caution , $\displaystyle x^2 - n$ must be irreducible over $\displaystyle \mathbb{Z}_p$ or in other words , $\displaystyle n$ is quadratic non-residue in modulo $\displaystyle p$ .

Besides , you can use the bijection : $\displaystyle f: S \to \mathbb{Z}_{p^2}$ $\displaystyle (a+b\sqrt{n})f = a+pb$ so what you need to show is the existence of primitive elements in $\displaystyle \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 $\displaystyle 0+ \sqrt{n}$ doesn't have an inverse in $\displaystyle S_{n,p}$ for any prime integer $\displaystyle p$.

This is especially true if there were a bijection with $\displaystyle Z_{p^2}$ since the maximum order of any element in this set is $\displaystyle p \cdot (p-1)$