C (Number Theory)

(\frac{a}{p}) = ⎩ ⎨ ⎧ 0, 1, - 1, p ∣ a, a is a nonzero square modulo p, a is not a square modulo p .

It depends only on the residue class of

a

p

ii

a^{(p - 1) /2} \equiv (\frac{a}{p}) (mod p) .

For

p ∤ a

, the sign is

+ 1

precisely for a quadratic residue and

- 1

p ∣ a

, both sides are zero.

Write

s = (a / p)

. If

p ∣ a

, both sides of the proposed identity are zero. Otherwise

s = \pm 1

(\frac{s a}{p}) = (\frac{s}{p}) (\frac{a}{p}) = s^{(p - 1) /2} s = s^{(p + 1) /2} .

For the middle equality, Euler's congruence determines the sign exactly, since both the symbol and

s^{(p - 1) /2}

are in

{1, - 1}

and

p

is odd.

Again

s = (a / p) \in {1, - 1}

(s / p) = s^{(p - 1) /2}

. If

p \equiv 1 (mod 4)

, the exponent is even and the answer is one. If

p \equiv 3 (mod 4)

, it is odd and the answer is

s

. Hence

(\frac{( a / p )}{p}) = {1, (a / p), p \equiv 1 (mod 4), p \equiv 3 (mod 4) .

There are no discussions about this article yet.

There are currently no matching articles.