Re: Order question

From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 04/29/04 

Date: Thu, 29 Apr 2004 22:38:03 +0100

Gregory G Rose wrote:

> Some terminology nits below.

I should tighten up my notation. My bad.

 
>> A safe prime p=2q+1 has a unique subgroup of order q. This is either the
>> unique subgroup of quadratic residues or the subgroup of non-residues, but
>> which one?
>
> To be a subgroup, it must be closed under
> multiplication, and include the identity. Since
> 1*1=1, 1 is a quadratic residue. Therefore it's
> always the quadratic residues that form the
> subgroup.
>
>> Take 11 = 2*5+1 as an example. 1,3,4,5,and 9 are quadratic residues, and
>> 2,6,7,8 and 10 are non-residues. Both groups have five members.
>
> No, {2,6,7,8,10} is not a group, and hence not a
> subgroup. It has no identity and is not closed.

Thanks. That was the answer I wanted.

Next question. Can you simply show that the subgroup of order q is the same
group as the group of QR's? I've done this before, but I lost it. 

-- 
Peter Fairbrother