Tag Archives: sum

Fermat’s little Theorem

Fermat’s little theorem: Let p be a prime. Then a^p-a is a multiple of p. In other words a^p is congruent to a mod p.

Proof: We will use Induction. For a=1 we have a^p-a=1^p-1=1-1=0. 0 is a multiple of p.

Now we assume, that the theorem works for a.

Last but not least, we have to show that a+1 works.  We have  (a+1)^p-(a+1)=(a+1)^p-a-1. Now we use the binomial theorem:

Screen Shot 2014-12-20 at 11.52.24 AM

We know that a^p-a is a multiple of p. Every summand of the sum is a multiple of p as well. It follows, that the theorem works for a+1 as well.

This proves the theorem.

Advertisements

Huygens Problem

A few months ago, I stumbled a pond a new problem solving idea. It is called the telescope method. I did know about it but I just used it subconsciously. I want to present a rather easy problem that can be solved with this method. In 1672 Huygens asked Leibnitz to solve this problem, which he did using the same method.

The problem is this: What is the sum off all reciprocals off the triangle numbers.

First we find a formula to express a triangle number. it is well known that this formula is:        (n*(n+1))/2 . Let x be the solution to the problem. Let dn denote the nth triangle number.Screen Shot 2014-08-07 at 5.28.48 PM

 

Now there is a nice trick that you can use:

Screen Shot 2014-08-07 at 5.32.16 PM

 

This has a great benefit for infinite sums. We add this into the equation above and get:

Screen Shot 2014-08-07 at 5.50.21 PM

Lets se what happens to the first few n. 1/1-1/2+1/2-1/3+1/3-14+1/4-1/5. As you can see, everything except the 1/1 cancels itself out. 1/1+(-1/2+1/2)+(-1/3+1/3)+(-14+1/4)+(-1/5…  =1/1+0+0+0+0….

We have 1=1/2x. Simple algebra gives us x=2, which is the solution to the problem.