7^nの下3けた

 投稿者：山中和義  投稿日：2014年 3月23日(日)12時48分53秒
  大阪桐蔭中学　入試問題　2009年度（平成21年度）算数7番
たとえば7×7×7×7=2401のように、7を4回かけた数を7[4]のように表します。
よって、7[4]の下3けたは401となります。
ただし、7[1]、7[2]の下3けたはそれぞれ007、049として考えます。
このとき、次の問いに答えなさい。
(1) 7[8]を計算しなさい。
(2) 7[20]の下3けたを求めなさい。
(3) 7[2009]の下3けたを求めなさい。

答え
(1) 7[8]=7[4]×7[4]=2401×2401=5764801
(2) (1)より、7[8]の下3けたは801
    7[20]=7[8]×7[8]×7[4]=801×801×401=257282001　∴7[20]=001
(3) 7[2009]は、7[20]を100回かけた数に7[8]をかけて、さらに7[1]をかけたものである。
    7[20]を100回かけた数の下3けたは001なので、801×7=5607　∴7[2009]=607
（終り）

7のべき乗の下3けたを表示してみると、


!7^2009 mod 1000 の計算
LET x=1
FOR n=1 TO 2009
   LET x=MOD(x*7,1000)
   PRINT n; x
NEXT n
END



その２


!7^2009=(7^20)^100*7^9≡1^100*7^9≡7^9 mod 1000
LET x=7
LET c=1
DO UNTIL x=1 OR c>2009 !7^c≡1 mod 1000を満たすcを見つける
   LET x=MOD(x*7,1000)
   LET c=c+1
LOOP
PRINT c
LET m=MOD(2009,c) !2009=c*Q+mより、(7^c)^Q*(7^m)と分解する
PRINT m
PRINT MOD(7^m,1000) !7^c≡1 mod 1000なので
END



高校生による考察

7*7=49=50-1より、7^2000=(50-1)^1000
これを二項定理で展開すると、
　項 comb(1000,r)*50^r*(-1)^(1000-r)、r=0,1,2,3,…
の和となる。
r=3以上では、50^rが1000で割り切れるから、下3桁はすべて0となる。


OPTION ARITHMETIC RATIONAL !多桁整数
LET s=0
FOR r=2 TO 0 STEP -1 !r=3,2,1,0のとき
   LET s=s + comb(1000,r)*50^r*(-1)^(1000-r)
NEXT r
PRINT MOD(s*7^9,10^3) !残り7^9を加味して
END



その２　多項式(x-1)^rの展開とその値


OPTION ARITHMETIC RATIONAL !多桁整数
LET x=50 !7*7=49=50-1より、7^2008=(50-1)^1004
LET s=0 !二項定理で展開した式をホーナー法で計算する
FOR r=2 TO 0 STEP -1 !r=3以上では、50^rが10000で割り切れるから、下3桁はすべて0となる。
!!FOR r=1004 TO 0 STEP -1
   LET s=MOD(s*x + comb(1004,r)*(-1)^(1004-r), 10^3)
NEXT r
PRINT MOD(s*7,10^4) !残り7を加味して
END



その２-２　多項式(x-3)^rの展開とその値


OPTION ARITHMETIC RATIONAL !多桁整数
LET x=10 !7^2009=(10-3)^2009
LET s=0 !二項定理で展開した式をホーナー法で計算する
FOR r=2 TO 0 STEP -1 !10^3, 10^2, 10, 1
!!FOR r=2009 TO 0 STEP -1
   LET s=MOD(s*x + comb(2009,r)*(-3)^(2009-r), 10^3)
NEXT r
PRINT s
END

 		 

Re: 7^nの下3けた

 投稿者：山中和義  投稿日：2014年 3月24日(月)09時54分31秒
  > No.3343[元記事へ]

問題
7^k（kは自然数）を10進法表示したとき、
表示の中のある部分に0が8個以上並ぶことが起こるという。
さて、これが起こるkはいくつか？

考察
オイラーの定理より、a＞0、n＞1のとき、(a,n)=1ならa^φ(n)≡1 mod n
(7,10^k)=1なので、7^φ(10^k)≡1 mod 10^k
k=1のとき、φ(10)=4より、7^4≡1 mod 10
k=2のとき、φ(100)=40より、7^40≡1 mod 100
k=3のとき、φ(1000)=400より、7^400≡1 mod 1000
k=4のとき、φ(10000)=4000より、7^4000≡1 mod 10000
　　：
よって、01、001、0001、00001、… のように下のけたに0が並ぶ。
この場合、7^4=2401のように、7^4≡1 mod 100、7^40≡1 mod 1000、… となる。
（終り）

補足
(x,y)=1のとき、φ(xy)=φ(x)φ(y)
pは素数のとき、
φ(p)=p-1
φ(p^m)=p^m-p^(m-1)=(p-1)p^(m-1)
より、
φ(10)=φ(2*5)=φ(2)φ(5)=(2-1)(5-1)=4
φ(100)=φ(2^2*5^2)=(2^2-2)(5^2-5)=2*20=40
φ(1000)=φ(2^3*5^3)=(2^3-2^2)(5^3-5^2)=4*100=400
φ(10000)=φ(2^4*5^4)=(2^4-2^3)(5^4-5^3)=8*500=4000
（終り）


実際に、探索してみると、


OPTION ARITHMETIC RATIONAL !多桁の整数
FOR N=1 TO 9 !mod 10^n
   LET A=7
   LET K=0
   LET B=1 !a^k=b
   DO
      LET K=K+1
      LET B=MOD(B*A,10^N)
   LOOP UNTIL B=1 !a^k≡1
   PRINT N; K
NEXT N
END


　n  k
　---------
　 1  4
　 2  4
　 3  20
　 4  100
　 5  500
　 6  5000
　 7  50000
　 8  500000
　 9  5000000

となる。


数字列の途中に現れる0を考えると、

答え
1  4
2  20
3  74
4  154
5  499
6  510
7  4411
8  6984
9  33836
（終り）


9以上は困難であるが、、、


OPTION ARITHMETIC RATIONAL !多桁の整数

LET A=7

LET K=0 !a^k=b
LET B=1

LET N=1 !0がn個
LET S$=REPEAT$("0",N)
DO WHILE N<=10 !10個まで
   IF POS(STR$(B),S$)>0 THEN !最初に見つかったもの
      PRINT N; K

      LET N=N+1 !次へ
      LET S$=REPEAT$("0",N)
   ELSE
      LET K=K+1
      LET B=B*A
   END IF
LOOP

END


 		 

戻る