1

I would like to find the number of different equivalence classes for $\{(x,y)\mid x^2\equiv y^2$ mod $3 \}$ on $\mathbb{N}^2$. I would just set $x^2$ to $0$ or $1$ or $2$ or $3$. For example mod($0$,$3$)=$0$, mod($1$,$3$)=$1$, mod($4$,$3$)=$1$ which would brings me to two classes. However, the solution seems quite different and I just dont get it:

mod(($3x)^2,3$)=mod($9x^2$,$3$)=$0$

mod(($3x+1)^2,3$)=mod($9x^2$+$6x$+$1$,$3$)=$1$

mod(($3x+2)^2,3$)=mod($9x^2$+$12x$+$4$,$3$)=$1$

May I ask for some assistance. Thank you in advance!

Jacky
  • 87

1 Answers1

1

You are correct. There are two equivalence classes, which are $\{0, 3, 6, 9, \dots \}$ and $\{1, 2, 4, 5, 7, 8, \dots \}$.

I'm not sure how this differs from what you say you read in the solution.

user208259
  • 1,465
  • I mean I just dont understand where the $3x$ comes from... – Jacky Jan 25 '15 at 13:04
  • Any natural number can be written in exactly one of the forms $3x$, $3x + 1$ or $3x + 2$, depending on its remainder after division by $3$. – user208259 Jan 25 '15 at 13:07
  • Im sorry I just dont get it. May I ask you for a simple example... – Jacky Jan 25 '15 at 13:52
  • For example, if $n = 13$, then you can write $13 = 3x + 1$ for $x = 4$. For $n = 15$, you have $15 = 3x$ for $x = 5$. The relevance here is that numbers of the form $3x$ are in one class, and numbers of the form $3x+1$ and $3x+2$ in the other class. – user208259 Jan 25 '15 at 13:59