未解決ファイルARCHIVE
FILE No.12255REOPENED

余り面白くない問題

論理出題 若2010-05-16
事件概要
トランプで少し遊んでみましょう。

JをQがあまりに愛するものだから、Kが割り入ってしまいました。
さて、どうなったでしょう?

ジャックはキングとクイーンの間に生まれた王子だと思われがちですが、
実はそうではなく、ジャックは王に仕える兵士、騎士だとのこと。
これはとんでもない不倫関係、城内で血を見る事になるかもしれませんね。
殿中でござるのでそれはご勘弁ください。

さて、これでは捻ったなぞなぞになってしまいますので、
論理・パズルに出題する以上は、せめて軽い計算問題にしましょう。

----------------
(以下、演算子 "^" を冪乗演算するものとします。
「a^b」 は、「a の b 乗」を意味します。
結合則は乗除算より高いものと考えてください。)

J^Q を K で割った余り
つまり
11^12 を 13 で割った余り
を求めて下さい。
----------------
ベタに書けば、以下のように。
11×11×11×11×11×11×11×11×11×11×11×11を13で割った余りはいくつ?
(11を、12回かけて、それを13で割ってください)

答えの数を半角数字(13で割った余りですから1〜2桁)でお答えください。

求め方にはいろいろな方法がありますが、一番早いのはある定理を知っている場合ですかね。
ただし、それを知っている方はその定理を是非再度ご自分で証明してみてから答を入力して下さい。
封印された解答を開く
1
ヒント答え方に捻りは何もありませんのでご了承ください。

計算すれば答えは確実に出せますから、ヒントというのもなんなのですが、
力技で全てを計算するのは骨が折れるでしょうから簡単に。

割った余り(剰余)の世界は閉じた世界です。
その中で計算している限りは、必ずその中だけで計算していけます。

これを広げていったものが、有限体という世界です。
解説答えはAになりました。
せっかくのトランプ問題ですから軽く占い風に。

勘で入力した人:
 その直感が全てです。上手に世間を渡っていきましょう。
手で計算した人:
 本当にお疲れ様でした。その根気こそが開ける世界があると私は信じます。
電卓で計算した人:
 これを計算できる電卓を持っているあなたは道具選びに長けてますね。
 45bit以上の計算ができるものを選んだあなたの目は確かです。
剰余での性質を使った人:
 その知識と考え方を先へと進めれば、世の整数問題の全てを解ける日が来るかもしれません。
 世界の全ての暗号は、いずれあなたの手の中に収まるでしょう。
フェルマーの小定理を使った人:
 ちゃんと証明しましたか?
最初に0を答えてしまった人:
 11と13は互いに素ですから11をいくら掛けても13で割り切れるはずありません。
 うっかりハチベエの称号をあなたに差し上げます。

さて冗談はこれくらいにして、真面目に解説です。
(以下、"13 で割った余りが等しい"ことを示す相似記号として==を用います。
つまり「14 == 1」とは「14 ≡ 1 (mod 13)」を意味します。)
力技で計算した場合。冪乗していった結果は以下のようになります。

11^1 = 11 == 11
11^2 = 121 == 4
: (文字数制限のため省略)
11^12 = 3138428376721 == 1 (mod 13)

でもこんな膨大な桁数まで計算しなくても、剰余(割った余り)の中での計算はその中に閉じるという性質があります。
A = m×i + a
B = m×j + b
とした場合、足し算と同様
A×B = m×k + a*b ≡ a*b (mod m)
なので明かです。

そしてもっと簡単にこれを求める方法として、フェルマーの小定理を用いるという手がありますが、これを説明するには文字数が足りませんので検索してください。
(とフェルマー風に終らせる落ち)

11^13 == 11 です。Kがどう頑張ってもJはJなんですね。

捜査データ

解答数
269
歴代 8161位 / 16,274
正解数
66
正解率
25%
論理カテゴリ平均 19%
評価
★★★★★
1 pt / 歴代 10785位
Good / Bad
1 / 0
評価ボタンの投票
コメント
10
証言記録
正解率
25%
縦線 = カテゴリ平均

証言記録 (10)

若
「数セミ」のコラムにでも掲載されたことがありそうな問題ですが、私は見た事が無いものですから一応出題させて頂きます。
もし既存ということでしたらご指摘ください。
(そもそも私は「数セミ」のような雑誌を講読したことがありません。ごめんなさい)

暗号屋としてこの先の問題を作るステップに出してみますが、この方向で次のスマートな問題をいつ作れるかは自信がありませんのでご容赦を。
そうそう正解者
余りの可能性を考えて、とりあえず数撃とうと…
その後○○で計算してみました。解説はさっぱりわかりませんでした!
taka正解者 一発^^
5乗まで計算。あまりにある法則が。
それでいくと12乗においてこの答え、13乗に
おいて解説と同じ答え。
ですが、入力前自信なく、電卓で確認^^;
ありがとうございました。
残り7件の証言をすべて表示
キョンシー正解者
剰余の性質を使いましたが、計算ミスで一発逃しましたorz
若 皆様、ありがとうございます
せっかくの日曜の朝から、面倒な計算をさせてしまってすみませんでした。
しかし、これだけすぐに挑戦して頂けるとは思っていなかったため、
皆さんにコメントを頂けて嬉しい限りです。

ところで、解説文の占いは笑って頂けましたか?

(コメントが長文となります故、それぞれへの返答は次のコメントにて書かせていただきます)
若
そうそうさん
十三回撃てばあたるような問題を、それでは面白くないと正面から解いてくださり、ありがとうございます。
どんな方法であれ解こうと向かってくれるところが、やはりそうそうさんらしいですね。

takaさん
さすがの一発ですね。試行していくうちに法則を発見するとは、やはり暗号問題にも強いtakaさんらしいとも感じました。
最後のチェックを電卓でおさえてから一発とるところも、さすがです。

キョンシーさん
惜しい! 最後の一手で詰めを誤るなんて…
いい感じで大人になってしまった弊害がどこかにあるのかもしれません…と、自戒を込めまして勝手な事を申させて頂きます^^;
kikki
間違って出てしまった…。↑正解ついてないけど解きましたので〜。
2項定理使った私は負け組:*.;".*・;・^;・:\(*^▽^*)/:・;^・;・*.";.*:

削除aaaa
若 ありがとうございます
kikkiさん、お待ちしておりましたよ。
いきなり二項定理を生で使ってくるとは、ちょいとびっくりはしておりますが、
実は例の定理の証明方法の一つにも二項定理を用いる方法もあるようですので、
もしかしたら、そこに最も近いところにいらしたようですね、さすがです。
(というか、その証明を先にされていらしたのですか?)
kikki
ふと考えていたのですが、999999が7で割り切れるというのもこの定理が背景にあるのですね。
ところでこの性質を使った問題を思いついたのですが、若干若さんのこの問題のヒントというか、フマキラーの症定理(←違う)を解説で行うような形になってしまう感じになりそうなのですが…。投稿しても良いでしょうか…(^^;)。

削除キー1111
若
kikkiさん
フマキラーの解説はちゃんとできていなかったので、心残りでありました。
(解説文の半分近く使ってふざけた占い書いたのがいけないのですが^^;)
ぜひ kikkiさんの手でご出題して頂き、解説までお願いできれば幸いです。

関連する問題

NEXT CASE

現代版推理ゲーム

未解決ファイルはこちら

▶ 未解決ファイルへ

掲載内容に問題がある場合
削除依頼・お問い合わせはこちら

▶ Googleフォーム