Suppose p and q are relatively prime integers, and 0 < p < q. If q has any prime factors besides 2 and 5, then a decimal expansion of p/q will eventually start to repeat. How long will the repeating part be?
Looking at the sequence of digits is actually a very difficult way to approach this problem. It's much simpler to look at the sequence of remainders. Remember how long division works. At every step, we have a remainder r, 0 <= r < q. To get the next digit in the expansion, we figure out how many times q goes into 10*r; this gives us a digit and a new remainder. In C++ code, I might write the long division algorithm this way:
/* Compute ndigits digits of p/q */
r = p;
for (i = 0; i < ndigits; ++i) {
d[i] = (10*r) / q;
r = (10*r) % q;
}
where those unfamiliar with C should remember that C's integer
division gives an integer result (in C, we have 1/2 == 0, but 1.0/2 ==
0.5). The operator % gives the remainder of the division.
If we keep computing digits, we will eventually see one of two things:
a zero remainder, or a repeat of a remainder seen in a previous step.
In the former case, p/q can be written as a non-repeating decimal; in
the latter case, we have a repeating fraction, where the length of the
repeating part is the same as the distance between occurrences of the
same remainder in the division algorithm.
The operator % is sometimes called the modulo operator, but
it's actually an odd name. In much of computer science, we speak of
the mod operator
, and mean operator that computes the
remainder in a division.
By contrast, if you're working with
abstract algebra or number theory and you say that two things are
equivalent modulo
something, you mean that there is an
underlying relation that divides your structure into equivalence
classes, and the two things under investigation happen to lie in the
same equivalence class. The usual example of this is time: 11 pm
today and 11 pm yesterday are not the same instant in time, but they
are equivalent modulo the twenty four hour cycle we use for time
keeping. The connection between modulo-as-operation and
modulo-an-equivalence is that when one takes a remainder after
dividing by q, one gets a single canonical representative of a whole
equivalence class of numbers which differ from each other by some
multiple of q. It's like using 11 pm today to refer to 11 pm any day;
they're all equivalent modulo a 24 hour day.
Anyhow. The C code for long division computes a sequence of
remainders, which look like r[k] = (p*10^k) % q. If q has prime
factors other than 2 and 5, then at some point we'll encounter a
remainder which is prime relative to q; at that point, we've started
the repeating part of the fraction. Past that point, the remainders
are all units in the ring of integers modulo q (Z_q),
which is
just a fancy way of saying that all the successive remainders are also
prime relative to q (and therefore have inverses in Z_q). For
instance, 4 and 7 are relatively prime, so 4 is a unit in Z_7; the
inverse is 2, since 4*2 = 7+1 = 1 modulo 7. The set of units in Z_q
is an important object in number theory, so important that it's size
is given a special name: the number of natural numbers less than q
which are prime relative to q is written phi(q); it is called Euler's
phi function or Euler's totient function.
Hmm. I assume totient
is related to quotient,
but I
actually don't know the origin of this word. I'll have to look that
up.
One reason why phi(q) is so important is that it connects the structure of multiplication and addition in Z_q. For example, for any m which is a unit in Z_q, I have m^phi(q) = 1; for instance, phi(7) = 6, and 4^6 = 4096 = 1 modulo 7. That means, for instance, that I have an easy way to write m^(-1); it's just m^(phi(q)-1). There are all sorts of other entertaining things you can do with this sort of manipulation -- including figuring out something about the question we originally asked, which is how long the repeating part in the decimal expansion of p/q will be. Without loss of generality, I can just consider 1/q; for more general p/q, I will generate a sequence of remainders which has the same period as for 1/q. Anyhow, if I start from the remainder 1 and run long division, the remainders will generate a cyclic subgroup of the group of units in Z_q -- I'll keep generating new remainders until at some point I get the remainder 1 back. Since I'm always multiplying by 10, the cycle thus formed is sometimes called the orbit of 10 in the group of units in Z_q. The order of this cycle -- the number of elements -- is the number of digits in the repeating part of the decimal expansion. There is a wonderfully versatile little theorem, due to Lagrange, which says that the order of a subgroup must divide the order of the group in which it is contained; in this case, that means that the number of digits in the repeating part must divide phi(q).
Cool, no? So the number of digits in the repeating part of a decimal expansion of p/q must divide phi(q). Actually, if you walk through the arguments I just made, you find that this is true for any base. So, for example, take q = 47; since phi(q) = 46 = 2*23, I can take an expansion in any base and find that the length of the repeating part is either 0, 1, 2, 23, or 46. Base 2, base 10, base 16 -- they all have to generate repetitions with a period that divides 46. Which divisor of 46 you actually get depends on the base in which you do the expansion, though.
So while writing the length of the repeating part of p/q is difficult in general, we can quickly say that it divides phi(q). When q is prime, phi(q) = q-1, and so we could potentially get a repeating part as long as q-1 digits. In fact, we often do get a repeating part as long as q-1 digits... which is why writing numbers in terms of repeating decimal isn't a very good choice of representations for most q. If it takes log10(p) + log10(q) < 2*log10(q) digits to represent a rational number in the form p/q, but as many as q-1 digits to represent the number as a repeating decimal, then the repeating decimal representation is exponentially longer than the rational number representation. Not good! At least, it's not good if you want to actually do arithmetic; if you want to play with number theory on the other hand, or with finite state machines, then this is lots of fun.
As an amusing aside, you can use the development above to write a wholly impractical scheme for cracking the RSA cryptosystem. You see, the RSA system is secure because we don't have good algorithms for computing the Euler totient function for large numbers. Yes, I know you've heard that the reason that RSA is secure has something to do with factoring, but the difficulty of factoring large numbers is really just a proxy for the difficulty of computing Euler's totient. The actual connection is that if m and n are large prime numbers then there's a simple formula for the totient of the product: phi(m*n) = (m-1)*(n-1). But if we do long division in several different bases, we're almost inevitably going to run into a base in which the length of the repeating part is equal to phi(q). So the totient function is actually easy to compute, and any talented grade schooler who knows about long division and repeating decimals can be taught how to crack RSA, right? Well, not exactly. The fact that computing phi(m*n) in this way would take time on the order of m*n -- rather than on the order of log(m*n) -- means that your precocious grade schooler would take at least 130 years to crack a 32-bit key, assuming that he never slept and could get a digit a second right.
A fast computer using a more effective attack algorithm could break a 32-bit RSA key in a matter of minutes (maybe less, I'm not sure). But those algorithms tend to run into the same explosive cost increases as the long-division cracking algorithm that I just proposed, so the key doesn't have to get that much longer to be much more secure. Currently, most transactions are guarded by keys at least 128 bits long, and the keys I use for remote login have either 1024 or 2048 bits. So unless you want to go into number theory as a career, you probably will find that the easiest way to compromise my keys is to completely go around them -- by finding my office and kicking me in the shins until I'm willing to hand them over, for instance.