Discrete Mathematics--modular arithmetic question?

Question

Hi, I have a question regarding equivalence classes in modular arithmetics. I want to know, on page 145 of the book "Discrete Mathematics" by Norman Biggs, is there a typo which causes a proof to be wrong? You can see p. 145 here in Google Books: http://books.google.com/books?id=Mj9gzZMrXDIC&pg=PA145&vq=a&dq=biggs+discrete+mathematics&source=gbs_search_s&cad=0#PPA145,M1

In the paragraph, Biggs is demonstrating a difficulty that arises because each equivalence class can have many names. He's showing how if [x]_m and [x']_m denote the same class, and [y]_m and [y']_m denote the same class, then [x]_m ⊕ [y]_m and [x']_m ⊕ [y']_m denote the same class.

He starts his proof by saying that x ≡ x' (mod m) and y ≡ y' (mod m) is given, I think because they are the same equivalence class. Then he says he will use in his proof theorem 13.1 from the book, which says if x_1 ≡ x_2 (mod m) and y_1 ≡ y_2 (mod m), then x_1 + y_1 ≡ x_2 + y_2 (mod m).

He says because of this theorem, in our problem x + x' ≡ y + y' (mod m); and consequently [x + x']_m = [y + y']_m as required.
However, is this right? I thought we were trying to prove that [x]_m ⊕ [y]_m and [x']_m ⊕ [y']_m denote the same class, which I think would require us to prove that [x + y]_m = [x' + y']_m, and not that [x + x']_m = [y + y']_m, wouldn't it?

Also, I think the book's theorem 13.1 would show that x + y ≡ x' + y' (mod m), wouldn't it, and not x + x' ≡ y + y' (mod m)? And I think that this would prove that that [x + y]_m = [x' + y']_m, which I think is what we want to prove?

So, is Biggs right, or am I right and are these all typos? Thanks!

Answer 1

No, it should be [x+y]. If it says [x+x'] and [y+y'] then they are typos. You are correct.



The best way to realize that it must be wrong is to realize that one case you can have is:



x=x' and y=y'



It makes no sense to prove [x+x']=[2x] is the same as [y+y']=[2y], because there's no guarantee that [2x]=[2y]. So that's definitely a typo.

Answer 2

m = 4k + 3 = 3 (mod 4) Is it a chance that m = x^2 + y^2 for any 2 integers x and y? assume x and y are even. Then x^2 + y^2 = (2k)^2 + (2j)^2 = 4k^2 + 4j^2 = 4(ok^2 + j^2) = 0 (mod 4) ? 3 (mod 4). So m ? x^2 + y^2. assume x and y are elementary. Then x^2 + y^2 = (2k + a million)^2 + (2j + a million)^2 = 4k^2 + 4k + a million + 4j^2 + 4j + a million = 4(ok^2 + ok + j^2 + j) + 2 = 2 (mod 4) ? 3 (mod 4). So m ? x^2 + y^2. assume x is even and y is elementary. Then x^2 + y^2 = (2k)^2 + (2j + a million)^2 = 4k^2 + 4j^2 + 4j + a million = 4(ok^2 + j^2 + j) + a million = a million (mod 4) ? 3 (mod 4). So m ? x^2 + y^2. So there exists no integer ok such that 4k + 3 is the sum of squares.

Answer 3

"However, is this right?"

no, it is not right



"I thought we were trying to prove that [x]_m ⊕ [y]_m and [x']_m ⊕ [y']_m denote the same class, which I think would require us to prove that [x + y]_m = [x' + y']_m, and not that [x + x']_m = [y + y']_m, wouldn't it?"

you are right







A"lso, I think the book's theorem 13.1 would show that x + y ≡ x' + y' (mod m), wouldn't it, and not x + x' ≡ y + y' (mod m)? And I think that this would prove that that [x + y]_m = [x' + y']_m, which I think is what we want to prove?"

yes, the theorem 13.1 shows that x + y ≡ x' + y' (mod m),