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.

Go to the first, previous, next, last section, table of contents.