0
$\begingroup$

Theorem 3.1, part 1. Let $p$ be an odd prime. Then, every $a \in \mathbb{Z}$ satisfies $\left(\dfrac{a}{p}\right) \equiv a^{\left(p-1\right)/2}\mod p$, where $\left(\dfrac{a}{p}\right)$ denotes the Kronecker symbol.

This is the proof from the textbook (Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition 1991): enter image description here

For the last third line, I don't understand what's the relation between $jj'$ and $(p-1)!$. "The combined contribution of $j$ and $j'$ to $(p-1)!$", does it mean $jj'^{(p-1)!}$? (This is part of an argument that if $\left(\dfrac{a}{p}\right) = -1$, then $a^{\left(p-1\right)/2} \equiv -1 \mod p$.)

Can anyone explain or show me a better proof?

$\endgroup$
2
$\begingroup$

Explanation: For odd prime $p.$ When $a$ is a non-square modulo $p$:

Partition the set $\{1,2,...,p-1\}$ into a collection of pairs $\{j,j'\}$ where $jj'\equiv a.$ For each such pair we have $j'\not \equiv j$ because $a$ is a non-square mod $p.$ Each member of $\{1,2,...,p-1\}$ belongs to just one of these pairs, because if $\{j,j'\}$ and $\{j,j''\}$ are two such pairs then $jj'\equiv a\equiv jj''\not \equiv 0,$ so $j'=j''$.

Let $S$ be the set of all these pairs. The main point is that $$(1).\quad \prod_{\{j,j'\} \in S} \left(jj'\right) \equiv (p-1)!$$ because each member of $\{1,2,...,p-1\}$ occurs exactly once ( as $j$ or $j'$) on the LHS of (1). And also $$(2),\quad \prod_{\{j,j'\} \in S} \left(jj'\right) \equiv a^{(p-1)/2}$$ because there are $(p-1)/2$ pairs in $S$ and for each $\{j,j'\}\in S$ we have $jj'\equiv a.$ Therefore $$\left( \frac {a}{p} \right)=-1\equiv (p-1)!\equiv a^{(p-1)/2}.$$

$\endgroup$
  • $\begingroup$ Cool, I get the main idea. But I have a little question. Must $jj' \equiv a$ exists? I know $jj' \equiv 1$ exists, but I'm not sure for any $a$ . $\endgroup$ – yashirq Nov 29 '16 at 4:04
  • $\begingroup$ If j$k\equiv 1$ let $j'=ka.$ Then $ jj'\equiv a.$ $\endgroup$ – DanielWainfleet Nov 29 '16 at 4:14
2
$\begingroup$

Here is another proof. All $\equiv$ symbols are congruences modulo $p$. First, since $\left(a^{\frac{p-1}{2}}\right)^2 \equiv 1$ you have $$a^\frac{p-1}{2} \equiv \pm 1 \,.$$

Let $b$ be a primitive root modulo $p$. Then $$a\equiv b^k \,.$$

If $\left( \frac{a}{p} \right)=-1$ then $k$ is odd.

Assume for contradiction that $$a^\frac{p-1}{2} \equiv 1 \,.$$ Then $b^{k \frac{p-1}{2}} \equiv 1$ and hence $$p-1 |k \frac{p-1}{2} \,.$$

It is easy to conclude that $2|k$.

$\endgroup$

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.