ExamplesOfProbablePrimes 2006-05-04 17:03:10 2006-11-03 17:28:32 Example probable prime % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here To give an example of a probable prime relative to a base: $4^{341233} - 3^{341233}$ has passed preliminary primality tests relative to bases 2, 3, 5, 7, 11, 13 and 101. Its square root is approximately $2.3362 \cdot 10^{102721}$, which makes a conclusive primality test by trial division in a reasonable time period impractical. To give an example of a probable prime by a pattern: this pattern $$2^2 - 1 = 3, 2^3 - 1 = 7, 2^7 - 1 = 127$$ $$2^{127} - 1 = 170141183460469231731687303715884105727$$ suggests that $2^{170141183460469231731687303715884105727} - 1$ might be a Mersenne prime. But since this is larger than the largest known Mersenne prime $2^{30402457} - 1$ (as of 2005), a Lucas-Lehmer test might take longer than the average human lifetime. On the other hand, $123456789 \cdot 10^{123456789} + 123456789$ is not a probable prime, because even though it is much larger than either of the probable primes given above, it is clearly divisible by $3^2$.