2
$\begingroup$

I was reading A. L. Whiteman - A family of difference sets. On page 109, the author generalizes the reduced residue system modulo $v$ where $v=pq$, $p$ and $q$ are primes. At the last paragraph, can someone explain why if $p-1=df$ and $q-1=ef'$ and $(f,f')=1$, if $ff'$ is odd, then $-1 \equiv g^{(d/2)} \pmod v$, and if $ff'$ is even, there does not exist any $s$, $s=0,\dotsc, d-1$, where $d$ is $\operatorname{lcm}(p-1,q-1)$ such that $-1 \equiv g^{s}\pmod v$?

$\endgroup$
4
  • 1
    $\begingroup$ Could you give a reference to the paper? MSN has not heard of it. Without that, it seems impossible to answer your question, which, for example, does not define $g$. $\endgroup$ – LSpice May 3 at 21:41
  • 1
    $\begingroup$ $g$ is the common primitive root of p and q $\endgroup$ – Akanksha Gupta May 3 at 22:18
  • 1
    $\begingroup$ @LSpice it looks like it has DOI 10.1215/ijm/1255631810 $\endgroup$ – Mark May 3 at 23:15
  • 1
    $\begingroup$ @Mark, ah, it's Whiteman, not Whitman! Thanks! Here's your DOI link: Whiteman - A family of difference sets. I have edited accordingly. $\endgroup$ – LSpice May 3 at 23:46
3
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ In the paper, we start with the common primitive root $g=xy(mod pq)$. Then how $<x,xy>$ becomes the generating set? $\endgroup$ – Akanksha Gupta May 4 at 21:51
  • $\begingroup$ In the third para, can you elaborate more on the arguments. How $a^m \equiv -1 \mod p $ and how similar argument works for $b$ but in another case we get inconsistency. $\endgroup$ – Akanksha Gupta May 4 at 21:56
  • $\begingroup$ First -- the multiplicative group of $\mathbb{Z}_{pq}$ is not cyclic, so doesn't have a primitive root. Compute some examples to convince yourself of this. Second -- in the third paragraph, $m$ must be even to get a solution $\bmod p$ and odd for a solution $\bmod q$, which is impossible. So no power of $xy$ evaluates to $-1 \bmod pq$. I think your confusion here will be resolved by thinking about my first sentence, and computing some explicit examples. $\endgroup$ – Padraig Ó Catháin May 5 at 9:51
  • 1
    $\begingroup$ Sorry - I still don't see what you're trying to say. Whiteman's paper is an elaboration of the cyclotomic construction for difference sets. This is normally applied to a group of prime order. It might help you to understand the base case thoroughly, including the relation between the cyclotomic numbers and expressions of the prime as a sum of squares. Then the material in Whiteman's paper is intricate, but nothing one would not expect. In particular, you should see why Whiteman carries out the constructions he does for $-1$, and why this is only a detail in the main argument. $\endgroup$ – Padraig Ó Catháin May 7 at 7:16
  • 1
    $\begingroup$ There's a Chapter in Marshall Hall's Combinatorial Theory where all this is laid out in detail. $\endgroup$ – Padraig Ó Catháin May 7 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.