Saturday, September 3, 2016

abstract algebra - Congruency and Congruent Classes




so studying for my midterm on Tuesday (intro to abstract algebra). The topics on the exam are Division Algorithm, Divisibility, Prime Numbers, FTA, Congruency, Congruent Classes and very brief introduction to rings.



I was reading a few theorems about Congruency and have a couple of questions.



I want to know what a "congruent class" is. My notes say "the congruence class of a modulo n" is a set:



$ \left\{ \text{all } b \in \mathbb{Z} | b \equiv a \pmod{n} \right\} $ which is also saying
$ \left\{ \text{all } a + kn \in \mathbb{Z} | k \in \mathbb{Z} \right\} $



okay so got that. I just wrote it for some people who might need a refreshed (it is a 3rd undergrad course after all).




So in my notes our professor has a following example:
$\left[ 60 \right]_{17} = \left[ 43\right]_{17}$



1) so the way I figured this out is that to check if they are equivalent, we subtract 60-43 and see if that is a multiple of n = 17. Is this how you can check if they are equal classes? If not, is there a better way to do so?



2) A certain theorem states: Let $n \in \mathbb{Z}_+; a, b \in \mathbb{Z}$ and $gcd(a,n) = d$ then $[a]x=[b]$ has exactly $d$ solutions. My question here is that is x a congruence class or a random integer? What is x and how do I solve for it?



3) Is it true that if we are in $\mathbb{Z}_{12}$ then $[7]x=[11]$ can be rewritten as $ 7x \equiv 11 \pmod{12}$? If so, would finding the solution be similar to solution in this question




Thankyou. I am just very confused about congurency and stuff. I understand the theorems but I am hoping someone would give me an "easy" explanation of what is going on. I still don't know the difference between circle plus and regular plus except that circle plus has to satisfy certain axioms. Am I right?


Answer



There is a much more general definition of congruence classes, but I shall restrict to the one that is sufficient for your course. Given any integer $n$ the only possible remainders that we can get when we divide an integer $a$ by $n$ are $0,1,...,n-1$.
Each set of integers which leave the same remainder on division by $n$ form what is called as a congruence class modulo $n$. All such congruence classes are mutually disjoint since a number can leave only one remainder on division by $n$. Their union is the set of all integers. Each integer in any given congruence class is said to be a representative of the class.



To check whether two integers are in the same class, we check their difference and see if it is divisible by $n$ (since the remainders of these integers cancel out when we divide by $n$). So your approach to your first question is right.



For the second question, $x$ is indeed a congruence class, since otherwise the equation does not make sense. We can define operations on the congruence classes by the correponding operations on their representatives. Its easy to check these are well defined.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...