MATH3170: Number Theory

For \((a):\) If \(a \equiv b\pmod{p},\) then \(x^2\equiv a\pmod{p}\) and \(x^2\equiv b\pmod{p}\) have the same solution or both have no solution. In either case \((a/p) =(b/p).\)

For \((b):\) There is clearly a solution to \(x^2\equiv a^2\pmod{p};\) in fact, the integer \(a\) satisfies it. Thus \(a^2\) is a quadratic residue of \(p,\) and so \((a^2/p) = 1.\)

For \((c):\) This is just a restatement of the previous corollary.

For \((d):\) Using \((c),\) we have

If \((ab/p) \neq (a/p)(b/p),\) then since the Legendre symbol takes the values only \(\pm 1,\) we would have \(1\equiv -1\pmod{p},\) which implies that \(p = 2,\) a contradiction. Thus \((ab/p) = (a/p)(b/p).\)

For \((e):\) Note that \((1/p) = 1\) since \(1^2\equiv 1\pmod{p}\) and \(1\) is a quadratic residue of \(p.\) If we let \(a = -1\) in part \((c),\) then we have \((-1/p) =(-1)^{(p-1)/2)}\) which is the desired result.

As is always the case, we suppose that there are only finitely many primes of the form \(4k + 1,\) say \(p_1, p_2,..., p_n\) and consider

Since \(N\) is odd, there is an odd prime \(p\) that divides \(N.\) So

which says that \((-1/p) = 1.\) Since

it must be the case, that \(p \equiv 1\pmod{4},\) or rather, \(p\) is of the form \(4k + 1\) and so \(p = p_i\) for some \(i.\) But

a contradiction. Thus there are infinitely many primes of the form \(4k +1.\)

Let \(r\) be a primitive root of \(p.\) Note that the powers \(r, r^2, r^3,...,r^{p-1}\) are just a permutation of \(1, 2, 3,..., p-1,\) since they are incongruent modulo \(p.\) So for any a between \(1\) and \(p-1,\) inclusive, we have that there is a unique \(k\) with \(1\leq k\leq p- 1,\) such that

Now by Euler's Criterion, we have

where \(r^{(p-1)/2} \equiv -1\pmod{p}\) by Euler's Criterion since \(r\) is a primitive root modulo \(p.\) Hence \((a/p) = (-1)^k\) since \((a/p)\) is either \(1\) or \(-1.\) Thus

since \(p-1\) is even.

Since \((a/p) \equiv (-1)^k\) in the above proof of the Theorem.