Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
Euler only works if c is prime. –  Thomas Andrews Nov 24 '12 at 6:48

1 Answer 1

up vote 1 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|improve this answer

Your Answer

 
discard

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.