MENU
158,684

スレッドNo.103

数の性質

N=11^100+22^100+33^100+44^100+55^100+66^100+77^100+88^100+99^100
を10で割った余りは?

引用して返信編集・削除(未編集)

以下合同式はすべてmod10
2^4=16≡6
3^4=81≡1
4^2=16≡6
5^n≡5
6^n≡6
7^4=2401≡1
8^4=4096≡6
9^2=81≡1
から
N≡1^100+2^100+3^100+4^100+5^100+6^100+7^100+8^100+9^100
=1+(2^4)^25+(3^4)^25+(4^2)^50+5^100+6^100+(7^4)^25+(8^4)^25+(9^2)^50
≡1+6+1+6+5+6+1+6+1=33≡3
なので、3。

引用して返信編集・削除(未編集)

与式≡1+0+1+0+1+0+1+0+1≡1 (mod2)

また、p=5 についてフェルマーの小定理を用いると、
与式≡1+1+1+1+0+1+1+1+1≡3 (mod5)

よって
与式≡3 (mod10)

引用して返信編集・削除(未編集)

お二人とも性質を熟知されていることがビンビン伝わってきます。
ひょんなことから5乗においては,a=1,2,3,・・・,9で
a^5≡a (mod 10)
が成立していることに気付いて、これを活用できる問題として作成しておりました。

特にDD++さんの最も簡潔な近道に感激しました。
なおこれがmod 100
となった場合はどの様に対処できるのですか?

引用して返信編集・削除(編集済: 2022年06月14日 05:48)

> なおこれがmod 100となった場合はどの様に対処できるのですか?

以下合同式はすべてmod100
n^2≡nの解は0,1,25,76
(つまりこの4つは何乗してもmod100で不変)
2^20=1048576≡76
3^20=3486784401≡1
4^10=1048576≡76
5^2=25≡25
6^5=7776≡76
7^4=2401≡1
8^20=1152921504606846976≡76
9^10=3486784401≡1
11^10=25937424601≡1
なので
N=11^100+22^100+33^100+44^100+55^100+66^100+77^100+88^100+99^100
=11^100(1^100+2^100+3^100+4^100+5^100+6^100+7^100+8^100+9^100)
={(11^10)^10}{1+(2^20)^5+(3^20)^5+(4^10)^10+(5^2)^50+(6^5)^20+(7^4)^25+(8^20)^5+(9^10)^10}
≡1・(1+76+1+76+25+76+1+76+1)
=333≡33
となり、100で割った余りは33。

引用して返信編集・削除(未編集)

オイラーのトーシェント関数を使います。

オイラーの定理より、a が 5 の倍数でないとき
a^φ(25)=a^20≡1 (mod25)
なので、
与式≡1+1+1+1+0+1+1+1+1≡8 (mod25)

また、
与式≡1+0+1+0+1+0+1+0+1≡1 (mod4)

よって
与式≡33 (mod100)

引用して返信編集・削除(未編集)

ついでに 1000 で割る場合も。

オイラーの定理より、a が 5 の倍数でないとき
a^φ(125)=a^100≡1 (mod125)
なので、
与式≡1+1+1+1+0+1+1+1+1≡8 (mod125)

また、
与式≡1+0+1+0+1+0+1+0+1≡5 (mod8)

よって
与式≡133 (mod1000)


10000 で割るとなると手を変えないといけませんね。

引用して返信編集・削除(未編集)

このスレッドに返信

このスレッドへの返信は締め切られています。

ロケットBBS

Page Top