Re: Jacobi symbols of higher degree
From: Kristian Gjøsteen (kristiag+news_at_item.ntnu.no)
Date: Mon, 17 Oct 2005 19:34:54 +0000 (UTC)
MB <firstname.lastname@example.org> wrote:
>Let r=2^k, and to make things simpler consider a prime modulus p. Take
>c at random in Z*_p. Give a lower bound to the probability that
>C=c^(2^k) is *not* a 2^(k+1)-th residue.
>If c is a quadratic residue (QR) then C will be a 2^(k+1)-th residue.
>But what if c is a non QR (NR)? It is tempting to conclude that then C
>is not a 2^(k+1)-th residue either, so that the wanted bound would be
>1/2, but this is likely to be false.
Let p=2rs+1. Then x is a 2r-th residue iff x has order s.
If c is a quadratic residue, then the order of c divides rs, and
the order of C divides s.
If c is a non-quadratic residue, then 2r must divide the order of
c, hence 2 divides the order of C, and C is not a 2r-th residue.
>For example, if r=2^2=4, c is NR and i= sqrt(-1) mod p is also NR, then
>i*c is QR, and has a square root say alpha. Then alpha is an 8th root
>of C=2^4 (I haven't checked with numerical data if this situation can
>ever arise, though).
Let's consider p=41=2*4*5+1. -1 has square roots 9 and -9. But 9
is a quadratic residue.
-- Kristian Gjøsteen