Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Exponents
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/