7 to the hundredth power divided by nine?

Question

I have been working this problem for a while and I know there must be a better way of finding the answer than I have been trying. Please help? Will you show me how to get the answer?

The question is [find the remainder when 7 to the hundredth power is divided by 9].

Answer 1

The easiest way to solve this problem involves properties of modular arithmetic. If you're not sure what that is, think of the way we tell time (on a 12-hour, am/pm system). Telling time is very similar to modular arithmetic. The basic idea is that you only have a few numbers, and once you get to the largest one you start at 0 again. It might be better to think of it as a set of remainders. When you divide by 9, you can only get 0, 1, 2, 3, 4, 5, 6, 7 or 8 as a remainder. You can't get 9 or any number bigger than 9 because if you could you could take another 9 out.

What's neat about modular arithmetic is that you can break up a number into factors and figure out the equivalent of those factors in the modular system. So if you have a number like 33, you can break it into 3 * 11. Then you know that the remainder when you divide 3 by 9 is 3, and 11 by 9 gives 2. You can replace the numbers in your factored formula. So 3 * 11 is the same as 3 * 2 (the 2 takes the place of the 11 because they give the same remainder when dividing by 9). Thus the remainder is 3*2 = 6. If you check it, the remainder when you divide 33 by 9 is 6.

In your specific problem, you can use properties of exponents in a similar way. 7^100 is the same as (7^4)^25. That is, 7 to the fourth power, and that whole number raised to the twenty-fifth power. You can make it even easier by breaking this up further to ( (7^2)^2)^25. That is, square seven (you get 49), then square that and raise the whole mess to the twenty-fifth power. You then just work your way from the inside out, reducing everything modulo 9... That is, you change each part to its equivalent remainder when divided by 9.

So, 7^2 = 49. 49 gives a remainder of 4 when divided by 9. So you can replace the innermost 7^2 with a 4.

Now you went from ((7^2)^2)^25 to (4^2)^25. Now, you can figure out that 4^2 is 16, so you're really looking at 16^25. You know that 16 gives a remainder of 7 when divided by 9, so you can change the 4^2, or 16, to a 7.

Now you have (4^2)^25 is the same as 16^25 which is the same as 7^25. You could stop here, but breaking it up further will help.

7^25 is the same as (7^5)^5. These numbers aren't too pretty, but they're not nearly as bad as 7 to the hundredth power. 7^5 is 16807. So now you've reduced it to 16807^5. Now it's time to figure out the remainder of 16807 divided by 9.

It turns out that 9 divides 16803, so the remainder above is 4. That means that big messy thing gives the same remainder 4^5. That is, 16807^5 is "congruent to" (the same as) 4^5 "mod 9" (the remainders are the same when you divide by 9).

Just one more step now. We just need to figure out the remainder of 4^5 when divided by 9. 4^5 is 1024. That means that the remainder when you divide by 9 is 7, because 9 divides 1024-7= 1017.

So, since each step along the way has given us equivalent expressions when you take the remainder upon division by 9, the remainder when dividing 7 to the hundredth power by 9 is the same as when dividing 1024 by 9. It is 7.

In short (if you've made it this far without being too confused), the answer is 7.

Answer 2

There is a general pattern.
7^1 mod 9 = 7
7^2 mod 9 = 4
7^3 mod 9 = 1
7^4 mod 9 = 7
7^5 mod 9 = 4
etc etc
generally
7^(3n+1) mod 9 = 7
So 7^100 mod 9 = 7

Answer 3

Starting with 7^2/9, the remainfers repeat 4,1,7, 4,1.7 ....., so when n= 100 , the remainder will be 7.

Answer 4

The exact answer is 7/9 ^ 100 Who in the world is doing remaindering (integer arighmetic) at the 100th power? You trying to calculate primes at that level to do RSA encryption (or break it)

I wish people would explain why they are doing these weird things. An effort to better undestand numbers! I guess my question is why do you really care?

Ron.

Answer 5

7^1 rem 9 = 7
7^2 rem 9 = 4
7^3 rem 9 = 1
7^4 rem 9 = 7
7^5 rem 9 = 4
7^6 rem 9 = 1
and so on.
So, 7^100 rem 9 = 7.

Answer 6

Nevermind, read the question wrong.