Tag Archives: integer

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.

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.

Egyptian Division

After I published a post on Egyptian Multiplication I was asked if an Egyptian Division exists as well. The answer is yes!…

Although I have to admit, that it only works out when the quotient is an integer.

Lets say we want to divide 144 by 24.

Screen Shot 2014-05-30 at 4.57.41 PM

Again we make 2 columns. The left numbers are the powers of 2(in order). The right numbers are multiples of the divisor,which are generated by doubling the number that is over the number. We stop entering numbers when the right number is bigger than the dividend. Then we chose some rows, so that the sum of the right numbers of the rows is equal to the dividend. In this case the row with 48 and 96 since 48+96=144. Then we add the left numbers of those rows and we get the solution.

Proof:                                                                                                                                              Lets say that we are dividing x by y.

We proof, that there always is a combination of rows, so that the sum of the right numbers is equal to the dividend. It is obvious, that the right number is y times as big as the left number in each row (the first row is 1,y and then we double both numbers). If the quotient is not an integer it does not work, so we can say that the quotient is an integer. It is well known, that you can write every integer as a sum of powers of 2 when each power is used once. That means that you can also write the divisor as sum of powers of 2. Multiplying the quotient by y is the same thing as multiplying each of the powers of 2 (whose sum is the divisor) by y and adding them up.It follows, that dividend can be written as a sum of the right numbers. Since the right number is y times as big as the left number in each row by the distributive property The sum of the left numbers is then the quotient.