3 = +/- 1 ( mod 8 )

Three equals plus or minus one:


We are doing arithmetic modulo 8.


Let x=3


Then x^2 = 9 = 1 ( mod 8 )


So x^2 - 1 = 0


(x-1)(x+1) = 0


So EITHER x-1=0 OR x+1=0


(We used axiom: if ab=0 then a=0 OR b=0. No division by zero here, right??!!?!)


So x = plus or minus 1.


Thus three equals plus or minus one


QEFD!


Dirk(MildManneredMathMan)

I'm not sure the previous post is meant to be taken seriously, but I'll give a serious response: In the integers modulo 8 it is not true that ab = 0 => a=0 or b=0. (4 * 2 = 8 = 0 (mod /images/glasses.gif).

Nice try. (not bad though)....


If ab=0 you don't have a=0 or b=0 unless you have an

"integral domain." In mod 8 you have 2*4=0 but 2 is not o nor is 4. Thus the problem. (Integral domain really just means if

ab=o then a=0 or b=0).

Actually, it's the difference between a modular domain and an integral domain. In base 8, 3*3=11, the only reason 3*3=1 (mod /images/glasses.gif is because the modular domain causes you to drop any values which are not in the "ones" column. Thus 3^5 = 3 (mod /images/glasses.gif, because we simply ignore the 3 in the 64's column and the 6 in the 8's column.

The assumtion that


x^2 - 1 = 0 (mod n)


has always exactly 2 solutions is wrong. A general upper limit to the number of solutions is twice the number of prime factors of n. In the case of n=8, valid solutions are 1, 3, 5 and 7.


As an interesting sidenote: the fact that, for n=pq where p and q are two different odd prime numbers, the above equation always has exactly 4 solutions (two trival 1 and n-1 and two nontrivial) is used in the Shor algorithm to factorize numbers in polynomial time on a quantum computer.

Right. Integers mod 8 do not form an integral domain: ab=0 does not imply a=0 or b=0. It's interesting to see what poker players know. (Also thanks for the info, Ignatius. I know aboput P, NP, #P etc. but not much about quantum poly time.)


Dirk(MildManneredMathMan)