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 $p$ be a prime, then $\mathbb{F}_p$ is a finite field. $\mathbb{A}^2(\mathbb{F}_p)$ is an affine plane. Number of points in $\mathbb{A}^2(\mathbb{F}_p)$ is $p^2$.

I look at a line equation $ax+by=c$ and realise that number of distinct lines equals to number of triples $(a,b,c)$, where $\gcd(a,b,c)=1,\ a,b,c \in [0,p-1]$.

The question is: how to count the triples?

share|improve this question
    
Have you thought about using the fact that you know the number of points on all of these lines? I think it's a good place to start. –  Patrick Da Silva Dec 7 '11 at 6:43
    
You are working in a field, so I don't understand the gcd condition at all? You get a line as long as one of $a,b$ is not zero, because then you can solve that coordinate as a function of the other. The remaining task is then to count how many $(a,b,c)$-combinations give rise to the same line. –  Jyrki Lahtonen Dec 7 '11 at 6:48
    
I must say that Jyrki's comment makes me suspicious too, I didn't think about it enough : the gcd condition doesn't make sense since you cannot speak of divisors in $\mathbb F_p$, non-zero elements are units. You need to think about your question a little more! What is is exactly that you're looking for? Do you want to count the number of lines instead? –  Patrick Da Silva Dec 7 '11 at 7:36
    
There is not only one line ; it would be naive to say that, since for every point (x,y) you can get it to solve a linear equation. It would make non-sense if every such linear equation would do the trick. –  Patrick Da Silva Dec 7 '11 at 7:37
    
@PatrickDaSilva, a line can be represented in the form of a parametric equation $ x = x_0 + at, y = y_0 + bt, t \in \mathbb{F}_p $. There are $p$ lines if $a=0$, $p$ lines if $b=0$ and one line if neither $a$ nor $b$ is not equal to $0$. So there are $2p+1$ lines. Am I correct? –  Sergey Filkin Dec 7 '11 at 7:37
show 3 more comments

3 Answers

up vote 3 down vote accepted

There are exactly $p$ lines that are parallel to the $y$-axis. Each of those is uniquely determined by the point of intersection with the $x$-axis.

All the other lines $y=mx+b$ are uniquley determined by their slope $m$ and intercept $b$. There are $p$ choices for both $m$ and $b$, so altogether we have $p^2$ lines that are not parallel to the $y$-axis.

Thus the answer is $p^2+p$.

share|improve this answer
1  
Another way of arriving at the same conclusion is that you can select the direction of the line in $p+1$ ways (parallel to $y$-axis, or a fixed slope). For each direction, you can partition the space $F_p\times F_p$ into $p$ parallel lines. The answer is then $(p+1)p$. –  Jyrki Lahtonen Dec 7 '11 at 8:13
    
Jyrki, thank you very much, now it's clear for me. –  Sergey Filkin Dec 7 '11 at 13:17
add comment

If you know about projective space, I think the easiest way is to count lines in the projective plane, and then subtract $1$ (for the line "at infinity", which you don't want to count).

By line-point duality, there are as many points as there are lines in $\mathbb{P}^2(\mathbb{F}_p)$ - and there are $p^2+p+1$ points in $\mathbb{P}^2(\mathbb{F}_p)$, because it is the disjoint union of the affine spaces of lesser or equal dimension. Thus there are $p^2+p$ lines in $\mathbb{A}^2(\mathbb{F}_p)$.

(The line-point duality comes from the fact that a line in $\mathbb{P}^2$ is given by a homogeneous equation $aX+bY+cZ=0$. It corresponds to the point $[a,b,c]$ in homogeneous coordinates.)

share|improve this answer
    
Bruno, Thanks for your insightful answer. When I become acquainted with proj space I will remember this. –  Sergey Filkin Dec 7 '11 at 13:15
    
@SergeyFilkin, you are most welcome! :) –  Bruno Joyal Dec 7 '11 at 15:45
add comment

I think what you want to do is to count the number of distinct lines. Your condition with the GCD only works when you are in $\mathbb Z$ or something like that. In $\mathbb F_p$ it's a little different. In the following I consider two lines to be the same if they have the same set of solutions, just to make sure I am clear.

There are $p$ lines of the form $ax = c$ and $a \neq 0$, because the set of solutions for those is just $(a^{-1} c, y)$ with $y$ ranging from $0$ to $p-1$ ; hence $a^{-1}c = A$ for some $A$ and the lines are just $(A,y)$ with $y \in \mathbb F_p$. There is also $p$ lines of the form $by = c$ with $b \neq 0$ for the same reasons. If $a=b=c=0$ then the line is the set of all couples $(x,y)$. If $a=b=0 \neq c$ then you get the empty line. Hence by considering $a=0$ or $b=0$ I got $2p+2$ lines. You distinguish what you consider a line or not in the latter. (You might not want to consider the empty line as a line.)

Assume from now on that $a \neq 0 \neq b$. A line of the form $ax + by = 0$ is always of the form $y = Ax$ with $A = b^{-1}a$. There are $p-1$ such lines, since $A$ can range from $1$ to $p-1$ and clearly all those lines are distinct.

It remains to consider the case where $c \neq 0$. In fact, if $ax + by = c$, then $y = Ax + C$, and by translating we have $y = A(x-A^{-1} C) + C = Ax - C + C = Ax$. Hence adding the constant $c$ gives us $p-1$ new lines for each value of $A$, and they are just translates of the old lines of the form $y=Ax$.

In the end, there are $(2p+2) + p(p-1) = p^2 + p + 2$ lines if you consider the empty set as a line, and $p^2 +p+1$ if you don't.

Hope that helps,

share|improve this answer
    
Sorry if I kept editing. I am thinking about the answer while I am writing it so I corrected stuff along the way. –  Patrick Da Silva Dec 7 '11 at 8:11
    
I did everything explicitly to make sure I was clear, but the right way to think about this is the following : look at a $p \times p$ grid and forget about the cases where the line is the whole grid or the empty set. A line in there is either vertical or of the form $y=ax+b$. There are $p$ vertical lines and $p^2$ choices of $a$ and $b$, and if $y=ax+b$ has the same set of solutions than $y=Ax+B$ then $a=A$ because you can compute slopes, and $b=B$ because $a=A$. Hence you get $p^2$ lines with $y=ax+b$ and $p$ lines with $x=c$, thus getting $p^2 + p$ lines. In the end I think I got it right. –  Patrick Da Silva Dec 7 '11 at 8:16
    
thanks alot. Now it's clear. –  Sergey Filkin Dec 7 '11 at 13:46
1  
You must have counted something twice, because the answer is $p^2+p$... also, why would the empty set ever count as a line? o_O –  Bruno Joyal Dec 7 '11 at 22:22
    
Surely a line = a coset of a one-dimensional subspace? Ok, in projective space we need to modify that in the usual way :-) –  Jyrki Lahtonen Dec 26 '11 at 17:58
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.