Partitions of Z

[arfa brane]

This is a dumbass question about modular arithmetic.

If a relation over $$ \mathbb Z $$ is $$ S\; =\; \{ (x,y)\; \mid \; x^4\; \equiv \;y4\; (mod 13) \} $$, how would you describe the equivalence classes?

I've got "S partitions Z[sub]13[/sub] into four equivalence classes, and any element of a partition has that partition as an equivalence class". I also list the subsets of Z[sub]13[/sub], but I think my answer needs something.

Or is it really that straightforward?

 

[rpenner]

The equivalence is not so trivial, For example:
$$12 \equiv -1 (\textrm{mod} \, 13) \; \Rightarrow (-1)^4 \equiv 12^4 = 20736 = 1595 \times 13 + 1 \equiv 1^4 (\textrm{mod} \, 13) $$

Exhaustive examination reveals the partition is into union of various elements of $$\mathbb{Z}_{13}$$.

http://www2.wolframalpha.com/input/?i=Table[Mod[n^4,13],{n,0,12}]

A: [0]
B: [1], [5], [8], [12]
C: [2], [3], [10], [11]
D: [4], [6], [7], [9]

Note that 2[ B] = [C], 2[C] = [D] and 2[D] = (mod 13)
So that B = -8[ B] = 8 [ B] = -[ B] and similarly for [A], [C] and [D].

This follows since $$x^4 -1 = (x^2 + 1)(x^2 - 1) \equiv (x - 5)(x-8)(x-1)(x-12) (\textrm{mod}\, 13)$$. Similarly $$x^4 -1 = (x^2 + 1)(x^2 - 1) \equiv (x - 2)(x-3)(x-1)(x-4) (\textrm{mod}\, 5)$$ but $$x^4 -1 = (x^2 + 1)(x^2 - 1) \equiv (x^2 +1)(x-1)(x-6) (\textrm{mod}\, 7)$$.

 

[arfa brane]

The other thing I should have been clear about in the answer is that Z is partitioned, but then each x can be in Z , and each y a member of Z[sub]13[/sub].

Each x or y in [0][sub]13[/sub] for instance is congruent to any multiple of 13, so each singleton [a], or representative of each equivalence class is congruent to four other integers in Z[sub]13[/sub] excluding {0}. I actually said something arm wavy like "Z is filtered by the equivalence relation into subsets of Z[sub]13[/sub]."

I noted that every element of B is congruent to 1 (mod 13), every element of C congruent to 3 (mod 13), and every element of D congruent to 9 (mod 13).

But Dr Stokes made sure to let it slip that the relation is an ordering of Z, induced by the modulo function and the exponentiation laws.

BTW does that mean (mod 13) is the kernel of the relation?

 

[AlphaNumeric]

The other thing I should have been clear about in the answer is that Z is partitioned, but then each x can be in Z , and each y a member of Z[sub]13[/sub].

Why are you making the distinction between what x and y are in? The equivalence relation is symmetric, you can swap x and y and still get the same results. After all if $$ x^{4} \equiv y^{4} \, mod \, 13$$ then $$ y^{4} \equiv x^{4} \, mod \, 13$$. The modulo equivalence relations mean that if $$ a \equiv b$$ mod n then a = b+kn for some integer k. Clearly then b = a + k'n where k' = -k is also integer. If it's not symmetric then it doesn't necessarily lead to an equivalence class structure as it's just a relation, not an equivalence relation.

BTW does that mean (mod 13) is the kernel of the relation?

The kernel of some relation or map is the set which maps to the 0 of the output set. The kernel of your relations are those x which satisfy $$x^{4} = 0$$ mod 13, ie $$x^{4} = 13k$$ for some integer k. The LHS is non-negative so k must be too. The RHS has a factor of 13 in it, which is prime and thus x must be a multiple of 13, thus x = 13m for all m integer. Done.

 

[arfa brane]

Why are you making the distinction between what x and y are in? The equivalence relation is symmetric, you can swap x and y and still get the same results.

I'm not making a distinction. It's just a for instance argument. But clearly one of x or y can be in Z[sub]13[/sub].
I know it's symmetric, it wouldn't be an equivalence relation otherwise. It has to be reflexive and transitive as well. I know all that.

But yeah, kernels. I wanted to know a bit more about homomorphisms.