Originally posted by kbaumenAnswer below:
Find the last digit in result of 2^1996.
Explanation how you did it would be nice. It's not that I don't know the answer, I would just like to see if there are other ways than I figured of solving this problem.
#
#
#
#
#
#
#
#
#
#
The first five powers of 2 are: 2, 4, 8, 16, 32. The final digits will therefore cycle through 2, 4, 8, 6 (in that order). When the index is a multiple of 4 the final digit will be 6, hence 2^1996 has final digit of 6.
Modulo arithmetic. The last 4 digits go through a cycle of 500 "last 4 numbers", and thus all I have to do is find the 500th and move backwards.
To find that out, I determine that 2^500 modulo 625 is 1, and thus find the four digits that are divisible by 16 and 1 more than a multiple of 625. 625 modulo 16 is 1, so I'm looking for 625*15+1 or 9376.
Now if I divide this by 16, I get another number, 586. So the remainder of my answer when divided by 625 has to be 586 AND divisible by 16.
586 modulo 16 is 10, which means I want 6*625 + 586 which is 4336.
(Belated math geek alert btw)
Originally posted by geepamoogleis the cycle through 500 numbers the same for all powers...like 3^n ect, or is the specific to 2^n. How is '500' found.
Modulo arithmetic. The last 4 digits go through a cycle of 500 "last 4 numbers", and thus all I have to do is find the 500th and move backwards.
To find that out, I determine that 2^500 modulo 625 is 1, and thus find the four digits that are divisible by 16 and 1 more than a multiple of 625. 625 modulo 16 is 1, so I'm looking for 625*15+1 or 9376.
...[text shortened]... dulo 16 is 10, which means I want 6*625 + 586 which is 4336.
(Belated math geek alert btw)
It's the same for 3.
The theory is fairly simple. If you start with modulo 5, there are only 4 possible answers for relatively prime numbers (numbers not divisible by 5 in this case). So if you're looking at powers, it will start repeating after 4 consecutive powers. (For two it would be 1,2,4,3,1,2,4,3, or make it 10 and you get 1,2,4,8,6,2,4,8,6)
Now with 25 (5 squared), you'll find that there are only 20 relatively prime numbers to look at, which means only 20 possiblities before it repeats itself.. (5,10,15,and 20 are all divisble by 5).
With 125 (5 cubed), you see 100 relatively prime modulos, which is 5 times what you had with 25, which is 5 times what you had with 5 itself, so that pattern becomes obvious.