Prove that the last 6 digits of 7^10000 is 000001?

Question

A question posted earlier asks for the last digit of 7^10000, which is 1. See:

http://answers.yahoo.com/question/index;_ylt=AkJay6wHimMniniNwiQNoxXsy6IX?qid=20070528191026AAAQKZg&show=7#profile-info-Xj9PN2XGaa

Prove that the last 6 digits of 7^10000 is 000001.

Mark S, but it can be proven. If you don't believe it's true, then prove it false.

For example, 7^20 ends in 001.

Man, lots of different ways of proving this. How to choose?

Answer 1

Wow, a problem from Scythian that I actually figured out in less than six hours. I am so proud of myself...

First, I note that 7^4 = 2401, which is one more than a multiple of 400. Write this number as 400k + 1.

Now take the fifth power of this: 7^20 = (400k + 1)^5 = (400k)^5 + 5(400k)^4 + 10(400k)^3 + 10(400k)^2 + 5 * 400k + 1. This number is one more than a multiple of 2000. Write it as 2000k + 1. Hence 7^20 ends in 2001, 4001, 6001, 8001, or 0001.

Take the fifth power of this new number: 7^100 = (2000k + 1)^5 = (2000k)^5 + 5(2000k)^4 + 10(2000k)^3 + 10(2000k)^2 + 5 * 2000k + 1. This number is one more than a multiple of 10000. Write it as 10000k + 1. Hence 7^100 ends in 0001.

Take the tenth power of this new number: 7^1000 = (10000k + 1)^10 = (10000k)^10 + 10(10000k)^4 + ... + 10 * 10000k + 1. This number is one more than a multiple of 100000. Write it as 100000k + 1. Hence 7^1000 ends in 00001.

Finally, take the tenth power one last time to get 7^10000 = (100000k + 1)^10 = (100000k)^10 + 10(100000k)^4 + ... + 10 * 100000k + 1. This number is one more than a multiple of one million. Write it as 1000000k + 1. Hence 7^10000 ends in 000001.

QED

* * * * *

Bonus factoid! The number ends in 6000001, i.e. the digit in front of the 000001 is a 6.

* * * * *

On Quadrillerator's argument: I follow that 1 = a^(2^5) mod 2^6 for odd a, but it seems to me that would imply 1 = a^(10^5) mod 2^6. In other words, 2^5 divides 10^5, but not 10^4.

Similarly, I follow that 1 = a^(4*5^5) mod 5^6 for a not divisible by 5, but, again, it seems to me that would imply 1 = a^(10^5) mod 5^6. Here, 4 * 5^5 = 12500, which divides 10^5, but not 10^4.

In summary (if I am following this correctly), his argument proves 7^10^5 rather than 7^10^4 ends in 000001.

Edit, note to Quadrillator: Ah, leave it in. It's nice technique and instructive, even if it is off by a factor of 10. :)

Answer 2

Since 1 = a^(2^5), mod (2^6) ==>
1 = a^10000, mod 2^6 for a≠0 mod 2

Since 1 = a^(4*5^5), mod(5^6) ==>
1 = a^10000, mod 5^6 for a≠0 mod 5

Thus, 1=a^10000 mod 10^6 for odd a not divisible by 5. So
7^10000 mod 10^6 = 1

---------- --------- --------- ----------

Explanation: Euler's Theorem (a generalization of Fermat's Little Theorem) says that:
1 = a^(φ(n)) mod n
where n is relatively prime to a and where Euler's totient function, φ(n), counts the number of positive integers less than n that are relatively prime to n.

If n=p^k for p prime, this becomes:
1 = a^((p-1)p^(k-1)) mod p^k for a≠0 mod p


***** ***** *****
Good catch Zanti! Dang 0 - I totally misread the problem.
I can patch up my proof, but it's not cute anymore, and I'll probably remove it in a while.

Since 1 = a^(2^5), mod (2^6), for a≠0 mod 2 ==>
a^10000 = (a^32)^312 * (a^16) = a^16 mod (2^6)
But 7^2 = 49
and (1+48)^4 is clearly 1 more than a multiple of 64 so
7^8 = 1 mod (2^6) so that
7^16 = 1 mod (2^6)
Thus, 7^10000 = 1 mod (2^6)


Since 1 = a^(4*5^5), mod(5^6), for a≠0 mod 5
and since 1047^5 = 7 mod (5^6) ==>
7^10000 mod (5^6)
= (1047^5)^10000 mod (5^6)
= (1047^(5*(5^4)*4))^8 mod (5^6)
= (1)^8 mod (5^6)
= 1 mod (5^6)


So 7^10000 mod 10^6 = 1

Answer 3

we know 7^4 = 2401

so 7^10000 = (2401)^2500

now 2401^2500 = (2400+1)^2500

if we collect nth term it it (2500 C n) (2400)^n

for n > 2 2400^n is divisible by 10^6

so we need to look for n = 2 and n =1

n=0 gives 1 and 1-1 = 0

n = 2 => (2500C2)(2400)^2 = 2500*1200*2400 so 10^6 is a factor
n =1 =>(2500)(2400) = 6000000 so 10^6 is a factor

so all the elements except last that is 1 is divisible by 10^6 and last element is 1

so last 6 digits are 000001 or 7^10000 mod 10^6 = 1

Answer 4

we can write 7^10000 as 49^5000
(1-50)^5000
using binomial,
=1 - 5000*50 + (5000*(5000-1)*(50)^2)/2 - (5000*4999*4998*(50)^3)/6 + (5000*4999*4998*4997*(50)^4)/24 - (5000*4999*4998*4997*4996*(50)^5)/120...
4th term and the other terms from 6th onwards are not going to contribute, since this can be writen as some integer*10^7

we only have to take contribution of first, second,3rd and 5th terms.
first term gives 1 in the unit place.
2nd gives -2 in the 5th and -5 in the 4th place
3rd gives 75
5th gives 5 in the 6th place
but this doesnt give the right answer.
Am i doing sumthing wrong??
maybe im making some calculation mistake.
Anyways, im tired

Answer 5

7^4mod10^6=2401 (7^4)^5=7^20 7^20mod10^6= 2401^5mod10^6=612001 (7^20)^5=7^one hundred 7^100mod10^6= 612001^5mod10^6=60001 (7^one hundred)^5=7^500 7^500mod10^6= 60001^5mod10^6=300001 (7^500)^5=7^2500 7^2500mod10^6= 300001^5mod10^6=500001 (7^25000)^4=7^ten thousand 7^10000mod10^6= 500001^4mod10^6=000001

Answer 6

it is simple to calculate: create simple program like this

float resf;
long res
for(int i=1;i<=10000;i++){
resf=res*7;
res=resf%10000000;
}

after this in the res you will have the last 7 digit of the 7^10000
it can be checked with smaller numbers

Answer 7

I don't think that the last 6 digits are as you've indicated. Below are the first several values in the series; you'll see that the repeating pattern prevents having zeroes in the last few places.
7
49
343
2401
16807
117649
823543
5764801
40353607
282475249
1977326743
13841287201
96889010407
678223072849
4747561509943
33232930569601
232630513987207