2
$\begingroup$

Solution: Applying Euler's Criterion, We have
$(a/c) ≡ a^{(c-1)/2} (\mod c) $ Hence if a ≡ b (mod c), then
$(a/c) ≡ a^{(c-1)/2} ≡ b^{(c-1)/2} ≡ (b/c) ≡ (\mod c)$

From here I'm not sure how to show that $(a/c) = (b/c)$
Any suggestions or corrections will be much appreciate it.

  • 1
    Euler only works if c is prime.2012-11-24

1 Answers 1

2

We assume that the symbol $(x/c)$ of the OP denotes the Jacobi symbol.

Recall that if $m$ is odd, and has prime power factorization $p_1^{e_1}\cdots p_k^{e_k}$, then by the definition of the Jacobi symbol, $(x/k)=\prod_{i=1}^k (x/p_i)^{e_i}.\tag{$1$}$ (The symbols on the right are Legendre symbols.)

If $a\equiv b\pmod{m}$, then $a\equiv b\pmod{p_i}$ for every prime divisor $p_i$ of $m$. But then by a standard property of the Legendre symbol, we have $(a/p_i)=(b/p_i)$. The desired result now follows from $(1)$. (For the Legendre symbol, the fact that if $a\equiv b\pmod{p}$ then $(a/p)=(b/p)$ follows trivially from the definition of the Legendre symbol.)