Modular Arithmetic and Finding a 13th Root
Date: 11/29/2004 at 18:50:27 From: Roland Subject: How can I (easily) take a 13th root in my head Let's try to calculate the 13th root of 925103102315013629321 in our head. Impossible? No! 13th roots have some very special properties that I am trying to investigate right now. Instead of really taking the 13th root of a number, one could actually calculate the 77th power of it. Since 13*77=1001, at least the last 4 digits would remain the same. Hence this approach would work for numbers of up to 50 digits in length! In the example given above, the 77th power of the last four digits "9321" (and only those are relevant) is "0041". Hence the 13th root is 41. Done! My only question is how to calculate the 77th power of a given number easily, but this turns out not to be too bad (see below), even though I am still missing the philosopher's stone. I had the problem in the past that these kind of complicated modulo-formulas got more complicated the more dependent the values are on other values. It turned out (for the other problem which was calculating square roots based on continued fractions) that it is actually quite easy to do the calculations using an iterative scheme based on the extended eucledian algorithm. However, I do not succeed in finding the right method for *easily* calculating the 2nd-last, ... digits of the 13th-root (respectively the 1001th power) in the same way. I just can't find a regularity in the formulas outlined below. Can you please help me in finding one? So far, I set my focus on numbers ending with a "1" (for a special reason, since there are numeric problems with even endings and endings on "5", which I am sure I would be able to solve as soon as my question is answered). I distinguish - "the root" - the 13th power of "the root" - the 1001th power of "the root" = the 77th power of the 13th power The following rules do apply: - last digit of the root = last digit of the 13th power = last digit of the 1001th power (in the example, this is "1") - the second last digit follows the very simple rule: "-n*3 mod 10" where n is the second last digit of the 13th power. For example, the second last digit of 41^13 = ...9321 is "2". -2*3 mod 10 = 4, so the second last digit of the root must be 4. - the third last digit also follows a very straight scheme: look up the value in the table given below using the 2nd-last digit and subtract 3 times the third-last digit of the 13th power. The result is the third last digit in the 13*77th power = the third last digit of the root! - I have one more formula like these ones for the following (fourth-last) digit, but it got awfully more complicated. Even worse, I might need even more digits to calculate for my needs, so I am basically stuck due to complexity. However, I am convinced that this can be done very easily! Please use the following table referenced above: 3rd-last digit of the 13th power: 0 1 2 3 4 5 6 7 8 9 value to use for further calculation: 0 3 9 7 6 8 2 7 5 5 for the example (41^13) you would use the second-last digit of (...9321)="2" to look up the value "9" in the table. Subtract the 3rd-last digit multiplied by 3 and calculate modulo 10: 9-3*3 mod 10 = 0. Hence the third-last digit of the root = third-last digit of the 1001th power is 0.
Date: 11/30/2004 at 17:14:34 From: Doctor Vogler Subject: Re: How can I (easily) take a 13th root in my head Hi Roland, Thanks for writing to Dr. Math. I see what you are trying to do, and that's a very clever idea that I've never seen before. Allow me to help you understand the math here. So you have some very large number N, which you know to be the k'th power of an integer for some (relatively large) number k. You want the k'th root. The idea depends on the fact that the k'th root is really an integer, for otherwise you'll get something that makes no sense at all. (Of course, if you're not sure, then you can always try the algorithm, get some number, and then take the k'th power and see if it worked.) First of all, your ideas are heavily founded in modular arithmetic, so I'm going to assume you are at least somewhat familiar with modular arithmetic. If not, you can start here: Mod, Modulus, Modular Arithmetic http://mathforum.org/library/drmath/view/62930.html So the idea is that you have N, and you know that N = m^k for some integer m, which you want to calculate by taking powers. So first you count up the digits of N, divide by k, and add one, and you find that m is a pretty small number. Let's say that you know m has, at most, d digits (in decimal). So the observation is that you actually only need to look at the last d digits of N. And then you have N = m^k (mod 10^d). Now, the next step requires that N is not divisible by 2 or 5, so that N--and therefore m--are elements of the multiplicative group of units mod 10^d. Then you just have to compute the order of the group mod 10^d. It turns out that every element of that group has order dividing r = lcm(4, 2^(d-2), 5^(d-1)), which is r = 5*10^(d-2) when d is at least 4, and r = 4, 20, 100 when d = 1, 2, 3. So now you just need to compute the multiplicative inverse of k mod r. Let's say this number is t. Then you raise both sides of the equation N = m^k (mod 10^d) to the t'th power. Then tk = 1 (mod r) means that you get m on the right. And since this is mod 10^d, you only need to use the last d digits of N on the left, and you get N^t = m (mod 10^d) but since you know m is smaller than 10^d, you get m exactly! To fill in two details, we have: How do you compute the multiplicative inverse (t) of k mod r? And how do you compute N^t mod 10^d? The answer to the first question is the extended Euclidean algorithm. Since you already mentioned that algorithm, I'll assume you know how to do it. The second problem is called modular exponentiation, and the usual technique is to repeatedly square N, reducing mod 10^d (taking only the last d digits) after each squaring, then multiplying together the terms you want (reducing after each multiply). For example, N^77 = (N^64) * (N^8) * (N^4) * N. So now let's do your problem by way of example. Let's find the 13'th root of 925103102315013629321. This number is 21 digits long, so a 13'th root can't be more than 2 digits long, since if m >= 100 then m^13 >= 100^13 = 10^26 > 925103102315013629321. So we really only need two digits. Of course, you *could* use more digits, but it makes the math easier to use as few as possible. So we compute m from N = m^13 (mod 100) 925103102315013629321 = m^13 (mod 100) 21 = m^13 (mod 100). We have d=2, so r=20. Now we need a multiplicative inverse for 13 mod 20. In fact, 77 is the multiplicative inverse for 13 mod 5, 20, and 100, and 500, so that will work for up to four digits. The smaller number 17 will also work for two digits, and it's a little easier to work with. So then we compute 21^17 (mod 100) or 21^77 (mod 100). We get 21^2 = 41 (mod 100) 21^4 = 81 (mod 100) 21^8 = 61 (mod 100) 21^16 = 21 (mod 100) 21^32 = 41 (mod 100) 21^64 = 81 (mod 100) In either case, 21^17 = 21 * 21 = 41 (mod 100) 21^77 = 81 * 61 * 81 * 21 = 41 (mod 100). And therefore m = 41 (mod 100). But since m < 100, that means m = 41. So we conclude that 41^13 = 925103102315013629321, which, in fact, it does. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum