Monthly Archives: November 2018

The Fermat primality test and the GCD test

Posted on November 18, 2018 by Brent

In my previous post we proved that if shares a nontrivial common factor with , then , and this in turn proves that is not prime (by Fermat’s Little Theorem). But wait a minute, this is silly: if shares a … Continue reading →

Posted in computation, number theory, primes | Tagged , , , | 1 Comment

Making the Fermat primality test deterministic

Posted on November 17, 2018 by Brent

Let’s recall Fermat’s Little Theorem: If is prime and is an integer where , then . Recall that we can turn this directly into a test for primality, called the Fermat primality test, as follows: given some number that we … Continue reading →

Posted in computation, number theory, primes | Tagged , , , | 1 Comment

The wizard’s rational puzzle (solutions, part 2)

Posted on November 9, 2018 by Brent

At long last, here is the solution I had in mind for the Wizard’s rational puzzle. Recall that the goal is to figure out the numerator and denominator of a secret rational number, if all we are allowed to do … Continue reading →

Posted in arithmetic, challenges, logic, programming, puzzles, solutions | Tagged , , , , , , , , , , | Comments Off on The wizard’s rational puzzle (solutions, part 2)