Meta
Categories
 algebra (46)
 arithmetic (76)
 books (30)
 calculus (7)
 challenges (56)
 combinatorics (21)
 complex numbers (6)
 computation (78)
 convergence (9)
 counting (34)
 famous numbers (48)
 fibonacci (18)
 fractals (13)
 games (34)
 geometry (71)
 golden ratio (8)
 group theory (28)
 humor (7)
 induction (7)
 infinity (19)
 iteration (24)
 links (76)
 logic (9)
 meta (43)
 modular arithmetic (30)
 number theory (105)
 open problems (11)
 paradox (1)
 pascal's triangle (8)
 pattern (98)
 people (21)
 pictures (71)
 posts without words (34)
 primes (55)
 probability (6)
 programming (20)
 proof (83)
 puzzles (18)
 recursion (16)
 review (21)
 sequences (28)
 solutions (30)
 teaching (14)
 trig (3)
 Uncategorized (6)
 video (19)
Archives
 May 2019 (3)
 April 2019 (2)
 March 2019 (3)
 February 2019 (3)
 January 2019 (4)
 November 2018 (3)
 October 2018 (4)
 September 2018 (4)
 August 2018 (6)
 July 2018 (2)
 June 2018 (5)
 May 2018 (3)
 April 2018 (5)
 March 2018 (4)
 February 2018 (3)
 January 2018 (4)
 December 2017 (3)
 November 2017 (3)
 October 2017 (1)
 September 2017 (1)
 July 2017 (4)
 June 2017 (4)
 May 2017 (9)
 April 2017 (7)
 March 2017 (5)
 February 2017 (4)
 January 2017 (3)
 December 2016 (4)
 November 2016 (6)
 October 2016 (6)
 September 2016 (2)
 August 2016 (5)
 July 2016 (2)
 June 2016 (4)
 May 2016 (4)
 April 2016 (2)
 March 2016 (3)
 February 2016 (9)
 January 2016 (8)
 December 2015 (5)
 November 2015 (29)
 August 2015 (3)
 June 2015 (2)
 April 2015 (1)
 May 2014 (1)
 December 2013 (1)
 October 2013 (1)
 July 2013 (1)
 June 2013 (1)
 May 2013 (1)
 April 2013 (3)
 March 2013 (3)
 February 2013 (2)
 January 2013 (5)
 December 2012 (3)
 November 2012 (4)
 October 2012 (5)
 September 2012 (1)
 August 2012 (4)
 July 2012 (1)
 June 2012 (6)
 May 2012 (2)
 April 2012 (3)
 March 2012 (1)
 February 2012 (4)
 January 2012 (5)
 December 2011 (1)
 November 2011 (7)
 October 2011 (4)
 September 2011 (6)
 July 2011 (2)
 June 2011 (4)
 May 2011 (5)
 April 2011 (2)
 March 2011 (4)
 February 2011 (1)
 January 2011 (1)
 December 2010 (1)
 November 2010 (4)
 October 2010 (2)
 September 2010 (1)
 August 2010 (1)
 July 2010 (1)
 June 2010 (2)
 May 2010 (3)
 April 2010 (1)
 February 2010 (6)
 January 2010 (3)
 December 2009 (8)
 November 2009 (7)
 October 2009 (3)
 September 2009 (3)
 August 2009 (1)
 June 2009 (4)
 May 2009 (5)
 April 2009 (4)
 March 2009 (2)
 February 2009 (1)
 January 2009 (7)
 December 2008 (1)
 October 2008 (2)
 September 2008 (7)
 August 2008 (1)
 July 2008 (1)
 June 2008 (1)
 April 2008 (5)
 February 2008 (4)
 January 2008 (4)
 December 2007 (3)
 November 2007 (12)
 October 2007 (2)
 September 2007 (4)
 August 2007 (3)
 July 2007 (1)
 June 2007 (3)
 May 2007 (1)
 April 2007 (4)
 March 2007 (3)
 February 2007 (7)
 January 2007 (1)
 December 2006 (2)
 October 2006 (2)
 September 2006 (6)
 July 2006 (4)
 June 2006 (2)
 May 2006 (6)
 April 2006 (3)
 March 2006 (6)
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 and found that it was open. Inside, she saw a very long row of chairs. She tried sitting in the first chair, but it was too small for her. So she tried sitting in the second chair, but it was also too small. The third chair was too small as well. “Oh dear,” said Goldilogs. “This is going to take all day.”
But then Goldilogs noticed that the chairs were arranged in order, from smallest to largest, and she clapped her hands with delight. “What organized people must live here!” she exclaimed. “I wonder, how ever did they arrange their chairs this way?” So she tried the chair in the middle of the row, and it was too big. Next she tried the chair a quarter of the way along, and it was too small. She continued in this manner, eliminating half of the remaining chairs with each test, until finally she found one that was Just Right. In fact, she found it so quickly that she had plenty of time to sit and enjoy reading from the selection of algorithms textbooks that she found on a shelf, and then she put everything back the way she found it and left before the bears got home.
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 post we found that the prefix length is fairly simple to find: it’s equal to the maximum number of factors of either 2 or 5 in .
What about ? This is a bit tricker to do efficiently. Let denote the result after removing all factors of or from , as before. Then we want to be evenly divisible by , or put another way, we want the smallest such that
So the obvious method is to compute , , , and so on, and find the first which yields . Practically speaking, we don’t have to compute from scratch at each step: we can start with , and then at each step multiply the current value by and reduce . We keep doing this until we reach again, and record how many steps it took. For example,
This took 6 steps, therefore is the smallest such that is divisible by 21; this matches what we saw in the previous posts, for example, the fact that has a repetend length of (remember that removing factors of 2 and 5 from yields ).
This method is correct, but we can do better—although for this we’ll need a little bit of group theory!
 Recall that is the set of numbers between and (inclusive) which share no common factors with .
 actually forms a group under multiplication : multiplying two values of always yields another such value, and for every there is some such that .
 We are then really asking for the order of the element in the group .
 By Lagrange’s Theorem, the order of an element must evenly divide the order of the group.
 The order of a group is just its size; in this case the order of is , the Euler totient function of .
 Hence we have learned that —the order of in the group —must evenly divide .
We can use this knowledge to find more quickly than simply counting powers of : just list all the divisors of , try each one by raising to the power of the divisor (using fast modular exponentiation of course), and pick the smallest one that yields . Using our example from before of , we find that , and so has to be one of , , , , , or . As another, bigger example, suppose . Then we can compute
.
(I was going to link to an explanation of how to compute —but it seems although I’ve mentioned many times before, I’ve never actually written about how to compute it! I’ll have to do that soon, since it’s a very interesting topic. In any case, if you don’t know how, you can just take my word for now.) This number has divisors we would have to try (since to make a divisor of , there are choices for the exponent of (namely, 0 through 5), 6 choices for the exponent of 3, and 2 choices for the exponent of ). things to try is much, much better than trying every single possible value from up to ! I wrote a little computer program to try them all, and it turns out that is the smallest divisor that works. Hence, we find that has a repetend of length (but I’m sure you knew that already =).
It turns out we can do this computation even faster—but that will have to wait for another post!
Posted in computation, group theory, modular arithmetic, number theory, pattern
Tagged decimal, expansion, group theory, rational, repeating, repetend, totient
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 repeating part. In that post I showed how to reduce it to the following question:
What are the smallest values of and such that is evenly divisible by ?
and I left it at that, with some questions for thought.

Can you see why we get to determine the values of and separately, i.e. neither value influences the other at all?
The reason we get to consider and separately is that and cannot possibly share any prime factors in common. only has 2 and 5 as prime factors; on the other hand, cannot have 2 or 5 as prime factors since it is equivalent to and . So the original question splits into two independent questions: (1) What is the smallest value of such that cancels all the factors of and in ? (2) What is the smallest value of such that cancels all the other prime factors in ?
The first subquestion is easy enough to answer: if , where has no factors of or , then choosing is both necessary and sufficient: it will be just enough to cancel all the factors of and in .
Let’s see how this works. The example we looked at last time was . If we factor we get , so our analysis above says , since there are two factors of . And sure enough, the decimal expansion has a prefix of length .
As another example, let’s pick a denominator by its factorization: suppose we have a denominator of . 5 has a higher exponent than the 2, so we predict the prefix will have length 4: and sure enough, for example,
We can try other numerators too, we just have to make sure they are relatively prime to . For example,
.
In my next post I’ll talk about how to find the repetend length!
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 wellknown that any rational number has a decimal expansion that either terminates, or is eventually periodic—that is, the digits after the decimal point consist of some initial sequence of digits, followed by a sequence of digits that repeats forever:
(Let’s assume ; if then we can just pull out the integer part before analyzing the part after the decimal point.) We’ll call the prefix, which has digits, and is the digit repetend.
The question is, given a fraction , how long will the prefix and repetend be (i.e. what are the smallest possible values of and )? In particular, it possible to compute and without simply doing long division?
It turns out that it is possible, and I’d like to explain how it can be done. I wrote about this a long time ago (exactly ten years and two days ago, actually!!) but I think I can do a better job explaining it now.
An example
Let’s start by looking at the fraction
It starts with a twodigit prefix (that is, ), and after that it repeats the sequence of digits forever.
Let’s play with this a bit. First of all, let’s multiply by to shift the prefix over to the left of the decimal point:
Now if we multiply by another , we shift one entire copy of the repetend to the left of the decimal point as well:
If we subtract these, the infinite repeating parts to the right of the decimal point will cancel, and we will be left with an integer:
(Of course in this case the integer is , but we don’t really care: since we’re only interested in the length of the prefix and repetend, it turns out that it doesn’t actually matter what the integer is, only the fact that it is one!)
We can now factor the lefthand side a bit to get
Let’s think about why this is an integer. Note that . First, the cancels with the and in , leaving
Now note that is divisible by , so the remaining denominator cancels and we are left with an integer. In fact, as you can check, is the smallest value of such that is divisible by .
Generalizing
Let’s generalize: suppose we have
and assume that is in lowest terms, that is, and share no common factors. Multiplying by shifts the prefix to the left of the decimal point,
then multiplying by and subtracting cancels the repeating part to the right of the decimal point:
Again, we can factor the lefthand side, yielding
We want to find the smallest values of and which make this work. Note that since we assumed and share no common factors, is actually irrelevant: it doesn’t contribute to cancelling at all. (This explains why repetends are always the same length for a given denominator.) So in the end, the question becomes:
What are the smallest values of and such that is evenly divisible by ?
Or, put another way, how can we choose and in such a way that every prime factor of also shows up in ? I’ll continue in future posts; for now, I leave you with a few questions:
 Can you see why we get to determine the values of and separately, i.e. neither value influences the other at all? (Hint: which prime factors of could possibly be canceled by ? Which could be canceled by ?)
 Can you figure out how to find the right value of ?
 Can you say anything at all about the right value of ?
(Hints: finding turns out to be much easier than finding , and requires only knowing some basic facts about divisibility. Saying useful things about requires knowing some number theory and/or group theory.)
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 able to prove this? Here’s one way to do it.
Suppose is composite and is a Fermat witness for —that is, . Let be some Fermat liar for , that is, is relatively prime to but . (How do we know there exists a Fermat liar for , you ask? Well, we don’t, but if there aren’t any then the theorem is obviously true.) Then I claim that is also a Fermat witness for :
So for every Fermat liar there is a corresponding Fermat witness . The only thing we might worry about is that some of these Fermat witnesses might not be distinct. But in fact, since is relatively prime to , multiplication by modulo is invertible, so and must be distinct modulo whenever and are. This proves that there are at least as many Fermat witnesses as there are liars; hence at least half are witnesses.
This means that, as long as there is at least one Fermat witness for , each we pick has a probability of at least of revealing that is composite. So if we pick different values for and all of them yield , we can conclude that there is only a chance that is composite. That’s pretty good, and it’s nice that the probability is independent of .
However, there’s one big flaw, which relates to my third question from the previous post: can there be composite values of with no Fermat witnesses? More in my next post!
Posted in computation, number theory, primes
Tagged Carmichael, Fermat, liar, primality, test, witness
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 using the Euclidean Algorithm, and is definitely not prime. (See my previous post.)

On the other hand, and might not share a prime factor, that is, they might be relatively prime (or put yet another way, their GCD might be ). This case breaks down into three subcases:
 . In this case we know by (the contrapositive of) Fermat’s Little Theorem that is definitely composite (although we don’t learn anything about its factorization); is called a Fermat witness for .
 is prime. In this case, Fermat’s Little Theorem tells us that must be equivalent to modulo . However, computing doesn’t necessarily tell us much, because the next case is also possible:
 but is composite. In this case is called a Fermat liar for .
The question becomes: for a given composite , how many Fermat liars and Fermat witnesses could there be? How many values of do we have to test to be “reasonably sure” whether is prime or composite?
Each pixel in the image from my previous post represents a particular pair. Each row represents a value of , with the top row corresponding to and the bottom row to . Each column represents a value of . Of course we only consider pairs with , which explains the triangular shape. (I include the case to complete the triangle, although these are not interesting from a primality testing point of view.)
The four cases outlined above correspond to the four colors:
 If and share a common factor, the pixel is colored yellow.
 If is a Fermat witness for , the pixel is green.
 If is prime, the pixel is blue.
 If is a Fermat liar for , the pixel is red.
Here’s a much smaller sample of the same visualization so we can see more clearly what’s going on.
Primes of course yield blue stripes. Nonprimes are stripes of yellow, green, and sometimes red. Testing a particular to see whether it is prime corresponds to picking random squares from its row: if we hit a yellow or green square, we learn immediately that is composite. If we hit a red square or a blue square, we aren’t sure. So far, however, things don’t look too bad: there are only a few isolated red squares, so picking two or three random values should be enough to ensure that we either find out is composite, or can safely assume that it is prime. Let’s continue the picture a bit farther; here are the first 100 values of :
I’ve also included some purple bars to the left of each row, showing what proportion of the numbers relatively prime to are Fermat liars. So far, none of the purple bars extend beyond the halfway mark (the first vertical line corresponds to half, and the second, slightly darker vertical line corresponds to ). It turns out there’s a good reason for this:
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.
Some questions for you:
 Can you prove this? The proof is not hard given the right idea.
 Suppose that for every composite , at least half the relatively prime values of are Fermat witnesses. If we pick random values of and find that for all of them, what can we say about the probability that is prime?
 The theorem has that pesky condition, “if there exists at least one Fermat witness for ”… do you think there could be composite values of with no Fermat witnesses? (Hint: go back and look at the picture from my previous post…)
Posted in computation, number theory, posts without words, primes
Tagged Fermat, liar, primality, test, witness
1 Comment