Skip to main content
deleted 21 characters in body
Source Link

The multiplicative group of $\mathbb{Z}_{pq} \cong \mathbb{Z}_{p} \times \mathbb{Z}_{q}$ is not cyclic, but is generated by $x =(a,1)$ and $y = (1,b)$ where $a$ is a primitive root mod $p$ and $b$ is primitive mod $q$. Whiteman's Lemma 1 shows that $xy$ has order the least common multiple of $p-1$ and $q-1$. Clearly $\langle x, xy\rangle$ is a generating set for the whole multiplicative group.

In the portion of the paper to which the question refers, Whiteman wants to decide whether $-1 \in \langle xy\rangle$. Equivalently, whether there exists an integer $m$ such that $a^m \equiv -1 \bmod p$ and $b^m \equiv -1 \bmod q$.

Whiteman's choice of notation is standard for working with cyclotomic difference sets, but slightly hard to follow otherwise. Let $e = \gcd(p-1, q-1)$, and suppose that both $\frac{p-1}{e}$ and $\frac{q-1}{e}$ are odd. Taking $m = \frac{(p-1)(q-1)}{2e}$, it's easy to see that $a^m = (a^{(q-1)/e})^{(p-1)/2} \equiv -1 \bmod p$ and similarly for $b$. So $(xy)^m \equiv -1 \bmod pq$.

On the other hand, if $\frac{p-1}{e}$ is even and $\frac{q-1}{e}$ is odd, the conditions on $a^{m} \equiv -1 \bmod p$ and $b^{m} \equiv -1 \bmod q$ are inconsistent and $-1 \notin \langle xy \rangle$. Whiteman goes on to express $-1$ as a product of generators of the multiplicative group.

The multiplicative group of $\mathbb{Z}_{pq} \cong \mathbb{Z}_{p} \times \mathbb{Z}_{q}$ is not cyclic, but is generated by $x =(a,1)$ and $y = (1,b)$ where $a$ is a primitive root mod $p$ and $b$ is primitive mod $q$. Whiteman's Lemma 1 shows that $xy$ has order the least common multiple of $p-1$ and $q-1$. Clearly $\langle x, xy\rangle$ is a generating set for the whole multiplicative group.

In the portion of the paper to which the question refers, Whiteman wants to decide whether $-1 \in \langle xy\rangle$. Equivalently, whether there exists an integer $m$ such that $a^m \equiv -1 \bmod p$ and $b^m \equiv -1 \bmod q$.

Whiteman's choice of notation is standard for working with cyclotomic difference sets, but slightly hard to follow otherwise. Let $e = \gcd(p-1, q-1)$, and suppose that both $\frac{p-1}{e}$ and $\frac{q-1}{e}$ are odd. Taking $m = \frac{(p-1)(q-1)}{2e}$, it's easy to see that $a^m = (a^{(q-1)/e})^{(p-1)/2} \equiv -1 \bmod p$ and similarly for $b$. So $(xy)^m \equiv -1 \bmod pq$.

On the other hand, if $\frac{p-1}{e}$ is even and $\frac{q-1}{e}$ is odd, the conditions on $a^{m} \equiv -1 \bmod p$ and $b^{m} \equiv -1 \bmod q$ are inconsistent and $-1 \notin \langle xy \rangle$. Whiteman goes on to express $-1$ as a product of generators of the multiplicative group.

The multiplicative group of $\mathbb{Z}_{pq} \cong \mathbb{Z}_{p} \times \mathbb{Z}_{q}$ is not cyclic, but is generated by $x =(a,1)$ and $y = (1,b)$ where $a$ is a primitive root mod $p$ and $b$ is primitive mod $q$. Whiteman's Lemma 1 shows that $xy$ has order the least common multiple of $p-1$ and $q-1$. Clearly $\langle x, xy\rangle$ is the whole multiplicative group.

In the portion of the paper to which the question refers, Whiteman wants to decide whether $-1 \in \langle xy\rangle$. Equivalently, whether there exists an integer $m$ such that $a^m \equiv -1 \bmod p$ and $b^m \equiv -1 \bmod q$.

Whiteman's choice of notation is standard for working with cyclotomic difference sets, but slightly hard to follow otherwise. Let $e = \gcd(p-1, q-1)$, and suppose that both $\frac{p-1}{e}$ and $\frac{q-1}{e}$ are odd. Taking $m = \frac{(p-1)(q-1)}{2e}$, it's easy to see that $a^m = (a^{(q-1)/e})^{(p-1)/2} \equiv -1 \bmod p$ and similarly for $b$. So $(xy)^m \equiv -1 \bmod pq$.

On the other hand, if $\frac{p-1}{e}$ is even and $\frac{q-1}{e}$ is odd, the conditions on $a^{m} \equiv -1 \bmod p$ and $b^{m} \equiv -1 \bmod q$ are inconsistent and $-1 \notin \langle xy \rangle$. Whiteman goes on to express $-1$ as a product of generators of the multiplicative group.

`\mod` almost always spaces badly compared to `\bmod`
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

The multiplicative group of $\mathbb{Z}_{pq} \cong \mathbb{Z}_{p} \times \mathbb{Z}_{q}$ is not cyclic, but is generated by $x =(a,1)$ and $y = (1,b)$ where $a$ is a primitive root mod $\mod p$$p$ and $b$ is primitive mod $\mod q$$q$. Whiteman's Lemma 1 shows that $xy$ has order the least common multiple of $p-1$ and $q-1$. Clearly $\langle x, xy\rangle$ is a generating set for the whole multiplicative group.

In the portion of the paper to which the question refers, Whiteman wants to decide whether $-1 \in \langle xy\rangle$. Equivalently, whether there exists an integer $m$ such that $a^m \equiv -1 \mod p$$a^m \equiv -1 \bmod p$ and $b^m \equiv -1 \mod q$$b^m \equiv -1 \bmod q$.

Whiteman's choice of notation is standard for working with cyclotomic difference sets, but slightly hard to follow otherwise. Let $e = \textrm{gcd}(p-1, q-1)$$e = \gcd(p-1, q-1)$, and suppose that both $\frac{p-1}{e}$ and $\frac{q-1}{e}$ are odd. Taking $m = \frac{(p-1)(q-1)}{2e}$, it's easy to see that $a^m = (a^{(q-1)/e})^{(p-1)/2} \equiv -1 \mod p$$a^m = (a^{(q-1)/e})^{(p-1)/2} \equiv -1 \bmod p$ and similarly for $b$. So $(xy)^m \equiv -1 \mod pq$$(xy)^m \equiv -1 \bmod pq$.

On the other hand, if $\frac{p-1}{e}$ is even and $\frac{q-1}{e}$ is odd, the conditions on $a^{m} \equiv -1 \mod p$$a^{m} \equiv -1 \bmod p$ and $b^{m} \equiv -1 \mod q$$b^{m} \equiv -1 \bmod q$ are inconsistent and $-1 \notin \langle xy \rangle$. Whiteman goes on to express $-1$ as a product of generators of the multiplicative group.

The multiplicative group of $\mathbb{Z}_{pq} \cong \mathbb{Z}_{p} \times \mathbb{Z}_{q}$ is not cyclic, but is generated by $x =(a,1)$ and $y = (1,b)$ where $a$ is a primitive root $\mod p$ and $b$ is primitive $\mod q$. Whiteman's Lemma 1 shows that $xy$ has order the least common multiple of $p-1$ and $q-1$. Clearly $\langle x, xy\rangle$ is a generating set for the whole multiplicative group.

In the portion of the paper to which the question refers, Whiteman wants to decide whether $-1 \in \langle xy\rangle$. Equivalently, whether there exists an integer $m$ such that $a^m \equiv -1 \mod p$ and $b^m \equiv -1 \mod q$.

Whiteman's choice of notation is standard for working with cyclotomic difference sets, but slightly hard to follow otherwise. Let $e = \textrm{gcd}(p-1, q-1)$, and suppose that both $\frac{p-1}{e}$ and $\frac{q-1}{e}$ are odd. Taking $m = \frac{(p-1)(q-1)}{2e}$, it's easy to see that $a^m = (a^{(q-1)/e})^{(p-1)/2} \equiv -1 \mod p$ and similarly for $b$. So $(xy)^m \equiv -1 \mod pq$.

On the other hand, if $\frac{p-1}{e}$ is even and $\frac{q-1}{e}$ is odd, the conditions on $a^{m} \equiv -1 \mod p$ and $b^{m} \equiv -1 \mod q$ are inconsistent and $-1 \notin \langle xy \rangle$. Whiteman goes on express $-1$ as a product of generators of the multiplicative group.

The multiplicative group of $\mathbb{Z}_{pq} \cong \mathbb{Z}_{p} \times \mathbb{Z}_{q}$ is not cyclic, but is generated by $x =(a,1)$ and $y = (1,b)$ where $a$ is a primitive root mod $p$ and $b$ is primitive mod $q$. Whiteman's Lemma 1 shows that $xy$ has order the least common multiple of $p-1$ and $q-1$. Clearly $\langle x, xy\rangle$ is a generating set for the whole multiplicative group.

In the portion of the paper to which the question refers, Whiteman wants to decide whether $-1 \in \langle xy\rangle$. Equivalently, whether there exists an integer $m$ such that $a^m \equiv -1 \bmod p$ and $b^m \equiv -1 \bmod q$.

Whiteman's choice of notation is standard for working with cyclotomic difference sets, but slightly hard to follow otherwise. Let $e = \gcd(p-1, q-1)$, and suppose that both $\frac{p-1}{e}$ and $\frac{q-1}{e}$ are odd. Taking $m = \frac{(p-1)(q-1)}{2e}$, it's easy to see that $a^m = (a^{(q-1)/e})^{(p-1)/2} \equiv -1 \bmod p$ and similarly for $b$. So $(xy)^m \equiv -1 \bmod pq$.

On the other hand, if $\frac{p-1}{e}$ is even and $\frac{q-1}{e}$ is odd, the conditions on $a^{m} \equiv -1 \bmod p$ and $b^{m} \equiv -1 \bmod q$ are inconsistent and $-1 \notin \langle xy \rangle$. Whiteman goes on to express $-1$ as a product of generators of the multiplicative group.

Source Link

The multiplicative group of $\mathbb{Z}_{pq} \cong \mathbb{Z}_{p} \times \mathbb{Z}_{q}$ is not cyclic, but is generated by $x =(a,1)$ and $y = (1,b)$ where $a$ is a primitive root $\mod p$ and $b$ is primitive $\mod q$. Whiteman's Lemma 1 shows that $xy$ has order the least common multiple of $p-1$ and $q-1$. Clearly $\langle x, xy\rangle$ is a generating set for the whole multiplicative group.

In the portion of the paper to which the question refers, Whiteman wants to decide whether $-1 \in \langle xy\rangle$. Equivalently, whether there exists an integer $m$ such that $a^m \equiv -1 \mod p$ and $b^m \equiv -1 \mod q$.

Whiteman's choice of notation is standard for working with cyclotomic difference sets, but slightly hard to follow otherwise. Let $e = \textrm{gcd}(p-1, q-1)$, and suppose that both $\frac{p-1}{e}$ and $\frac{q-1}{e}$ are odd. Taking $m = \frac{(p-1)(q-1)}{2e}$, it's easy to see that $a^m = (a^{(q-1)/e})^{(p-1)/2} \equiv -1 \mod p$ and similarly for $b$. So $(xy)^m \equiv -1 \mod pq$.

On the other hand, if $\frac{p-1}{e}$ is even and $\frac{q-1}{e}$ is odd, the conditions on $a^{m} \equiv -1 \mod p$ and $b^{m} \equiv -1 \mod q$ are inconsistent and $-1 \notin \langle xy \rangle$. Whiteman goes on express $-1$ as a product of generators of the multiplicative group.