Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Euler only works if c is prime. – Thomas Andrews Nov 24 '12 at 6:48
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.