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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/