# Prove that if a ≡ b (mod c), where c is odd, then (a/c) = (b/c)

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.

-
Euler only works if c is prime. – Thomas Andrews Nov 24 '12 at 6:48

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.)