And now the repetition period for odd n divides q[n]=2^MultiplicativeOrder[2, n, {1,-1}] - 1 The exponent here always lies between Log[k, n] and (n-1)/2 , with the upper bound being attained only if n is prime. Unlike for the case of rule 60, the period is usually equal to q[n] (and is assumed so for the picture on page 260 ), with the first exception occurring at n=37 .

It appears to be zero only when n is of the form 5 m or 12q , where q is not prime ( q > 5 ).

Induction was to some extent already used in antiquity—for example in Euclid 's proof that there are always larger primes. … It was shown by Raphael Robinson in 1950 that universality is also achieved by the Robinson axioms for reduced arithmetic (usually called Q) in which induction—which cannot be reduced to a finite set of ordinary axioms (see page 1156 )—is replaced by a single weaker axiom.

In the late 1970s it was noted that by evaluating PowerMod[a, n - 1, n]  1 for several random integers a one can with high probability quickly deduce PrimeQ[n] .

↔ a  Quotient[c b , Binomial[c, b]] a  GCD[b, c] ↔ (b c > 0 ∧ a d  b ∧ a e  c ∧ a + c f  b g) a  Floor[b/c] ↔ (a c + d  b ∧ d < c) PrimeQ[a] ↔ (GCD[(a - 1)!