Large Numbers and CongruencesDate: 03/05/2002 at 12:42:43 From: Boris Dusek Subject: Last three digits of large number Find the last three digits of the number 11^(11^(11^(11^(11^11)))) written in base seven. Date: 03/09/2002 at 06:57:06 From: Doctor Pete Subject: Re: Last three digits of large number Hi Boris, This is a very challenging question! In order to answer it, I will have to use some ideas from elementary number theory; in particular, I assume you are already familiar with congruences. I will write a == b (mod m) to mean a is congruent to b, modulo m. Now, let P[0] = 1, P[n] = 11^P[n-1], for all positive integers n. Then 11^(11^(11^(11^(11^11)))) = P[6]. The last three digits of P[6] in base 7 is equivalent to finding 0 <= x < 343 such that P[6] == x (mod 343). (Note 343 = 7^3.) This is because P[6] in base 7 has the representation P[6] = a[0]7^0 + a[1]7^1 + a[2]7^2 + ... + a[d]7^d, where the coefficients a[0], a[1], ..., a[d] are nonnegative integers from 0 to 6. Thus, when P[6] is divided by 7^3, the remainder is x = a[0]7^0 + a[1]7^1 + a[2]7^2, and we see that expressing x in base 7 will give us the last three base-7 digits of P[6]. That said, the first observation to make is that 11^147 == 1 (mod 343). How did I find this congruence? I used a computer. However, I used it for convenience, not out of necessity. This is because, if necessary, we can compute by hand 11^2 == 121 (mod 343), 11^4 == 121^2 == 235 (mod 343), 11^8 == 235^2 == 2 (mod 343), 11^16 == 2^2 == 4 (mod 343), 11^32 == 4^2 == 16 (mod 343), 11^64 == 16^2 == 256 (mod 343), 11^128 == 256^2 == 23 (mod 343), 11^147 = 11^(128+16+2+1) == 23*4*121*11 = 122452 == 1 (mod 343). So, we have, for nonnegative integers k, m, with m < 147, 11^(147k + m) = (11^147)^k * 11^m == 1^k 11^m = 11^m (mod 343). It follows that we seek the the value of m for which P[5] = 147k + m, or equivalently, the remainder of P[5] divided by 147, or P[5] == m (mod 147). To do this, we again compute successive powers of 11 modulo 147, and we find 11^42 == 1 (mod 147), and 11^(42k' + m') = 11^m' (mod 147), where 0 <= m' < 42, and 0 <= k'. Thus by similar reasoning as before, we want to find m' such that P[4] == m' (mod 42). By now the process should be clear; we compute 11^6 == 1 (mod 42), so we want to find a number m" such that P[3] == m" (mod 6). This leads us to compute 11^2 == 1 (mod 6), so we want to find a number m"' such that P[2] = 11^11 == m"' (mod 2). But since 11 is odd, 11^11 is itself odd, so m"' = 1. Therefore, P[3] == 11^m"' = 11^1 = 11 == 5 (mod 6), hence m" = 5, and continuing back up along the chain of congruences we have constructed, we find P[4] = 11^m" = 11^5 == 23 = m' (mod 42), P[5] == 11^m' = 11^23 == 23 = m (mod 147), P[6] == 11^m = 11^23 == 219 (mod 343). Thus x = 219, which, when written in base 7, is 432, since 4*7^2 + 3*7 + 2 = 4*49 + 21 + 2 = 196 + 23 = 219, so 4, 3, 2 are the last three digits of P[6] written in base 7. I hope my explanation has been sufficiently clear. I used several important properties of congruences, so if you are unfamiliar with them, I highly suggest any book on elementary number theory. - Doctor Pete, The Math Forum http://mathforum.org/dr.math/ Date: 03/10/2002 at 08:56:34 From: Boris Dusek Subject: Last three digits of large number Thank you for your answer. It was not only clear but also very challenging because you showed me the way(s) how you can sort out such difficult problems. So thank you very much for your response! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/