Hi Dr. Erickson.  Sorry a couple of the Mathematica questions are blank, I'm just not that good at writing code yet.  I know I should have come to your office but I just figured eventually I would get things to work...oops.

Chapter  5

Homework: 1, 2, 5, 7, 8, 9, 10, 11, 12, 14, 15, 17, 18, 19, 21, 23, 24, 25.

(5.1) Use one of the Mathematica implementations of Algorithm 5.2 to determine π(107).

Using the newprimelist command from the Chapter 5 Mathematica notebook, we find that there are 664,579 primes up to 107.

(5.2) Recall from p.24 that "twin primes" are pairs p and p+2 with both numbers prime.  Use newprimelist to count the number of twin prime pairs up to 107.  Make a conjecture as to the number of twin prime pairs up to n.

Using Mathematica, and newprimelist (set equal to twinlist for this application) with the following command, we find that there are 58,980 twin primes up to 107.

Count=0;Do[If[twinlist[[i+1]]-twinlist[[i]]==2,Count=Count+1],{i,1,Length[twinlist]-1}];Print[Count]

(5.5) The "lucky numbers" are defined by a sieving process as follows.  [See book for process] The numbers left by this process are the lucky numbers.  Create a Mathematica procedure to produce the set of lucky numbers up to n.  Make a conjecture as to the proportion of numbers up to n that are lucky numbers.  How does this proportion compare to the limiting proportion in the Prime Number Theorem?

(5.7) Modify the primefactorization procedure so that beyond 2, only odd trial divisors are tested.  Compare the speed of this new version to that of the original by finding the factorization indicated in (5.17).  Can you make further improvements to the primefactorization procedure?

(5.8) Use newprimefactorization to create a procedure that emulates Mathematica's DivisorSigma  command.

This doesn't work yet...but I'm sure learning a lot about Mathematica trying to write this command!  Katiedivisorsigma[k_, n_] := Module[{factor, l}, factor = newprimefactorizatoin[n]; l = Length[factor]; Product[((Part[factor, i])^(k (1 + Part[factor, i])) - 1)/((Part[factor, i]^k) - 1)]].
 

(5.9) What form does a Fermat number have in base 2?

A Fermat number is of the form  .  It is one more than a power of two.  So in base two it will be a string of 2n-1 zeros, sandwiched between 1's.   

(5.10) Prove the following facts about Fermat numbers:

(a) No Fermat number ends in a 1 (in base 10).

Assume Fn≡ 1 mod 10.  Then  Fn-1≡ 0 mod 10, and since 5|10,  Fn-1 ≡ 0 mod 5. This means that 5|.  Thus no Fermat number can be congruent to 1 mod 10.

(b) No Fermat numbers except 3 and 5 are divisible by 3 or 5.

I ran across a theorem during my capstone studies that states:  "Let m and n be distinct non-negative integers.  Then the Fermat numbers Fm and Fn are relatively prime."  (We also show this in 5.11)  So all Fermat numbers are relatively prime.  Since F0=3 and F1=5, no other Fermat numbers are divisible by 3 or 5.

(5.11)

(a) Prove that the Fermat numbers {Fn}=F0F1...Fn-1+2, n≥1. 

First we show Fn=F0F1...Fn-1+2, n≥1 holds for n=1.  When n=1, F1=3+2=5=Fo+2.  Now assume that this relations shows for n,  so that  FoF1F2...Fn-1=Fn-2.  Now, let's show that this holds for n+1. 

FoF1F2...Fn-1 Fn = ( FoF1F2...Fn-1)Fn

= (Fn-2)Fn

= (-1)( +1)

= ()2-1

= -2

= Fn+1-2

Since the relation holds for n+1, by induction it holds for n.  Thus the Fermat numbers satisfy this relation.

(b) Prove that every two different Fermat numbers are relatively prime.

    Let Fm, Fn be two Fermat numbers, where m<n.  From part (a) we know that FoF1F2...Fn-1=Fn-2.  Assume b divides both Fm and Fn.  Then we know b|( Fn-FoF1F2...Fm...Fn-1)=2.  So b=1 or b=2.  But since Fm and Fn are odd, b cannot be 2.  Thus b=1 and we know gcd(Fm, Fn)=1.  Implying every two different Fermat numbers are relatively prime.

(c) Show that the result (b) implies that there are infinitely many prime numbers.

Assume there are a finite number of prime numbers.  Then for every p, prime there is at most one Fn such that p|Fn.  Thus since there is a finite number of primes there can only be a finite number of Fermat numbers (since Fermat numbers are relatively prime).  But there are an infinite number of Fermat numbers, a contradiction!  Thus there must be infinitely many prime numbers.

(5.12) Find an even number n such that there exists no odd number m with Φ(m)=Φ(n).

 I haven't found it yet but it must be greater than 68.

(5.14)

(a) Use Lucas' theorem and Mathematica to find prime factors of the Fermat numbers F9 and F11.

I'm not even sure if my code would've worked, but it was taking so long, that I figured it was wrong.  So I haven't factored these yet.

(b) Similarly, find factors of F12 and F13 (thereby showing that these numbers are composite).

A factor of F12 is  67280421310721.

A factor of F13 is 4385858440954921.

(5.15) Use Pepin's test to show that the Fermat number F8 is composite.

pepinstest[n_] := Module[{m, a},
m = fermatnumber[n];
a = 3;
Do[a = Mod[a^2, m], {2^n - 1}];
If[Mod[a, m] == -1, Return["prime"], Return["composite"]]]

In[40]:=
pepinstest[8] //Timing

Out[40]=
{0.01 Second,composite}

(5.17) What form does a Mersenne number have in base 12?

Since a Mersenne number is one less than a power of two, in base two a Mersenne number would be a string of n 1's (Where the Mersenne number is Mn). 

(5.18) Prove that 3 is the only number that is both a Fermat number and a Mersenne number.

To be a Fermat number and a Mersenne number we would need:

(5.19) Prove that if ab-1 is prime, then a=2 and b is a prime.

Assume ab-1 is a prime and let b=pq (where p is prime).  We can factor ab-1 = (ap-1)(ap(q-1)+ ap(q-2)+ ...+ap+1).  Assume either p or q is 1.  let q=1.  Then (ap(q-1)+ ap(q-2)+ ...+ap+1) is one and p is prime.  If p=1, we have a-1=1.  So a=2.  Thus if ap-1 is prime a=2, and b is a prime.

(5.21) Prove Theorem 5.13.

Theorem 5.13 states:  The number Mn are pseudoprimes for the base 2 or are prime numbers.  (That is, Mn|2Mn -1, for all n≥1).  To Prove this we need to show that the Mersenne numbers satisfy this condition: Mn|2Mn -1, for all n≥1.  Then we will have that Mn are pseudoprimes for the base 2 or are prime numbers.

(5.23) Determine prime certificates for 1999, 7368787, and 2038074743.

In[59]:=primecertificate[1999]
Out[59]={1999,3,{2,3,37}}

In[60]:=primecertificate[7368787]

Out[60]={7368787,2,{2,3,17,23,349}}

In[61]:=primecertificate[2038074743]

Out[61]={2038074743,5,{2,11,67,211,6553}}

(5.24) Write a Mathematica procedure to list the composite numbers less than 1000, for which the newprimetest procedure fails  (i.e. numbers which are pseudoprimes to the bases 2, 3 and 5).

(5.25) Use Algorithm 5.17 (or largeprime) to find a prime number with at least 200 digits.

Using largeprime

In[75]:=largeprime[200]//Timing

Out[75]={143.957 Second,\
164339001343560786815086528637546160309448142888537067679494254135167719017916\
271044376998101872660795780959438474931585165383559462355518372881576431555382\
749158853444861926664441061193295780286390880253}

When I copied this number into Microsoft Word and used "tools"  to count the characters, it returned the that there are 204 characters (digits) in this number.