122 6. Integers, Divisors, and Primes
So this algorithm, when repeated sufficiently often, tests primality with
error probability that is much less than the probability of, say, hardware
failure, and therefore it is quite adequate for practical purposes. It is widely
used in programs like Maple and Mathematica and in cryptography.
Suppose that we test a numbernfor primality and find that it is com-
posite. Then we would like to find its prime factorization. It is easy to see
that instead of this, we could ask for less: for a decomposition ofninto the
product of two smaller positive integers,n=ab. If we have a method to
find such a decomposition efficiently, then we can go on and testaandbfor
primality. If they are primes, we have found the prime factorization ofn;
if (say)ais not a prime, we can use our method to find a decomposition of
ainto the product of two smaller integers, etc. Sincenhas at most log 2 n
prime factors (Exercise 6.3.4), we have to repeat this at most log 2 ntimes
(which is less than the number of its bits).
But unfortunately (or fortunately? see Chapter 15 on cryptography), no
efficient method is known to write a composite number as a product of two
smaller integers. It would be very important to find an efficient factorization
method, or to give a mathematical proof that no such method exists; but
we don’t know what the answer is.
6.10.2Show that 561 is a Carmicheal number; more exactly, show that
561 |a^561 −afor every integera. [Hint: Since 561 = 3· 11 ·17, it suffices to
prove that 3|a^561 −a,11|a^561 −1 and 17|a^561 −a. Prove these relations
separately, using the method of the proof of the fact that 341| 2340 −1.]
Review Exercises
6.10.3Prove that ifc = 0 andac|bc, thena|b.6.10.4Prove that ifa|banda|c, thena|b^2 +3c+2bc.6.10.5Prove that every prime larger than 3 gives a remainder of 1 or−1if
divided by 6.
6.10.6Leta>1, andk, n >0. Prove thatak− 1 |an−1 if and only ifk|n.6.10.7Prove that ifa>3, thena,a+ 2, anda+ 4 cannot be all primes. Can
they all be powers of primes?
6.10.8How many integers are there that are not divisible by any prime larger
than 20 and not divisible by the square of any prime?
6.10.9Find the prime factorization of (a) 20
10
; (b) 20!.