Lecture 8

May 17

The sum over all positive divisors notation. The equation defines the number theoretic function F(n) in terms of the number theoretic function f(d) by summimg f(d) over all positive divisors d of n .

Example 1

Let f(n)=1, then F(1)=f(1)=1, F(2)=f(1)+f(2)=1+1=2, F(3)=f(1)+f(3)=1+1=2, F(4)=f(1)+f(2)+f(4)=1+1+1=3, F(5)=f(1)+f(5)=1+1=2, F(6)=f(1)+f(2)+f(3)+f(4)=1+1+1+1=4, F(7)=f(1)+f(7)=1+1=2, F(8)=f(1)+f(2)+f(4)+f(8)=1+1+1+1=4, F(9)=f(1)+f(3)+f(9)=1+1+1=3, F(10)=f(1)+f(2)+f(5)+f(10)=1+1+1+1=4.

It looks F(n)= =d(n) the number of divisors functiion.

Example 2

Let f(n)=n , then F(1)=f(1)=1, F(2)=f(1)+f(2)=1+2=3, F(3)=f(1)+f(3)=1+3=4, F(4)=f(1)+f(2)+f(4)=1+2+4=7, F(5)=f(1)+f(5)=1+5=6, F(6)=f(1)+f(2)+f(3)+f(6)=1+2+3+6=12, F(7)=f(1)+f(7)=1+7=8, F(8)=f(1)+f(2)+f(4)+f(8)=1+2+4+8=15, F(9)=f(1)+f(3)+f(9)=1+3+9=13, F(10)=f(1)+f(10)=1+10=11, F(12)=f(1)+f(2)+f(3)+f(4)+f(6)+f(12)=1+2+3+4+6+12=28, F(13)=f(1)+f(13)=1+13.

It looks like this F(n)= the sum of divisors function.

sum over divisors function is multiplicative theorem

Theorem: The number theoretic function is multiplicative if the number theoretic function f(n) is multiplicative.

Proof: Let a and b be relatively prime , so that gcd(a,b)=1. Let a have positive divisors d[1],d[2],...,d[r] . Let b have positive divisors e[1],e[2],...,e[s]. Then F(a)*F(b)=( f(d[1])+f(d[2])+...+f(d[r]) ) * ( f(e[1])+f(e[2])+...+f(e[s]) )

= f(d[1])*f(e[1]) + f(d[1])*f(e[2]) + ... +f(d[1])*f(e[s])

+f(d[2])*f(e[1]) + f(d[2])*f(e[2]) + ... + f(d[2])*f(e[s])

+...

+f(d[r])*f(e[1]) + f(d[r])*f(e[2]) + ... + f(d[r])*f(e[s]) .

There were r*s terms in the above sum. Now consider F(a*b) =

f(d[1]*e[1])+f(d[1]*e[2])+...+f(d[1]*e[s])

+f(d[2]*e[1])+f(d[2]*e[2])+...+f(d[2]*e[s])

+...

+f(d[r]*e[1])+f(d[r]*e[2])+...+f(d[r]*e[s]) .

Now use the condition that a and b are relatively prime to show that gcd(d[i],e[j])=1 . Let d be a divisor of a, then integer u exixts such that a=d*u . Let e be a divisor of b, then integer v exists such that b=e*v . Since gcd(a,b)=1, integers x and y exist such that x*a+y*b=1 . Now replace a by d*u and b by e*v in this equation. We have x*(d*u) + y*(e*v)=1. Rearrange this equation as (x*u)*d+(y*v)*e=1 . We now have a linear combination of d and e that is equal to 1. This shows us that the gcd(d,e) is at most 1. Since it must be at least 1, it can only be 1. Therefore gcd(d,e)=1 . This means that every term such as f(d[i]*e[j]) in the above sum may be exoanded into f(d[i])*f(e[j]) because f was multiplicative. Thus every term in the above sum is equal to the corresponding term in the previous sum. Therefore F(a)*F(b)=F(a*b) for all

a and b relatively prime. Therefore F is multiplicative.

Example:

Let f(n)=n^k . Then f(a*b)=(a*b)^k. f(a)*f(b)=a^k*b^k. Recall (a*b)^k=a^k*b^k . Therefore f(n) is multiplicative. Actually we have shown that f(n) is more than multiplicative, since we did not need to assume that gcd(a,b)=1. Such functions are called totally multiplicative. Then by our theorem is multiplicative.

In Maple this function is in the numtheory package and is written sigma[k](n)

> with(numtheory):

Warning, new definition for order

> sigma[2](6);

Check: 1^2+2^2+3^2+6^2=1+4+9+36=50

Perfect number

A perfect number n is a positive integer n such that . This says that the sum of the proper divisors of n equals n. A proper divisor is a positive integer that divides n, but is not equal to n. Note we may rewrite the defining equation as by adding n to each side.

Examples:

6=1+2+3

28=1+2+4+7+14

> k:=0:
for i to 10000 do
if sigma(i)-i=i then
k := k+1;
pf[k] := i;
fi;
od:
smallest_perfect_numbers := [seq(pf[i],i=1..k)];

> ifactor(smallest_perfect_numbers);

abundant number

An abundant number is a positive integer n, such that the sum of its proper divisors is greater than itself. That is n abundant if (n)-n>n , or if (n)>2*n .

Examples:

12, because 1+2+3+4+6=16>12

18, because 1+2+3+6+9=21>18

deficient number

A deficient number is a positive integer n, such that the sum of its proper divisors is less than itself. This is n is deficient if , or if (n)<2*n .

Examples:

1, because it does not have any positive proper divisors. The divisor 1 is equal to 1.

2, because 1<2

4, because 1+2=3<4

Every positive integer is either deficient, perfert, or abundant.

amicable pairs

Two positive integers a and b are said to be an amicable pair if the sum of the positive proper divisors of a equals b, and the sum of the positive proper divisors of b equals a. Using this becomes and .

Find them all by brute force search up to a bound B.

> B := 2000;

> B := 2000;
k := 0:
for i to B do
t := sigma(i)-i;
if i<t then
u := sigma(t)-t;
if u=i then
k := k+1;
ap[k] := [i,t]
fi;
fi;
od:
all_amicable_pairs := [seq(ap[i],i=1..k)];

Perfect number theorems

Euclid's perfect number theorem

If 2^k-1 is a prime number, then n= 2^(k-1)*(2^k-1) is a perfect number.

Proof: 2^k-1 is an odd number for k>1 , so it is relatively prime to 2^(k-1) , which only contains the prime 2 in its prime power factorization. Since is multiplcative and since gcd(2^(k-1),2^k-1)=1 we have: (n)=

(2^(k-1)*(2^k-1))

= (2^(k-1))* (2^k-1)

=(2^((k-1)+1)-1)/(2-1) * (1+ 2^k-1)

= (2^k-1) * 2^k .

Now we compute 2*n=2*2^(k-1)*(2^k-1)=2^k*(2^k-1) , and this is equal to (n) . Therefore n is a perfect number.

Euler's even perfect number theorem states that:

Theorem: Every even perfect number is of the form 2^(k-1)*(2^k-1), where 2^k-1 is prime.

Proof: Let n be an even perfect number. Then n=2^r*q , where r>=1, and q is an odd integer. Since is multiplicative, we have (n)= (2^r*q)= (2^r)* (q)=(2^(r+1)-1)/(2-1)* (q)=(2^(r+1)-1)* (q).

Since n is perfect, we also have (n)=2*n=2*2^r*q=2^(r+1)*q.

Therefore (2^(r+1)-1)* (q)=2^(r+1)*q. Divide both sides by 2^(r+1)* (q) to find that:

(2^(r+1)-1)/2^(r+1)=q/ (q) .

The fraction on the right may not be in lowest terms , so let d=gcd(q, (q)).

Then we have that q=d*(2^(r+1)-1)=d*2^(r+1)-d , and that (q)=d*2^(r+1). So (q)=q+d. But 2^(r+1)-1>1 , since r>=1, so d is a proper divisor of q. If d>1 then (q)>=1+d+q , but (q) is only q+d. Therefore d=1. Thus (q)=q+1 . The only choice is that q is prime . We also have q=2^(r+1)-1 . Now the theorem is true after choosing k=r+1.

odd perfect numbers?

Are there any odd perfect numbers?

If there are then the smallest one has to have more than 300 digits and have at least 8 distinct prime factors. See:

http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Perfect_numbers.html

Mersenne primes

We have just seen that all even perfect numbers contain one odd prime factor of the form q=2^k-1 . Numbers of the form 2^k-1 are called Mersenne numbers, and prime numbers of the form 2^k-1 are called Mersenne primes.

Which Mersenne numbers are Mersenne primes?

Let's use Maple to find them for k up to a bound B.

> B := 100;
k := 0:
for i to B do
m := 2^i-1;
if isprime(m) then
k := k+1;
Me[k] := i;
Mp[k] := m;
fi;
od:
k;
Mersenne_exponents := [seq(Me[i],i=1..k)];
Mersenne_primes := [seq(Mp[i],i=1..k)];

It looks like the Mersenne exponent k , which creates the Mersenne prime 2^k-1 must also be a prime number. Can we prove it?

Theorem: If k is composite then 2^k-1 is composite.

Proof: Let k=m*n, where both m>1 and n>1. be a partial factorization of the composite number k. Consider the polynomial x^n-1. We divide it by x-1 and find a quotient polynomial

q=x^(n-1)+x^(n-2)+...+x+1. We can also verify this by multiplying (x-1)*q=x^n + x^(n-1) + ... + x - x^(n-1)-x^(n-2)-...-x-1=x^n-1 , because all the middle terms cancel. Now write 2^k=2^(m*n) = (2^m)^n . We just choose x=2^m This gives us a factorization of

2^k-1=(2^m-1)*( (2^m)^(n-1) + (2^m)^(n-2) + .... + 2^m + 1) . Since m>=2, 2^m-1>=3 and the other factor is greater than 1 also. So both factors are greater than 1, so we have a non-trival factorization of 2^k-1. Therefore 2^k-1 is composite.

Lucas Lehmer test for Mersenne primes

Let p be a prime > 2. Define n=2^p-1 . Also let s[1]=4, s[k+1] =s[k]^2-2 (mod n), for k>=1. Then n is prime if and only if s[p-1]=0 (mod n) .

Proof: See

Title: Algorithmic number theory, Vol. 1, pages 273-275

Authors: Eric Bach and Jeffery Shallit

Publisher: the MIT press

We can write the above Lucas Lehmer test in Maple as follows:

> #read Lucas_Lehmer;

> Lucas_Lehmer := proc (p) local s, n, i; if p = 2 then true elif isprime(p) then s := 4; n := 2^p-1; for i to p-2 do s := `mod`(s^2-2,n) od; if s = 0 then true else false fi else false fi end;

> Lucas_Lehmer(7);

> ifactor(2^7-1);

> Lucas_Lehmer(11);

> ifactor(2^11-1);

Are there infinitely many Mersenne primes? still unknown

See :

http://www.utm.edu/research/primes/mersenne.shtml

Theorem: If k=a*b and a is odd , a>1, and b>1, then 2^b+1 divides 2^k+1.

Proof: Consider the polynomial x^a+1 . Divide it by x+1 and we compute the quotient polynomial

q = x^(a-1) - x^(a-2) + x^(a-3)- ... -x+1. This works because a was an odd number. We can also check it by multiplication we find (x+1)*(x^(a-1)-....-x+1) =x^a-x^(a-1)+x^(a-2)-...-x^2+x + x^(a-1) -x^(a-2)+x^(a-3)-...-x+1=x^a+1. Now Let x=2^b and we have our non-trivial factorizatiion of 2^k+1=(2^b+1) *((2^b)^(a-1) - (2^b)^(a-2) + ... - 2^b+1). Since b>=2 2^b+1>=5 and since a>=3 the other factor is >= (2^2)^2-2^2+1=13. Therefore we have a non-trivial factorization.

Because of the above theorem 2^k+1 could be a prime only if k=2^m .

Fermat numbers and Fermat primes

A Fermat number is of the form n=2^(2^m)+1 for some non-negative integer m. A Fermat prime is a Fermat number that is also a prime number.

Examples: 2^(2^0)+1=2^1+1=2+1=3 is a Fermat prime

2^(2^1)+1=2^2+1=4+1=5 is a Fermat prime

2^(2^2)+1=2^4+1=16+1=17 is a Fermat prime

2^(2^3)+1=2^8+1=256+1=257 is a Fermat prime

2^(2^4)+1=2^16+1=65536+1=65537 is a Fermat prime

2^(2^5)+1=2^32+1= +1= =641*6700417 is a Fermat number

> with(numtheory);

Warning, new definition for order

> for i from 0 to 6 do f[i]:=fermat(i); ff[i]:=ifactor(f[i]); od;

No other Fermat primes have ever been found. Gauss proved that we could construct the regular polygon with a prime p number of sides if p if and only if p was a Fermat prime. Here construct means that we are only allowed to use a straight edge and a compass. This also means that we could express the coordinates in terms of nested square roots of rational expressions of rational numbers.

For example to construct the regular 17-gon inside the unit circle we would need to express the coordinates of 2 vertices in terms of nested square roots. One vertex is easy just choose (x,y)=(1,0) . The coordinates of the nearest vertex in the first quadrant would be (x,y)=(cos(2*Pi/17), sin(2*Pi/17) ) .

We just need to express cos(2*Pi/17) and sin(2*Pi/17) in terms of nested square roots. Gauss did this:

The answer is:

> c17 := 1/16*sqrt(34-2*sqrt(17))-1/16+1/16*sqrt(17)+1/16*sqrt(68+12*sqrt(17)-6*sqrt(34-2*sqrt(17))-2*sqrt(34-2*sqrt(17))*sqrt(17));

> s17;

> s17 := 1/16*sqrt(136-8*sqrt(17)+8*sqrt(34-2*sqrt(17))-2*sqrt(34-2*sqrt(17))*sqrt(68+12*sqrt(17)-6*sqrt(34-2*sqrt(17))-2*sqrt(34-2*sqrt(17))*sqrt(17))+2*sqrt(68+12*sqrt(17)-6*sqrt(34-2*sqrt(17))-2*sqrt(34-2*sqrt(17))*sqrt(17))-2*sqrt(68+12*sqrt(17)-6*sqrt(34-2*sqrt(17))-2*sqrt(34-2*sqrt(17))*sqrt(17))*sqrt(17));

Check

> Digits := 60;

> evalf(c17);

> evalf(cos(2*Pi/17));

> evalf(s17);

> evalf(sin(2*Pi/17));