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 $N(x^{n}=a)$ denote the number of solution to $x^{n}=a$ in $\mathbb{F_{p}}$

Lemma: $N(x^{n}=a)=\sum_{\chi^{n}=\epsilon}\chi{(a)}$ where the sum is taken over all characters. In particular, $N(x^{2}=a)=1+(^{a}_{p})$, where $(^{a}_{p})$ is the Legendre symbol.

Question1: Why is it that $N(x^{n}+y^{n}=1)=\sum_{a+b=1}N(x^{n}=a)N(y^{n}=b)$?

Question2: By direct substitution, we should get that $N(x^{2}+y^{2}=1)=p+\sum_{a}(^{a}_{p})+\sum_{b}(^{b}_{p})+\sum_{a+b=1}(^{a}_{p})(^{b}_{p})$, but I am not able to get this because I don't know how to deal with the summation in two variables.

share|cite|improve this question
The premise of question 1 is false. Perhaps you meant $N(x^n+y^n=1)=\sum_{a+b=1} N(x^n)=a N(y^n=b)$. – Alon Amit Mar 3 '12 at 5:52
@Alon: The premise is true, and I can't make any sense out of what you've written. How are $a$ and $b$ outside a summation, for one thing? – anon Mar 3 '12 at 6:01
@anon: The $a$ and $b$ being outside the parentheses is just a typo, I'm sure. Alon's point is rather that if you sum over $a+b = 1$ then you are counting the number of $x$ and $y$ such that $x^n + y^n = 1$, not the number such that $x^n +y^n = a$, as is written in the question. Of course, this is surely just a typo in the question! Regards, – Matt E Mar 3 '12 at 6:36
@MattE: Ah, I see Alon switched the $=$ and $)$ around. That is one permutation I failed to contemplate! I also mentally took the premise to mean what was intended rather than what was written... – anon Mar 3 '12 at 6:43
up vote 4 down vote accepted

Summation in two variables can be simplified when one of the variables is determined by the other one. Here we have $a+b=1$, so we can simply replace $b$ with $1-a$ in the inner expression and sum over all $a\in\mathbb{F}$. However doing this is not always necessary to derive formulas or solutions.

Now for question 1, note that any solution $(x,y)$ to $x^n+y^n=1$ will correspond to $u$ and $v$ such that their sum $u+v=1$; simply take $u=x^n$ and $v=y^n$. So we can take the set of all solutions and partition them into cells, each cell is labelled by $(u,v)$ such that $u+v=1$ and inside each cell are all the $x$ and $y\in\mathbb{F}$ such that $x^n=u$ and $y^n=v$. Since these $x$ and $y$ are independent of each other when $u$ and $v$ are fixed, we conclude tha the number of solutions inside the cell labelled $(u,v)$ is just the product of $N(x^n=u)$ and $N(y^n=v)$. Summing over the available indices gives


For question 2, we use direct substitution:

$$N(x^2+y^2=1)=\sum_{u+v=1}N(x^2=u)N(y^2=v)=\sum_{u+v=1}\left(1+\left(u\over p\right)\right)\left(1+\left(v \over p\right)\right)$$

Multiply out the summand on the RHS and split into multiple summations. Note that if you are summing over $u+v=1$ but the summand only depends on $u$ (respectively, $v$), then we need only note that for any $u$ (resp. $v$) there is exactly one $v$ (resp. $u$) to make $(u,v)$ a solution to $u+v=1$, so we are effectively just summing over all $u\in\mathbb{F}$ in that case!

n.b. I replaced $a$ and $b$ with $u$ and $v$ here.

share|cite|improve this answer
@anon, Thanks for the excellent reply. – Edison Mar 3 '12 at 16:48

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.