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

Let $p$ be an odd prime and $\mathrm{gcd}(n, p) = 1.$ Assume that $n = p_1^{a_1} p_2^{a_2} ... p_k ^{a_k}$ is the prime factorization of n. Prove $$\left(\frac{n}{p}\right) = \left(\frac{p_1}{p}\right)^{i_1} \left(\frac{p_2}{p}\right)^{i_2} ... \left(\frac{p_k}{p}\right)^{i_k},$$ where $i_j = 1$ if $a_j$ is odd, and $i_j = 0$ if $a_j$ is even.

share|cite|improve this question
I guess you must be talking of the Jacobi Symbol and, thus, you already know, hopefully, that it is a multiplicative function, so...what exactly is your problem?? – DonAntonio Nov 19 '12 at 17:32
@DonAntonio No need to be seem to be particularly critical today, given some of you other comments. Perhaps that is your style? It's fine to ask for clarification ("what do you know about..." or "where are you stuck"? But it can be demeaning to suggest that a user "ought" to know how to proceed. Why would someone trouble to post a question if one already knows how to solve it? – amWhy Nov 19 '12 at 17:44
i understand it is jacobi symbol problem is getting there from this question and trying to make connection is where I am having difficulty – chuwee Nov 19 '12 at 18:00
I've no idea where did you get the impression I was being sarcastic: not at all. What I can see is that you're particularly sensitive, at least today and at least wrt this thread. It is my personal idea that anyone dealing with the Jacobi symbol learns almost immediately that it is a multiplicative function, so my question stands: whether I am right or not, where is exactly the problem qwith this question? We could save us all this nonsense if askers added some insights, ideas, info to their questions, don't you think? – DonAntonio Nov 19 '12 at 21:48

Hint: The problem seems to be about the Legendre symbol, since the thing at the bottom is an odd prime. It could also be about the Jacobi symbol, since in this case the Legendre symbol and the Jacobi symbol coincide.

How one does it depends on the theorems already available.

To reduce the exponents $a_j$ to the $i_j$, you can use the following fact:

Let $m$ and $p$ be relatively prime, and let $n=a^2 m$, where $a$ and $p$ are relatively prime. Then $n$ is a quadratic residue of $p$ if and only if $m$ is a quadratic residue of $p$. However, this fact is not really needed: see below.

You will also need the following fact: the product of two quadratic residues is a quadratic residue, as is the product of two quadratic non-residues. The product a a QR and a NR is a NR.

From this you can conclude that in general $(ab/p)=(a/p)(b/p)$. (I am using $(m/p)$ for the Legendre symbol.) From the product formula for two terms, one can see that $$(c_1c_2\cdots c_k/p)=(c_1/p)(c_2/p)\cdots(c_k/p).$$ That is very close to the formula you want to prove. Note that in particular, $(c^a/p)=(c/p)^a$. So $(c^a/p)=1$ if $a$ is even, and $(c^a/p)=(c/p)$ if $a$ is odd.

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.