CAI - Exercise sheet 07

Exercise 1: (Carmichael numbers)

(a)

p=(6k+1)(12k+1)(18k+1)

To show is that:
(Subscript[p, k])-1 divises   p-1  for   (Subscript[p, k])=(6 k + 1) ,   (Subscript[p, k])=(12 k + 1) and (Subscript[p, k])=(18 k + 1)

Together[(p-1)/6k]

Together[(p-1)/12k]

Together[(p-1)/18k]

(b)

Clear[FindCarmichaelNumber];
FindCarmichaelNumber[k_]:=Module[{p1,p2,p3},
i=k;
p1=6i+1;
p2=12i+1;
p3=18i+1;
While[Not[PrimeQ[p1]&&PrimeQ[p2]&&PrimeQ[p3]],
i++;
p1=6i+1;
p2=12i+1;
p3=18i+1;
];
p1 p2 p3
]

FindCarmichaelNumber[10^60]//Timing

Exercise 2: (Lucas-Test)

(a)

Clear[LucasTest];
LucasTest[n_]:=Module[{qList,isPrime=False},
qList=FactorInteger[n-1][[All,1]];
For[a=2,a<n,a++,

If[PowerMod[a,n-1,n]==1&&Select[qList,PowerMod[a,((n-1)/(#)),n]≠1&]==qList,isPrime=True;Break[];];
];
isPrime
]/;n≥3 && n∈Integers

Table[{k,LucasTest[k]},{k,3,50}]

(b)

For the test one should have a factorization of n-1   in order to determine all the prime divisors of n-1.  Otherwise one should first use an algorithm to factorize n-1. In this case one could apply it directly  on n to sheck if it is prime or not.  For that reason the algorithm is only for the numbers of a particular for appropriate, particularly of the form  (2^n)+1.