A Tase of Modular Arithmetic

Modular arithmetic was one of the greatest contributions to mathematics was made by Carl Friedrich Gauss. Gauss was the son of an accountant. Legend has it that by three years old Gauss was pointing out mistakes of his father, and by five, he was managing the accounts. At age seven, Gauss was instructed to add the numbers 1 through 100 as a punishment. He did this by pairing the numbers whose sum was 100 (100 and 0, 99 and 1, 98 and 2, etc.) and multiplied by the number of pairs. Gauss’ method of taking a large amount if number and grouping them into equivalent groups was just the start of modular arithmetic.

Later, Leonard Euler further developed Gauss’ research by coming up with congruence classes. Specifically, he came introduced the following:

X = A (mod N)

where X-A is congruent to N*B where B is some integer. For example, in modulo 4, 11 is congruent to 3 because they both have a residual of 3 (3/4 is 0 remainder 3 and 11/4 is 3 remainder 3). Another way of stating this is 11 is congruent to 3 because they both have the same remainders.

Furthermore, Euler developed addition and multiplication for these groups. He showed that two numbers must be multiplied for example, and then that product should be converted to the right congruence class. For example, let’s multiply 3 and 2 in mod 4.

3×2=6

? = 6 (mod 4)

6 / 4 = 1, remainder 2

2 = 6 (mod 4)

He showed that any two components that were multiplied from different groups should produce the same result every time. Here is another example to model this concept. As stated above, we know that 11 and 3 are equivalent in modulo 4. We also know that 6 is equivalent to 2 in modulo 4 from our previous results. So if we multiply 11 and 6 and we multiply 3 and 2, we should come up with the same results.

11 x 6 = 66

? = 66 (mod 4)

66 / 4 = 16 remainder 2, so

2= 66 (mod 4)

AND

3 x 2 = 6

? = 6 (mod 4)

6 / 4 = 1 remainder 2, so

2 = 6 (mod 4).

Thus, 11 x 6 and 2 x 3 are congruent in modulo 4.

These discoveries were used by many mathematicians and are applicable to a wide variety of mathematical areas such as Cauchy sequences, topology, addition and multiplying large numbers, and much more.

Let’s look at some examples in topology:

In her book, How to Bake Pi, by Eugenia Cheng, she states that a donut is topographically equivalent to a coffee mug. You might ask, in what sense or in what congruence class? The donut is congruent to a coffee mug in the sense that they both have one hole. The coffee mug may seem to have two holes (one as the handle and one where the coffee goes) but the place where the coffee goes is not actually a hole. It is a depression. This process is referred to as a homeomorphic.

Consider a second example of  congruent classes in topology which are homotopic (this means we can take something and shrink it). For example O is congruent to Q because we can take the little tale and shrink it to look like the O. If we take all of the alphabet, we can break it up into three congruence classes: letters with no holes, letters with one hole, and letters with two holes.

Group 1 [ No Holes]: C, E, F, G, H, I, J, K, L, M, N, S, T, U, V, W, X, Y, Z

Group 2 [ 1 Hole]: A, D, O, P, Q, R

Group 3 [ 2 Holes]: B

In conclusion, the discovery of congruence classes and modular arithmetic is very important in mathematics because it allows us to larger group of numbers or items which behave the same and put them into one group and perform operations on these groups such as multiplication and subtraction. We can generalize and make more discoveries with less work in topology, algebra, space, and much more.

 

 

 

Advertisements

Euler and the Seven Bridges of Konigsberg

Euler had a major influence on mathematics in that he developed new ideas and also extended existing ones. For example, he was the first to use e as the base of the natural logarithm, he was the first to come up with the idea of i, he developed with the power series of e… the list goes on. He made developments in a variety of mathematical areas: calculus, number theory, topology and also graph theory. Specifically, he studied and found a solution to the following problem: Is it possible to start at a point and cross over every one of the seven bridges only once and end at the starting point?

Euler

We talked about this problem in class briefly, and it is one I have studied before, but don’t remember it that well. I wanted to re-explore it and go through Euler’s solution step by step:

The first thing we do to solve this problem is to put into a different sort of map. We will represent each island by a vertex. The islands are the two areas which are surrounded by rivers. Consider the picture above. The first island is easy to find; it is directly in the middle. The second is the piece of land directly to the right of it. It is surrounded by rivers on three sides and the fourth side is basically the end of the picture; no river, no land therefore an its an island, I guess. Everything to the right of the island we will label with a vertex and the same for the left side.

So far, we have the following:

1102151259

For our next step, we will draw a line between two vertices for every bridge between the two islands. There is only one bridge that goes from Island A and Island B. There are two bridges we can use to get from Island A the right side and two bridges from Island A to the left side. There is one way to get from Island B to the right side and one way to get from Island B to the left side. When we connect our island with edges, we have the following diagram:

1102151252-1

Next, Euler looked at how many edges or bridges run into each vertex. In number theory, we call this the degree of each vertex.

So the degree of the vertex labeled “Island A” is 5 because there are five edges which are connected to this vertex or five different bridges you could cross if you were standing on Island A. Similarly, the vertex labeled “Island B” has degree 3, the vertex labeled “Right Side” has degree 3, and the vertex labeled “Left Side” has degree 3. One thing that can be noted about the number of degrees for each of the vertices is that it is odd.

We are looking for a path that starts at one vertex, goes through every edge only once and ends at the starting point. Euler called this a circuit, specifically a Euler circuit. Since every vertex has an odd degree, a Euler circuit does not exist according to Euler’s second theorem. In order for a circuit to exist, every vertex must be even.

This is because if hit a vertex, we need to come out the other side. Once we travel on an edge, we can’t travel it again because of the nature of a circuit and because of the nature of this problem; We can only cross every bridge once. So we eventually run into the problem of going to a vertex but running out of edges to take going away from the vertex. For this reason, we need an even number of degrees of in a connected graph in order to have a Euler circuit.