2.7.42 Types Tutorial Exercise 10

Testing the first number, we might arbitrarily choose 17 for ‘x’.

1:  17 mod 811749613   2:  17 mod 811749613   1:  533694123 mod 811749613
    .                      811749612              .
                           .

    17 M 811749613 RET     811749612              ^

Since 533694123 is (considerably) different from 1, the number 811749613 must not be prime.

It’s awkward to type the number in twice as we did above. There are various ways to avoid this, and algebraic entry is one. In fact, using a vector mapping operation we can perform several tests at once. Let’s use this method to test the second number.

2:  [17, 42, 100000]               1:  [1 mod 15485863, 1 mod ... ]
1:  15485863                           .
    .

 [17 42 100000] 15485863 RET           V M ' ($$ mod $)^($-1) RET

The result is three ones (modulo ‘n’), so it’s very probable that 15485863 is prime. (In fact, this number is the millionth prime.)

Note that the functions ‘($$^($-1)) mod $’ or ‘$$^($-1) % $’ would have been hopelessly inefficient, since they would have calculated the power using full integer arithmetic.

Calc has a k p command that does primality testing. For small numbers it does an exact test; for large numbers it uses a variant of the Fermat test we used here. You can use k p repeatedly to prove that a large integer is prime with any desired probability.