Wednesday 6/23

Euler Phi Function (7.1)

We then defined the summatory function of an arithmetic function f(n) to be
F(n) = ∑ f(d) where the sum is taken over all divisors d of n.

An example led us to the remarkable identity
∑ φ(d) = n where the sum is taken over all divisors d of n.

We proved this identity by partitioning the integers from 1 to n into the classes C_k, such that j is in C_k if and only if (n,j)=k which is equivalent to (n/k,j/k)=1. This last condition shows that there are φ(n/k) integers in the class C_k thus proving the identity.

Sum and Number of Divisors (7.2)

We proved that the summatory function of a multiplicative function is multiplicative, which immediately implied that τ(n) and σ(n) are multiplicative.

This allowed us to prove the following formulas for τ(n) and σ(n)
τ(n)= ∏ (a_i+1)
σ(n)= ∏ (p_i^a_i+1-1)/(p_i-1)
where both products are for i=1..k and n=p₁^a₁p₂^a₂...p_k^a_k is the prime power factorization of n.

Perfect Numbers and Mersenne Primes (7.3)

We showed that n is an even perfect number if and only if it has the form
n=2^m-1(2^m-1)
where (2^m-1) is prime and m>2

A prime is called a Mersenne prime if it has the form 2^m-1, thus even perfect numbers are related to Mersenne primes.

We used the two nice lemmas proved at the end of Thursday June 10th's lecture to show that 2^m-1, is prime only if m is prime. We pointed out that there is a fairly quick way to check wether a number of the form 2^m-1 is a Mersenne Prime, which is called the Lucas-Lehmer test. We also noted that we conjecture that there are infinitely many Mersenne primes, but we have no proof. This is of course equivalent to the conjecture that there are infinitely many even perfect numbers.

Finally, nobody has ever seen an odd perfect number, but we can't prove that none exist.

You can learn a lot more about Mersenne primes here.