# Question about number of solutions in $\mathbb{F_{p}}$

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.

-
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
To all hands: The typo in the original question pointed out by Matt E is now fixed. Therefore his comment may now look funny. My "fault" :-) – Jyrki Lahtonen Mar 3 '12 at 10:14

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

$$N(x^n+y^n=1)=\sum_{u+v=1}N(x^n=u)N(y^n=v).$$

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.

-
+1 @anon, I fixed the typo from the question that Matt E pointed out. I edited your answer to reflect this change. Feel free to roll it back or whatever. I apologize for this extra trouble. I think that this is for the best. – Jyrki Lahtonen Mar 3 '12 at 10:10
@anon, Thanks for the excellent reply. – Edison Mar 3 '12 at 16:48