YLL討論網

求2^1234之末四位

5^1234之末四位有循環性已解決

2^1234還沒解決
有請各位大大

首先就是找出有無規律：

由於2^10的末四位為1024
　　2^30的末四位為1824
　　2^50的末四位為2624
　　...

可看出每逢二十次方時，末兩位皆相同，且千百位數差8

另外，兩數乘積的末四位可視為此兩數之末四位相乘。

因此，2^1234=(2^1230)*(2^4)

其中，2^1230之千百位為[(1230-10)/20]*8+10=498，只取98

故2^1230之末四位為9824

所以2^1234之末四位為9824*16之末四位，其值為7184。

piny 寫到:首先就是找出有無規律：

由於2^10的末四位為1024
　　2^30的末四位為1824
　　2^50的末四位為2624
　　...

可看出每逢二十次方時，末兩位皆相同，且千百位數差8

另外，兩數乘積的末四位可視為此兩數之末四位相乘。

因此，2^1234=(2^1230)*(2^4)

其中，2^1230之千百位為[(1230-10)/20]*8+10=498，只取98

故2^1230之末四位為9824

所以2^1234之末四位為9824*16之末四位，其值為7184。

紅色部分可以補一下證明嗎
補上證明
本題就破解啦

2^10的末四位為1024
2^30的末四位為1824
2^50的末四位為2624
2^70的末四位為3424
2^90的末四位為4224
2^110的末四位為5024
2^130的末四位為5824
2^150的末四位為6624
2^170的末四位為7424
2^190的末四位為8224
2^210的末四位為9024
2^230的末四位為9824
2^250的末四位為0624
2^270的末四位為1424
2^290的末四位為2224
2^310的末四位為3024
2^330的末四位為3824
2^350的末四位為4624
2^370的末四位為5424
2^390的末四位為6224
2^410的末四位為7024
2^430的末四位為7824
2^450的末四位為8624
2^470的末四位為9424
2^490的末四位為0224
2^510的末四位為1024

我不會證明，但經試算可發現2^510的末四位已重覆。

先介紹一個數論上相當重要的定理-尤拉定理

尤拉定理：
設m是大於1的整數，n屬於自然數且(m,n)=1，則m^φ(n)≡1 (mod n)
其中，φ(n)表示不大於n，且與n互質之自然數個數，又稱為尤拉函數。

在本題中，取m=2，n=5^4=625，φ(625)=625*(1-1/5)=500
根據尤拉定理，2^500≡1 (mod 625)
即2^500-1=625t，(2^4)(2^500-1)=10000t，2^504-2^4=10000t
可推得2^504≡2^4 (mod 10^4)

2^1234  
= [(2^504)^2]*(2^226)
≡ (2^8)*(2^226) (mod 10^4)
≡ 2^234 (mod 10^4)
≡ 2^(13*2*3*3) (mod 10^4)
≡ 8192^(2*3*3) (mod 10^4)  
≡ 8864^(3*3) (mod 10^4)
≡ -(1136)^(3*3) (mod 10^4)
≡ -(3456)^3 (mod 10^4)
≡ -2816 (mod 10^4)
≡ 7184 (mod 10^4)
末四位數為7184

sorry! 忘了登入

先介紹一個數論上相當重要的定理-尤拉定理

尤拉定理：
設m是大於1的整數，n屬於自然數且(m,n)=1，則m^φ(n)≡1 (mod n)
其中，φ(n)表示不大於n，且與n互質之自然數個數，又稱為尤拉函數。

在本題中，取m=2，n=5^4=625，φ(625)=625*(1-1/5)=500
根據尤拉定理，2^500≡1 (mod 625)
即2^500-1=625t，(2^4)(2^500-1)=10000t，2^504-2^4=10000t
可推得2^504≡2^4 (mod 10^4)

2^1234
= [(2^504)^2]*(2^226)
≡ (2^8)*(2^226) (mod 10^4)
≡ 2^234 (mod 10^4)
≡ 2^(13*2*3*3) (mod 10^4)
≡ 8192^(2*3*3) (mod 10^4)
≡ 8864^(3*3) (mod 10^4)
≡ -(1136)^(3*3) (mod 10^4)
≡ -(3456)^3 (mod 10^4)
≡ -2816 (mod 10^4)
≡ 7184 (mod 10^4)
末四位數為7184

其他應用：
若取m=2,n=5^3，可求2^k的末三位數
若取m=2,n=5^2，可求2^k的末兩位數

我學的時候是叫歐拉定理,歐拉函數
只是地區不同譯音不同的差別...(有時真令人討厭)

讓我說說如何求出φ(m)

6=2^1*3^1
φ(6)=2^(1-1)*3^(1-1)*(2-1)*(3-1)=2

45=3^2*5^1,
φ(45)=3^(2-1)*5^(1-1)*(3-1)*(5-1)=24

10800=2^4*3^3*5^2,
φ(10800)=2^(4-1)*3^(3-1)*5^(2-1)*(2-1)*(3-1)*(5-1)=2880

舉了這些例子
相信大家都能明白如何求φ(m)
那麼還有否其他方法呢？

這定理就如費馬小定理一樣~
不過歐拉定理不只是對質數
而是對所有數(當然m,n互質除外)