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
_____________________________________________

Power from Its Base and a Little String?

Date: 04/11/2012 at 11:34:14
From: Diogo 
Subject: Find the exponent of a power from the last K digits

Hi, 

I would like to know if there's a way to find the exponent of a base
given the last K digits of its decimal expansion.

For example, take seven as a base, and 143 as the last three digits of
some power of 7. In short, 7^n = ...143.

Powers of seven have a pattern, so I used this in my favor, and did this
modular arithmetic to try to find the exponent:

   143 mod 10 = 3
      tenBase = 1000

I tried many cases:

   7^3 mod 1000 (if it equals 143)
   7^7 mod 1000
   7^11 mod 1000
   7^13 mod 1000
   7^17 mod 1000
   7^21 mod 1000 = 143.
   
So 7^n = .....143 for n = 21.

But I would like to know if there are any reverse ways to find the
exponent "n" more quickly. In particular, extremely large cases pose some
real difficulty.



Date: 04/12/2012 at 14:12:54
From: Doctor Vogler
Subject: Re: Find the exponent of a power from the last K digits

Hi Diogo,

Thanks for writing to Dr. Math. 

Let's suppose that you know an integer x, an integer y, and a positive
integer K such that

   x^n = y (mod 10^K)

You want to find out all integers n that satisfy this equation. In fact,
let's also assume that x is neither even nor divisible by 5 (and the same
about y).

It turns out that the multiplicative group of integers mod 10^K has the
structure of a product of cyclic groups of orders (when K >= 2):

   2, 2^(K - 2), 4, and 5^(K - 1).

(When K = 1, you get a cyclic group of order 4.)

This means that the powers of x will repeat in a pattern of the least
common multiple (LCM) of those numbers. So the cycle length is [a 
factor of]

   K  = 1: 4
   K  = 2: LCM(2, 1, 4, 5) = 20
   K  = 3: LCM(2, 2, 4, 25) = 100
   K >= 4: LCM(2, 2^(K - 2), 4, 5^(K-1)) = 5*10^(K - 2)

What this means is that if K is very large, then you can try the four
powers of x mod 10 to see which one of those (if any) is equal to y mod
10. That will tell you the value of n mod 4. Then you can try the five
different choices for n mod 20 that have the necessary value of n mod 4,
and see which one of those (if any) is equal to y mod 10. Then the five
choices for n mod 100 that have the necessary value of n mod 20, and the
five choices for n mod 500, trying ten choices at each step. For each, you
only have to try at most ten powers and get another digit of n.

When you are done, you will know the value of n mod 5*10^(K - 2), which is
the best you can do, since adding any integer multiple of 5*10^(K - 2) to
n will not change x^n mod 10^K.

Actually, your number x might be a power itself, in which case the minimal
cycle length could be smaller than what is indicated above. But the
theorems on the following Dr. Math conversation will tell you how to find
out the actual cycle lengths (which is the order of 7 mod 10^K):

    http://mathforum.org/library/drmath/view/70472.html 

For example, you want to solve 7^n = 143 mod 10^K. First, we compute the
order of 7 mod 10^K. It is the LCM of the orders of 7 mod 2^K and 
7 mod 5^K. Since 7 has order 4 mod 5, but 7^4 - 1 is divisible by 25 (and
not 125), that means that the order of 7 mod 5^K is

   K  = 1 : 4
   K  = 2 : 4
   K >= 2 : 4*5^(K - 2).

Next, 7 is 3 mod 4, and 7^2 - 1 is divisible by 16 (but not 32), so that
means that the order of 7 mod 2^K is

   K  = 1 : 1
   K  = 2, 3, 4 : 2
   K >= 4 : 2^(K - 3).

This means that the order of 7 mod 10^K is

   K  = 1 : 4
   K  = 2 : 4
   K  = 3 : 20
   K  = 4 : 100
   K >= 5 : 5*10^(K - 3).

So we try 7^0, 7^1, 7^2, and 7^3 mod 10, and find that

   7^3 = 3 mod 10

This means that n = 3 mod 4. And this is also sufficient for K = 2. 

Next, we try 7^3, 7^7, 7^11, 7^15, and 7^19 and find that if K >= 3, then
n = 19 mod 20. If K >= 4, then we need to check 7^19, 7^39, 7^59, 7^79,
and 7^99. It turns out that none of them ends in 0143, so there are no
solutions if K >= 4.

On the other hand, if you had asked when 7^n = 849 mod 10^K, then you
would find that there are solutions for all K:

  K = 1 : n = 2 mod 4
  K = 2 : n = 2 mod 4
  K = 3 : n = 14 mod 20
  K = 4 : n = 34 mod 100
  K = 5 : n = 134 mod 500
  K = 6 : n = 1134 mod 5000
  K = 7 : n = 21134 mod 50000
  K = 8 : n = 21134 mod 500000
  K = 9 : n = 521134 mod 5000000
  K = 10 : n = 45521134 mod 50000000
  K = 11 : n = 345521134 mod 500000000
  K = 12 : n = 4345521134 mod 5000000000
  K = 13 : n = 4345521134 mod 50000000000
  K = 14 : n = 204345521134 mod 500000000000
  K = 15 : n = 1204345521134 mod 5000000000000
  K = 16 : n = 46204345521134 mod 50000000000000

And so on.

At each step after K = 5, there are ten values to check, and each choice
gives one of the ten digits for the next digit of 7^n. So one of them
always works.

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:
College 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/