Archive for the ‘Number Theory’ Category

Back around 2000, I found a copy of Neal Koblitz’s text A Course in Number Theory and Cryptography at the Borders bookstore in Bangor, Maine.  I only worked my way through the first chapter, but was fascinated with these ideas.  I found Professor Koblitz’s website which, at the time, had a tutorial section on finite fields and elliptic curve cryptography (this may have been on the Certicom website, I can’t remember now).  I moved on to other forms of digital cryptography, like the Diffie-Hellman Key Exchange and RSA Cryptosystem, but always appreciated Prof. Koblitz’s work.  Recently, we dressed up for Halloween as a number and I chose to be the number 4.  As part of my costume, I drew the addition table for the Galois Field of order 4GF(4)=^{GF(2)[x]}/_{x^2+x+1}, and did a lot of thinking that week about the element a, which was defined as the root of the equation 0=x^2+x+1 in GF(2)

This past week, I decided to look at the mathematics behind Bitcoin and blockchain, and lo and behold, it is Finite Fields and Elliptic Curve Cryptography – I don’t know why it took me so long to find this out, but now I’m excited about these topics.  I am a little skeptical about the current “Bitcoin bubble.”  I’m not sure that these valuations are sustainable, but from everything I’ve read, the blockchain algorithm behind Bitcoin is revolutionary and the mathematics is “supercool.”

Here’s a graph of the equation y=x+1 in GF(2).


Read Full Post »

Fun Stuff

I was reading Kate Nowak’s blog f(t) yesterday and followed a link to the Phillips Exeter Academy website where they’ve posted a pretty amazing collection of problem sets for all levels of math from Pre-algebra to Calculus (and beyond!).

I’ve only just begun to work on some of these, but I’m having a good time so far.

The first one that caught my eye was this:

Can you find a fraction so that the difference between the fraction and its reciprocal is exactly equal to 1?

That is \frac ab - \frac ba=1

The problem gave the example that \frac85 - \frac58 = \frac{39}{40}

D’oh – off by \frac{1}{40}

Then the question asks – Can you find another fraction that gets closer than this?

I approached this from a couple of different ways – first I took the original equation \frac ab - \frac ba=1 and created a common denominator to get \frac{a^2 - b^2}{ab} = 1 or a^2 - b^2 = ab and a^2 - ab - b^2 = 0.

I didn’t pursue this past that point, but did come back to it later.

Next, I broke out the spreadsheet and set it up to take all the numbers from 1-30 and create fractions and their reciprocals from these and subtract them.

Looking at all that, I noticed a few places where the difference between 1 and the \frac ab - \frac ba was smaller than \frac{1}{40}.

This happened for \frac {13}{8} - \frac {8}{13} and \frac {21}{13} - \frac {13}{21}.  Then it was time for class.

The numbers in the fractions that were getting close to 1 had caught my eye yesterday and this morning when I came in, I sat down with it again and saw that they were all consecutive Fibonacci numbers.  So, I made a new spreadsheet with Fibonacci numbers and the fractions and reciprocals and noticed that the difference \frac ab - \frac ba was approaching 1.

At some point yesterday afternoon I went to Wolfram Alpha and typed in a^2 - ab - b^2 = 0 just to see what I would get and it provided a relationship between the two variables that comes from treating one of the variables as a constant so that

a=\frac b2 (1 \pm \sqrt{5})

In other words a and b cannot both be integers!  And of course, some of you may have picked up on this sooner than I did – the number that produces the exact value of 1 is phi – The Golden Ratio.

\phi - \frac {1}{\phi}=1.


Read Full Post »

I’ve been teaching an on-line History of Math course (with a HUM humanities prefix) this term.

The posts for that course are here.

The most recent post was about the French mathematicians of the 17th century – Viète, Mersenne, Fermat, Descartes and Pascal.

French Mathematics of the 17th century


Francois Viète (1540-1603)

Francois Viète was the son of a lawyer in 16th century France.  He is credited with devising a scheme* in which unknown quantities in algebra would be represented by letters that are vowels and constant quantities would be represented by letters that are consonants.  At the time, the Arabic algebra that had been transferred to Europe over the previous 500 years was based on prose writing – everything was described in words.  After Viète’s initial use of letters for unknowns and constants, René Descartes later began to use letters near the end of the alphabet for unknowns (x, y, z) and letters from the beginning of the alphabet for constants (a, b, c).  This practice continues today.

In 1593, the Dutch ambassador to France said to French King Henry IV that a well-known Dutch mathematician had posed a problem that was beyond the capabilities of ANY French mathematician.  Henry IV passed the problem along to Viète and Viète was able to solve it.

Viète began a correspondence with Roomen, the Dutch mathematician who had posed the problem originally and became one of the first internationally recognized French mathematicians.  He worked mainly in trigonometry, astronomy and the theory of equations.

*This link is a paper written by a college student at Rutgers University in New Jersey.  Papers on other subjects by other students in the same course can be found here.

Marin Mersenne (1588-1648)

Marin Mersenne was a French monk best known for his research into prime numbers.  He also did important research into the musical behavior of a vibrating string, showing that the frequency of the vibration was related to the length, tension, cross section and density of the material.

Mersenne primes are prime numbers of the form 2^p-1, where p is a prime number itself.  For example

2^2-1=3 which is prime

2^5-1=31 and so on.

Mersenne was also interested in the work that Copernicus had done on the movement of the heavenly bodies and despite the fact that, as a monk, he was closely tied to the Catholic church, he promoted the heliocentric theory in the 1600′s.

Mersenne was also known as a friend, collaborator and correspondent of many of his contemporaries.  Fermat, Pascal, Descartes, Huygens, Galileo, and Torricelli all corresponded with Mersenne and the exchange of ideas among these scientists promoted the understanding of music, weather and the solar system.

René Descartes (1596-1650)

René Descartes is probably best known for two things.  One is the conclusion “I think therefore I am” (Cogito ergo sum in Latin and Je pense donc je suis in French) and the other is the geometric coordinate system generally known as the Cartesian plane.

Descartes joined the army of Prince Maurice of Nassau in 1619 and was in Bavaria (southern Germany) and Bohemia (Czech Republic) during the beginning of the Thirty Years War.

The importance of the Cartesian Plane is difficult for us to understand today because it is a concept that we are taught at a young age.  Locating objects on a grid by their horizontal and vertical coordinates is so deeply embedded in our culture that it is difficult to imagine a time when it did not exist.

Before Descartes’ grid system took hold, there was Geometry:


and there was Algebra:


(Click on photo for larger view)

…and they were separate fields of endeavor.  The idea that a geometric shape like a parabola could be described by an algebraic formula that expressed the relationship between the curve’s horizontal and vertical components really is a ground-breaking advance.  It is so ground-breaking that once it happened, people began to forget that it hadn’t always been that way.

Once this new method for describing curves was developed, the question of finding the area under a curve was addressed.  This is the general problem of Integral Calculus.  Descartes (among others) saw that, given a polynomial curve y=x^n, the area under the curve could be found by applying the formula A=\frac{x^{n+1}}{n+1}

These were the rudimentary beginnings of the development of the Calculus that would be devised by Isaac Newton and Gottfried Leibniz in the ensuing years.

Fermat (1601-1665)

Pierre Fermat is also mostly remembered for two important ideas – Fermat’s Last Theorem and Fermat’s Little Theorem.  Fermat’s Last Theorem is a simple elegant statement – that Pythagorean Triples are the only whole number triples possible in an equation of the form a^n+b^n=c^n.

Pythagorean Triples are interesting groups of numbers that satisfy the Pythagorean relationship a^2+b^2=c^2.  Triples such as {3,4,5} {6,8,10} {8,15,17} {7, 24, 25} can be found that satisfy the equation.  But – Fermat’s Last Theorem says that if the n in the original equation is any number higher than two, then there are no whole number solutions.

It’s true – but very difficult to prove.  Mathematicians tried for 350 years or so to prove this theorem before it was finally accomplished by Andrew Wiles in 1995.

By the way, you can generate Pythagorean Triples using the following formulas:

Pick two numbers x and y, with x>y




Fermat’s Little Theorem is a useful and interesting piece of number theory that says that any prime number p divides evenly into the number a^{p-1}-1, where a is any number that doesn’t share any factors with p.

Blaise Pascal (1623-1662)

Blaise Pascal was the son of Etienne Pascal, who was a lawyer and amateur mathematician.  Etienne Pascal knew Marin Mersenne and often visited him at his Paris monastery, and when Blaise was a teenager he sometimes accompanied his father on these visits.

Pascal’s first published paper was a work on the conic sections.  He also did research on the composition of the atmosphere and noticed that the atmospheric pressure decreased as the elevation increased.  This led him to believe that beyond the atmosphere there existed a vacuum in which there was no atmospheric pressure.

René Descartes visited Pascal in 1647 and they argued about the existence of a vacuum beyond the atmosphere.  Descartes felt that this was impossible and criticized Pascal, saying that he must have a vacuum in his head.

Pascal is known for the structure of Pascal’s Triangle, which is a series of relationships that had previously been discovered by mathematicians in China and Persia.

Here is Pascal’s version:


Here is the Chinese version:


Here is a version that we often see in textbooks:


Each successive level is created by adding the two numbers above it, so in the 6th row {1,5,10,10,5,1} the 10 is created by adding the 4 and the 6 from the row above it.  These number patterns are actually quite useful in a wide variety of situations.

In raising a binomial to a power like (x+y)^5, the coefficients of each term are the same as the numbers from the 6th row:


These numbers are also related to Discrete Mathematics and Combinatorics which describes how many ways there are to choose something from a series of possibilities.

There was a lot of great mathematics happening in Italy, England, Holland and Germany during the 17th century, but this collection of French mathematicians spanning nearly 100 years produced a tremendous amount of very important mathematical ideas.

The English, Germans and Swiss would make great contributions to mathematics in the 18th century with Newton, Leibniz, the Bernoullis, Euler and others, while the French would still contribute with the works of Laplace, Lagrange and Legendre.

Read Full Post »