2090:整数部分

イメージ 1

イメージ 2

問題2090・・・ひよこさんのブログ http://myhome.cururu.jp/gersdorffite/blog/article/70000854869 より Orz~





































































解答

上記サイトより Orz~

・周期pさんのもの Orz~

(5+Sqr(19))^n = a+bSqr(19) とおけば、(a、bは自然数)
(5‐Sqr(19))^n = a‐bSqr(19)
が全ての自然数nで成立する。
これが、共役性の利用の具体例。
この2式をたせば、
2a = (5+Sqr(19))^n +(5‐Sqr(19))^n
⇔ (5+Sqr(19))^n = 2a‐(5‐Sqr(19))^n
ここで、 0 < 5‐Sqr(19) < 1 であるから、
(5+Sqr(19))^n の整数部分が 2a‐1 とわかる。
ここからは解けるとふみました。

・まるさんのもの Orz~

2a = (5+Sqr(19))^n + (5-Sqr(19))^n
= Σ[k=n to 0]{ (5^k・Sqr(19)^(n-k)) + 5^k・(-Sqr(19))^n-k) }

Sqr(19)のある項は、打ち消しあう。
19の累乗がかかっている項は、19で割り切れるので、mod19のとき残るのは、最初の項のみ。

≡2・5^n (mod 19)

2a -1 ≡ 2・5^2005 - 1
≡ 2・5^7 - 1 (mod 19) (∵ 5^n (mod 19) はnが9個で1サイクル、5^9≡1)
≡ 2・16 - 1 ≡ 12 (mod 19)

巧妙なものですね♪
5^7≡17 がすぐ分からなかったので、、、

・わたしの

5^18≡1 (mod 19)・・・フェルマーの小定理
だから、2005/18=111・・・7 から、
2・5^2005≡2・5^7
5^9≡1 or -1
5^18・5^9=5^27=(5^3)^3 のはず。
125/19=6・・・11
つまり、5^3≡11
2・5^7≡2・11^2・5=1210
1210/19=63・・・13
けっきょく、2・5^7-1≡13-1=12

共役性を使って解く問題は最初に見たとき感動しました♪
ひよこさんのブログには面白い問題、、、かなり難しいけど、、、誰かさんじゃないけど、、、中毒になりそうです...^^;γ
けど、、、さすがに今日は当直明けで、、、眠い。。。Good night ! ...Zzz...

関連記事
スポンサーサイト



コメント

No title

スモークマン
さやかさん、いらっしゃいませ~ ^^
このベッドルームのデザインはシンプルでいいでしょ♪
大御所のデザイナーの方のものです...Orz...v

No title

★さやか★
さっぱりです。

ぽち!
非公開コメント

トラックバック