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.

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|improve this question
3  
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
2  
@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
add comment

1 Answer

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

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

share|improve this answer
    
+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
add comment

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.