Category Archives: number theory

Finding the prefix length of a decimal expansion

Posted on February 2, 2019 by Brent

Remember from my previous post that we’re 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 … Continue reading →

Posted in number theory, pattern | Tagged , , , , | 3 Comments

Finding prefix and repetend length

Posted on January 29, 2019 by Brent

We interrupt your regularly scheduled primality testing to bring you something else fun I’ve been thinking about. It’s well-known that any rational number has a decimal expansion that either terminates, or is eventually periodic—that is, the digits after the decimal … Continue reading →

Posted in number theory, pattern | Tagged , , , | 2 Comments

More on Fermat witnesses and liars

Posted on January 23, 2019 by Brent

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 , , , , , | Comments Off on More on Fermat witnesses and liars

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

Posted on January 18, 2019 by Brent

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

Posted on January 15, 2019 by Brent
Posted in computation, number theory, posts without words, primes | Tagged , , , | 5 Comments

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

Primality testing: recap

Posted on September 10, 2018 by Brent

Whew, this is developing into one of the longest post series I’ve ever written (with quite a few tangents and detours along the way). I thought it would be worth taking a step back for a minute to recap what … Continue reading →

Posted in computation, number theory, primes | Tagged , , , | 2 Comments

Post without words #22

Posted on August 23, 2018 by Brent
Posted in arithmetic, computation, number theory, posts without words | Tagged , , | 8 Comments

Modular exponentiation by repeated squaring

Posted on August 18, 2018 by Brent

In my last post we saw how to quickly compute powers of the form by repeatedly squaring: ; then ; and so on. This is much more efficient than computing powers by repeated multiplication: for example, we need only three … Continue reading →

Posted in computation, number theory | Tagged , , , , , , , | 4 Comments