9 - GCDs, Pseudoprimes and Miller's Test

Summary

This chapter contains two investigations of a number-theoretic nature, building on the ideas of Chapter 3. Investigation A is on greatest common divisors (gcds), and B is on pseudoprimes and Miller's test for primality.

A GCDs of random pairs and triples of numbers

Aims of the project

The idea is to find, by theoretical and experimental means, estimates for the probability that a pair of randomly chosen positive integers have no common factor. This is also extended to triples of numbers.

Mathematical ideas used

Elementary ideas of probability are used (e.g., probability of two independent events is the product of their individual probabilities). There are several mathematical arguments given which need to be ‘filled in’ with some details—in fact, this project is more mathematical than computational. The idea is to use mathematical arguments and experiment to determine certain probabilities, such as: given three random integers, what is the probability that each of the three resulting pairs of integers are coprime—that is, have gcd 1?

MATLAB techniques used

The project uses the M-flle gcdiv.m from Chapter 3, which calculates the gcd of two integers. It also requires the writing of some M-files which use loops and conditionals.

The M-flle gcdran.m takes n pairs of ‘random’ numbers, each < 1000, and finds the gcd of each pair, then prints out the percentage of pairs with gcd equal to 1.