Sunday, 26 February 2012

Introduction to Modular Arithmetic and Congruence

Modular arithmetic is an arithmetic system for the integers where the numbers wrap around, like on a clock for example. The numbers start at one, they go round to twelve and then start again at one, this would be an example of modulo 12. However generally in modular arithmetic we start at 0 and go to 11, before starting at 0 again. This means that 7 o'clock would be 6 mod 12 (mod is often used to shorten modulo). In fact because the number line "wraps around" it means that 19 o'clock = 7 o'clock (as you will know if you have used a 24 hour clock), this means that 18 mod 12 = 6 mod 12; because of this a mod m is wrote where a < m.

However it does not have to be just modulo 12, it can be modulo anything (as long at is a positive integer), so let us jump straight into the definition. So that you are aware of the notation I will use a|b means b divides a (this means that b/a is an integer). Let m be a positive integer and let a, b both be integers if m|a-b then a is congruent to b modulo m, wrote mathematically this is: a ≡ b mod m. Make sure you do not think "≡" means equivalent in this case, because it does not!

You can add in modular arithmetic (provided they have the same modulo). Let m be a positive integer and let a, b,c and d be integers if a ≡ b mod m and c ≡ d mod m then a + c  (b+d) mod m. So basically you add the parts preceding the modulo together and then find modulo m of that.
You may also notice that a/m has a remainder of b, this is how we can quickly work out that 19 o'clock is the same as 7 o'clock, or the same as 103 o'clock. You simple divide the number by the modulo and work out the remainder.

An example of why we would use this using our clock as an example is if it is 4 o'clock now, what will the time be in 157 hours? So what we have is 3 mod 12 and 157 mod 12, adding these together we get 160 mod 12, 160/12 = 13 remainder 4. This means that 160 mod 12 = 4 mod 12, so it will be 5 o'clock 157 hours from 4 o'clock.

This should give you an idea of how to do basic addition with congruences, if you do not understand fully read what I have wrote again and then if you still do not understand, post a comment. Now we have the basic principles in place we can begin to go further. Now we will prove that a mod m + b mod m = (a+b) mod m and also how multiplication works in modular arithmetic.

Multiplication between two congruences is just as easy as addition with congruences, I will first provide a definition to you, before proving it. Let m be a positive integer and let a, b,c and d be integers if a ≡ b mod m and c ≡ d mod m then ac  (bd) mod m; this is the same sort of principle as addition. Now to prove them.

First to prove addition:

Now to prove multiplication:

These are the very basics of congruences, but the are integral to modular arithmetic (I mean, think how important addition and multiplication is normally), they are very, very powerful and I will begin to explore them more and more in my upcoming posts. I will prove just one more result as it is pretty easy and uses multiplication.

The proposition is that an ≡ bn mod m is also true provided  ≡ b mod m and n is a positive integer. We will prove this by induction. Let P(n) be be the statement of the proposition, then P(1) is obviously true as we already know that ≡ b mod m. So let us assume that P(n) is true, then we have that an ≡ bn mod m and that ≡ b mod m, multiplying the two of them together (using our proved method) we get a × an ≡ b × bn mod m, this then simplifies to: an+1 ≡ bn+1 mod m, which is P(n+1). Hence P(n) is true for all values of n!

I hope that you like this post and that is helps you. If you did like it then please also like us on Facebook.

Friday, 24 February 2012

Basic Introduction to Topology

Topology is the study of properties that are preserved within objects through twisting, stretching and deformations of that object. However you are not allowed to tear the object, this is key.

In more formal terms, topology is the study of shapes without reference to distance. Or in yet more formal terms it is the study of continuous functions. The study of continuous functions requires the knowledge of range and domain of a function, it studies functions with domains and ranges that make the function continuous. But if you knew that, it is unlikely you would be reading this blog post for absolute beginners as to what topology is!

Also a slight detour from the topic, a continuous function is one where a small change in the input results in a small change in the output too, if it does not follow this then it is said to be discontinuous. Also, just to note, if the inverse function of a continuous function is also continuous it is said to be bicontinuous.

A good way to picture the rules of topology is to picture plasticine, if you have a shape that can be twisted, stretched or deformed in anyway without being torn and put together into a new form then your original shape is topologically equivalent to the new shape you would make.

The reason that topology is useful is that it examines the properties of a shape or region and investigates the properties that are independent of geometric properties the shape or region has. This is the great advantage that topology utilises is that it does not rely on angles or distances, the only thing you need to know is the type of "continuous information" of the object.

Two objects with the same topological properties are said to be homeomorphic. The most well known example of this is that a torus and coffee cup are homeomorphic, they are (topologically speaking) the same shape. As a lot of objects are homeomorphic, it means that if we have a theorem that applies to one object in topology then it also applies to every other object that is homeomorphic to it.
An animation depicting how you
create a coffee cup from a torus.
The point of topology is not to be confusing or just strange, like all Maths it serves some purpose. Be that to merely solve more problems in Maths with a greater ease or to answer problems in the "real world", there is always a purpose to a Mathematical field. And of course, topology is no different. Topology was created to investigate the relationships between objects, and that is exactly what topology does! In fact the origins of topology stemmed from the famed Leonhard Euler when he tried to solve the problem Seven Bridges of Konigsberg, however it truly took off when George Cantor and Henri PoincaréPoincaré (the famous Mathematician) also famously said "mathematics is not the study of the objects themselves, but the relations between them".

Previously unanswerable questions are now possible, because of the aid of topology. Some that you may wonder why anyone ever wanted to know and others that are pretty useful and interesting. This list should show you what I mean by that.

  1. If a coffee is stirred gently then is there always a drop of coffee that finishes in the same place as it started.
  2. It is not possible for the velocity of the wind to be non-zero at every point on Earth. This means that at some point at Earth, this means that at any time at all there is no wind whatsoever.
  3. There are always two points on the equator that are 180° apart in longitude that have the same temperature.
  4. A tennis ball can never be combed in such a way that a cowlick does not appear.
  5. It is always possible to cut two irregular pancakes on a plate in half using just one slice.
And that is it for a basic introduction to topology, I will try to get more posts done on topology in the future, so please stay tuned for that! Be sure to comment any questions, tell your friends about us and like us on Facebook!

Thursday, 23 February 2012

Domain and Range of a Function

When functions are first introduced the terms domain and range of a function may have been briefly mentioned but never explained in full detail. The domain and range of a function are very important in a variety of subjects and you will definitely encounter it at some stage when maths begins to get more in depth.

The notation for a function, f with a domain of X and a range of Y is; f : X  Y. This however, still means nothing to you thought as you do not know what a domain or a range actually is, but once I explain it will all become clear.

The domain of a function is the values that can be put into the function whilst still producing a valid answer, basically this is all the values that x can take on. For example the function, f(x) = 1/x can have any value for x at all, that is not a 0. Mathematically speaking this is "all x ≠ 0". The range of a function are the possible values that can be produced by the function, the "range" of values that y can take on.

To combine everything we have done so far I will use another example. Find the domain and range of f(x) = √(x+3). The domain of this function is everything that makes what is inside the square root greater than or equal to 0, so for x ≥ -3 and the range of the function is everything that a square root can be, so everything positive which is y ≥ 0. Or, to put this mathematically:

And that is all there is to it! Domains and ranges are very easy to work out and deal with and they are very useful when it comes to nearly all areas of maths when graphs are a necessity.

Sunday, 19 February 2012

Pi, Circles and Spheres!

If you have done Maths to a secondary school level at some point you will have encountered circles, spheres and pi. But this information may have passed over your head or you never really went into the details of why these things work.

All circles have the amazing property that their circumference and diameter are related by a ratio, this ratio is known as pi. The interesting property about this number is that it is transcendental, this means that the decimal expansion is non-repeating at any stage and continues on for infinity (or in more formal mathematical terms, there is no polynomial with rational coefficients where π is a root). This property in itself is beautiful.

Pi has in fact been calculated to insane precision, to roughly ten trillion decimal places! This was obviously done using a computer, no human would try to take on this task (I sincerely hope). It is not very necessary to have such an accurate representation of π as if it is calculated to 11 decimal places you can accurately estimate the circumference of any circle that fits inside of the Earth to one millimetre. And if π is represented to 39 decimal places you can estimate the circumference of any circle inside the observable universe to the radius of one hydrogen atom. So 10 trillion decimal places is slightly unnecessary, but that is one way to get your name in the history books.

If you have ever really put any thought to maths you will often come to the thought of "why?". Why do the formulas we are told and have to recite work? And unfortunately, schools very rarely pay attention to the why and just have you use formulae blindly. And this thought is often the case with the area of a circle. We all know that it is πr2 but why is it that way? Like all maths that we use, it has been proved rigorously by many individuals.

Area of Circle:
Here is a rather simple proof of why the area of a circle is so. If we split a circle into an even number of pieces we can rearrange them into a shape that resembles a parallelogram.

All I have done with my circle of radius r is split it into 8 equal sectors and move them around so they interlock in a  parallelogram  like shape. The top of the  parallelogram  like object uses half of the chunks we have used, which is half of the circumference, which is πr. Again from GCSE Maths you may remember that the area of a  parallelogram is defined as base × height. As the sectors of the circle get smaller in width the parallelogram begins to take shape and the top and bottom of the shape begin to flatten out. 

So sectors of width infinitely small will create a perfect parallelogram of height r and base πr, therefore the area of this parallelogram (and thus the circle) is πr2! And that is why we have our concise formula for the area of any circle.

There is also a proof for why a the volume of a sphere is also correct, but this requires some knowledge of calculus. So if you do not know calculus perhaps do not continue reading, however you are more than welcome to and then try to begin to understand calculus.

Volume of Sphere:
A sphere can be thought of as revolving a semi-circle around the x-axis. To do this consider a semi-circle circle with a centre at the origin and a radius of r, this will have an equation:

Any cross-section of the sphere derived by revolve the semi-circle, y, is a circle with a radius of y and an area of πy2! If we slice the sphere up into a infinite number of slices of infinitesimal thickness then the area of each slice is also it's volume (as it has an infinitely small thickness, essentially 0). So this means that the volume of each slice is πy2, if we add the volumes of every single slice then we get the total volume, which is that of a whole sphere!

This means that we are talking about integrating πy2 between r and -r to find the total area, and as area is the same as the volume for each slice the total volume.

And that's all! We have proved that formulae for the area of the circle and volume of a sphere are in fact correct. If there is anything at all that I have done here please do not hesitate to leave a comment and I will respond and explain to the best of my abilities.

Monday, 13 February 2012

Proof by Contradiction: Infinite Prime Numbers

There are many complex and obscure methods of proving that there are infinite prime numbers, but this one is certainly the easiest and it is a demonstration of how unpredictable numbers can be dealt with in an efficient manner, it is also an easy introduction to proofs by contradiction.

First, just to clarify what proof by contradiction actually means:
1.) We assume that what we are trying to prove to be false is in fact true.
2.) If we find a contradiction in our assumed hypothesis that we have assumed then it can not be true. And that means that our assumed hypothesis is false, proving what we originally wanted.

So using this as our basis we are going to assume that there is in actual fact a finite amount of prime numbers, how many there is does not matter just that at some point there are no more prime numbers. If we multiply all of these prime numbers together we will get:

2 × × ... × pn-1 × pn

Where pn is the last prime number and this number is clearly not prime as is has every single prime number as a factor. However if we add 1 to this number then any of the prime numbers that we try to divide it by will give a remainder of 1, this means that it too is prime!
p = 2 × × ... × pn-1 × p+ 1

If this number is also prime it means that our original statement about there being finite prime numbers is incorrect, therefore there are an infinite number of prime numbers!

This took literally two lines of working to prove that there are an infinite number of prime numbers, this massive, beautiful and unfathomable concept was proved so efficiently and beautifully. This is what Maths is about, how concisely you can express complicated statements. Maths is solely about explaining the world around us and where this leads us is some amazing, incomprehensible places.

Friday, 10 February 2012

Proof by Induction: Sum of Odd Numbers

I will introduce an integral part of mathematics in this blog post, proof by induction. It is fundamental to many proofs and is a pretty simple concept to grasp, I will demonstrate how this proof works with a simple example.

The first basis of proving by induction requires some intelligent intuition to our problem. This means that we look at the pattern of what is happening and try to prove this for all values. For the sum of square numbers this goes:

1 = 1

1+3 = 4
1+3+5 = 9
1+3+5+7 = 16

You may have noticed from this that the sum the answers is always a square number. The sum of the first n odd numbers appears to always equal n2, but it just appears that way for the examples that we have given, we do not know that is true for all values, yet.

So our assumption is the sum of the first n odd numbers equals to n2:

1+3+5+...+(2n-1) = n2

This is our assumption, but if we can prove that n+1 odd numbers equals to (n+1)2 then that means it will hold true for the sums of any number of odd numbers. To begin to check this we add n+1th odd number onto both sides of our assumption.

1+3+5+...+(2n-1)+(2n+1) = n2+2n+1

As you can see the right side does factorise to give:

1+3+5+...+(2n-1)+(2n+1) = (n+1)2

Which means that our original assumption was correct! Ergo the sum of the first n odd numbers does equal to nformally in mathematical notation this is:

And that is it for an example of how you use the proof by induction, now it just needs to be put in terms that are applicable for all problems.

Principle of Mathematical Induction

If for each positive integer n we have a statement P(n). If we prove the following two things then the statement is true:
a.) P(1) is true.
b.) For all n, if P(n) is true then P(n+1) is also true. This then means that P(n) is true for all positive integers n.

If that is pretty hard to compute look back to our example, our assumed statement is that P(n) = n2 our assumption is true for P(1), 1 = 12 and we then proved that assuming P(n) is true that P(n+1) is also true. Therefore if P(1) is true, then P(2) is true too, etc.

Stay tuned for my future blog posts where I will utilise mathematical induction to find general formulas or proofs to many things.