Category Archives: modular arithmetic

MaBloWriMo 24: Bezout’s identity

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 , , , , , , , | 2 Comments

MaBloWriMo 23: contradiction!

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 , , , , , , , , , , , | 5 Comments

MaBloWriMo 22: the order of omega, part II

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 , , , , , , , , , , | 1 Comment

MaBloWriMo 21: the order of omega, part I

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 , , , , , , , , , , | 2 Comments

MaBloWriMo 16: Recap and outline

We have now established all the facts we will need about groups, and have incidentally just passed the halfway point of MaBloWriMo. This feels like a good time to take a step back and outline what we’ve done so far … Continue reading

Posted in algebra, arithmetic, computation, famous numbers, group theory, iteration, modular arithmetic, number theory, primes | Tagged , , , , , , , , , | 2 Comments

MaBloWriMo 11: Examples of Groups

For reference, here’s the definition of a group again: a set a special element a binary operation on such that is associative, that is, whenever , , and are elements of is the identity for , that is, for every … Continue reading

Posted in algebra, group theory, modular arithmetic, number theory | Tagged , , | 5 Comments

MaBloWriMo 9: omega and its ilk

So far, we have defined a sequence of numbers , and showed that where and . This is a big step: the are defined recursively (that is, each is defined in terms of the previous ), but and give us … Continue reading

Posted in algebra, arithmetic, modular arithmetic, number theory | Tagged , , , , , , | Leave a comment