プロフィール

mathnegi

Author:mathnegi
ゆる~い人間です(*´ヮ`*)
宮城県在住~

カレンダー

05 | 2017/06 | 07
- - - - 1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 -

最新記事

全記事リスト

全ての記事を表示する

最新コメント

月別アーカイブ

カテゴリ

閲覧者数

検索フォーム

RSSリンクの表示

リンク

ブロとも申請フォーム

この人とブロともになる

QRコード

QR

電卓だよん♪

電 卓

お問い合わせはこちらまで~♪

名前:
メール:
件名:
本文:

受験ブログ 大学受験(指導・勉強法)へ

スポンサーサイト

--.--.-- --:--|スポンサー広告
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2013年日本数学オリンピック予選 第9問

2013.01.28 00:00|数学
どもども。

今回はこの間の日本数学オリンピック予選の第9問をやります~

いよいよあと4題ですねー
いわば四天王ですakaname.gifeto_mi.gifeto_tora.gifisona.gif
ここからはどの問題も本気で手強いです~

間違ってるところあったら教えてね~

問題はこちらから~箱ドットおにおん2mini
http://www.imojp.org/challenge/old/jmo23yq.html

問題文はいたってシンプル
10^2013-1の約数で1以上100以下のものをすべて出してね~~
というものです~

2013絡みの問題,いよいよ登場ですね~
数オリ受けるような人間なら 2013=3×11×61 であることは
頭にインプットしてあることでしょう

とりあえず解法を1つ挙げるんですが,
なかなか骨が折れる作業です~
きっと,もう少し効率のいい解法もあるんじゃないかな~という気はします~
是非是非教えて下さいませませ~


さてさて,10^2013-1という数字の形を見るに,
フェルマーの小定理がパッと頭をよぎる人も多いかと思います~

フェルマーの小定理というのはコレですねinsect_kabuto_m.gif


p1_20130123052152.jpg

この定理を利用して問題にアタックしてみよーと思います

10^2013-1が素数pを約数に持っていると仮定しましょう~
このときpについてどんなことが言えるんでしょうか。
それを探ってみます~

10^2013が10の倍数なので,とりあえず2と5は
10^2013-1の約数ではないことは分かります。
すなわち p≠2,5 ですね。

ここでフェルマーの小定理より,

10^(p-1)≡1 (mod p)

であることが言えますkorobo.gif


2013をp-1で割った時の商をQ_1,余りをR_1としましょう~
すなわち 2013=(p-1)Q_1+R_1 です~
このとき,10^2013={10^(p-1)}^Q_1×10^R_1
≡(1)^Q_1×10^R_1≡10^R_1 (mod p)
が成り立ちます~。
今度はp-1をR_1で割った時の商をQ_2,余りをR_2として
10^(p-1)≡10^R_2 (mod p)
を導きます。この操作を繰り返していくと
10^2013≡10^(p-1)≡10^R_1≡10^R_2≡10^R_3≡…… (mod p)
となり,ユークリッドの互除法より,2013とp-1の最大公約数をgとすると

10^2013≡10^g (mod p)

が成り立つことが分かります~kojika.gif


p2_20130123052152.jpg
p3_20130123052153.jpg


このことは,2013A+(p-1)B=gを満たす整数A,Bが存在することを
利用して言うこともできます~kuma_fly.gif


p4_20130123052153.jpg


逆に, 素数pに対して,2013とp-1の最大公約数gが
10^g≡1 (mod p) を満たしていたら,pは 10^2013-1 の約数だと
いえるでしょうか?

2013÷g=M とすると, (10^g)^M≡1^M より
10^2013≡1 が従いますねm_0001.gif


p4 5


というわけで, 10^g≡1 (mod p) を満たす(g,p)の組を探す作業が始まります。
gは2013の100以下の約数なので,その候補は1,3,11,33,61の5通りに絞られます~

各候補に対して,対応し得るpを求めていけばいいですね~

g=1,3の時は 10^g-1 とその約数が容易に分かるので
それを手掛かりにpを探すのが早そうです

p7_20130123052221.jpg
p8_20130123052221.jpg

g=11,33,61 のときは,10^g-1の素因数分解は大変そうなので
方針を変えます。p-1はgの倍数なので, p-1=gk と書けます。
p=gk+1 の形で表される素数について条件を満たすかチェックすることにします~patikapa.gif

例えばg=11のときは,p=11k+1の形で書ける100以下の素数は
p=23,67,89 の3つですね~
ただし,p=67だとg=33になってしまうので,コレは除外です~

p=23,89 のとき, 10^11≡1 (mod p) が成り立つかどうか
検証します。合同式の性質を使って根性で確かめていきます~

p9_20130123192856.jpg

残りの場合も同様に検証していくよーrabi_happy.gif


p10_20130123192857.jpg

p11_20130123052223.jpg

p12_20130123052223.jpg


10^2013-1の素因数は 3,37,67 であることはわかりました。
あとはこの3つの素因数から作られる合成数である約数についての検証が必要ですs2_sum_bbq.gif

100以下の約数を求めればいいので,37と67の倍数については37と67のみになるので
3^2=9,3^3=27,3^4=81 について検証すれば十分です~

3の倍数,9の倍数かどうかの判断は,各桁の数の和をとってみればわかりますよねー
10^2013-1=999…9 (9が2013個並んでいるよ~)
なので,検証は困難ではありません~

   p16.jpg

p13_20130123052243.jpg

    p17.jpg









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

テーマ:算数・数学の学習
ジャンル:学校・教育

タグ:2013 日本数学オリンピック 予選 フェルマーの小定理 素因数 合同式 約数 最大公約数

コメント

質問

いつも、このブログを楽しみに見させてもらってます。
突然すいません。
この問題の初めのほうで商と余りを置いてユークリッドの互除法を用いて、 素数pに対して,2013とp-1の最大公約数gが
10^g≡1 (mod p) を満たしていることと,pは 10^2013-1 の約数であることは同値であると示しておられましたが、どのような発想でそのような解法にいたったのでしょうか?自分のような凡人には到底思いつきません...もし、お時間があれば、教えていただけると幸いです。

No title

コメントありがとうございます~

約3年前の記事らしいですねー
そんなに前から記事書いてたっけなーとか別の部分でしみじみ思ったりしてしまいました~
3年も前なので当時の思考の様子は覚えてないですが,
フェルマーの小定理を何とか利用できないものかと試行錯誤した記憶はなんかありますねー

2013乗からg乗まで次数下げできたんだけど,きっとこれがカギなんじゃないかな~
もしかしてこれが必要十分条件だったりしないかな~もしそうだったら嬉しいな~
あ!期待通りだったー♪やったぜワッショイ♪

みたいな感じだったんじゃないかと思います~
このアイデアはフェルマーの小定理が利用できそうな別の問題にも活用できる機会がありそうですね。
整数論や群論なんかに長けた人にとってはすごい自然な発想なのかもしれないです。
まぁ定かではないですが~v-39


非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。