Monthly Archives: November 2015

MaBloWriMo 29: Equivalence classes are cosets

Posted on November 30, 2015 by Brent

Today will conclude the proof of Lagrange’s Theorem! Recall that we defined subgroups and left cosets, and defined a certain equivalence relation on a group in terms of a subgroup . Today we’re going to show that the equivalence classes … Continue reading →

Posted in algebra, group theory, proof | Tagged classes, cosets, equivalence, groups, Lagrange, MaBloWriMo, proof | Comments Off

MaBloWriMo 28: Equivalence relations are partitions

Posted on November 29, 2015 by Brent

Today we’ll take a brief break from group theory to prove a fact about equivalence relations, namely, that they are the same as partitions. A partition is a pretty intuitive concept: you take a big set, and cut it up … Continue reading →

Posted in algebra, group theory, proof | Tagged equivalence, groups, Lagrange, MaBloWriMo, partition, proof, relation | 2 Comments

MaBloWriMo 27: From subgroups to equivalence relations

Posted on November 28, 2015 by Brent

Again, let be a group and a subgroup of . Then we can define a binary relation on elements of , called , as follows: if and only if there is some such that . That is, for any two … Continue reading →

Posted in algebra, group theory, proof | Tagged equivalence, groups, Lagrange, MaBloWriMo, proof, relation, subgroups | Comments Off

MaBloWriMo 26: Left cosets

Posted on November 27, 2015 by Brent

Let be a group and a subgroup of . Then for each element we can define a left coset of by . That is, is the set we get by combining (on the left) with every element of . For … Continue reading →

Posted in algebra, group theory, proof | Tagged cosets, groups, Lagrange, MaBloWriMo, proof, subgroups | 1 Comment

MaBloWriMo 25: Subgroups

Posted on November 26, 2015 by Brent

So in the remainder of the month, we’ll prove that in any group , the order of each element must evenly divide the order (size) of the group. I said in an earlier post that this is called Lagrange’s Theorem; … Continue reading →

Posted in algebra, group theory, proof | Tagged groups, Lagrange, MaBloWriMo, proof, subgroups | 1 Comment

MaBloWriMo 24: Bezout’s identity

Posted on November 25, 2015 by Brent

A few days ago we made use of Bézout’s Identity, which states that if and have a greatest common divisor , then there exist integers and such that . For completeness, let’s prove it. Consider the set of all linear … Continue reading →

Posted in algebra, arithmetic, modular arithmetic, number theory | Tagged Bezout, combination, divisor, gcd, identity, linear, MaBloWriMo, proof | 2 Comments

MaBloWriMo 23: contradiction!

Posted on November 24, 2015 by Brent

So, where are we? We assumed that is divisible by , but is not prime. We picked a divisor of and used it to define a group , and yesterday we showed that has order in . Today we’ll use … Continue reading →

Posted in algebra, group theory, modular arithmetic, number theory, proof | Tagged contradiction, groups, lehmer, lucas, MaBloWriMo, Mersenne, omega, order, prime, proof, test, X | 5 Comments

MaBloWriMo 22: the order of omega, part II

Posted on November 23, 2015 by Brent

Yesterday, from the assumption that is divisible by , we deduced the equations and which hold in the group . So what do these tell us about the order of ? Well, first of all, the second equation tells us … Continue reading →

Posted in algebra, group theory, modular arithmetic, number theory, proof | Tagged groups, lehmer, lucas, MaBloWriMo, Mersenne, omega, order, prime, proof, test, X | 1 Comment

MaBloWriMo 21: the order of omega, part I

Posted on November 22, 2015 by Brent

Now we’re going to figure out the order of in the group . Remember that we started by assuming that passed the Lucas-Lehmer test, that is, that is divisible by . Remember that we also showed for all . In … Continue reading →

Posted in algebra, group theory, modular arithmetic, number theory, proof | Tagged groups, lehmer, lucas, MaBloWriMo, Mersenne, omega, order, prime, proof, test, X | 2 Comments

MaBloWriMo 20: the group X star

Posted on November 21, 2015 by Brent

So, where are we? Recall that we are assuming (in order to get a contradiction) that is not prime, and we picked a smallish divisor (“smallish” meaning ). We then defined the set as that is, combinations of and where … Continue reading →

Posted in algebra, arithmetic, group theory, number theory | Tagged groups, MaBloWriMo, monoids, X | Comments Off