# 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:

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.

# Egyptian Multiplikation

In this post I will introduce egyptian multiplikation to you.

Lets say you want to multiply 15 with 22. You make 2 coulums:                                                      If the right number is even, you simply half it and double the first number.                                 If the second number is odd, you subtract one from it and then half it. The other number gets doubled.                                                                                                                                           You keep on doing this until the second number has reached 1.                                                 Now you take all the rows, where the second number is odd. If you add the first numbers of these rows you get the product:  15*22=30+60+240=330.

Proof:

Let our product be x*y. x*0 is always zero. If y is even, we have x*2*y/2 which is equal to x*y. If y is odd we have x+2*x*(y-1)/2=x+x*(y-1)=x*y. So basically what we did, is that we just took 1 x out of the product. When we continue this algorithm, we eventually get to y=0 since we make y smaller with an integer amount in each step. If y is zero the product is zero, which means that we took the whole number out. Since we only took out numbers when y was odd, we have to add all the x’s from the rows where the y is odd.

That proves the method.