Category Archives: computation

Goldilogs and the n bears

Once upon a time there was a girl named Goldilogs. As she was walking through the woods one day, she came upon a curious, long house. Walking all round it and seeing no one at home, she tried the door … Continue reading

Posted in computation, humor | Tagged , , , , | 1 Comment

Finding the repetend length of a decimal expansion

We’re still trying to find the prefix length and repetend length of the decimal expansion of a fraction , that is, the length of the part before it starts repeating, and the length of the repeating part. In my previous … Continue reading

Posted in computation, group theory, modular arithmetic, number theory, pattern | Tagged , , , , , , | Leave a comment

More on Fermat witnesses and liars

In my previous post I stated, without proof, the following theorem: Theorem: if is composite and there exists at least one Fermat witness for , then at least half of the numbers relatively prime to are Fermat witnesses. Were you … Continue reading

Posted in computation, number theory, primes | Tagged , , , , , | Leave a comment

Fermat witnesses and liars (some words on PWW #24)

Let be a positive integer we want to test for primality, and suppose is some other positive integer with . There are then four possibilities: and could share a common factor. In this case we can find the common factor … Continue reading

Posted in computation, number theory, posts without words, primes | Tagged , , , , | 1 Comment

Post without words #24

Image | Posted on by | Tagged , , , | 5 Comments

The Fermat primality test and the GCD test

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

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