Category Archives: number theory

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

Finding the prefix length of a decimal expansion

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

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

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