フェルマーの小定理

昨日のABC F問題のように、既約分数（有理数）を「(mod 素数) における逆元を用いて整数として表現する」ことが問われる場合があります。 atcoder.jp この記事では 分数をなぜ整数として表現できるのか どうやってその値を算出するのか という辺りを丁寧にまとめてみます。 逆数と逆元（数学的に丁寧な話） この項目は数学的に込み入った話になるので、プログラミング的な話に注目する人は飛ばしても良いです。 まず、分数とは何かをあらためて考えてみます。， について、 です。言い換えれば、分数（＝除算）は割る数 の逆数 を掛ける操作（＝乗算）です。 では、逆数とは何でしょう。 の逆数を と表現す…

素数に関するオイラーの定理ここでは，(フェルマーの) 2平方定理の証明で用いる素数に関するオイラーの定理の証明をします． 2平方定理奇素数(奇数かつ素数，すなわち 3 以上の素数) が 4 で割ると 1 余るとき， は 2 つの平方数の和として表される．2平方定理については，詳しくは上のリンク先に記事がありますので，そちらをどうぞ． 以下が素数に関するオイラーの定理です．オイラーの名前が残っている数多くの定理のうちの一つです． 定理．奇素数 について，\begin{align*} p\equiv 1 \pmod{4} \end{align*}と\begin{align*} x^2\equiv …

フェルマーの小定理(Fermat's little theorem)フェルマーといえば, 360年間もの間証明されなかったことで有名な「フェルマーの最終定理」があります. まず, フェルマーの小定理の内容を紹介します.素数 と自然数 が互いに素であるとき,\begin{align*} a^{p-1}\equiv 1 \pmod{p} \end{align*}が成り立つ.つまり, を で割ると1余る, という意味です. (合同式についてはこちら). 証明ここでは証明を3通り挙げておきます. 1つ目, 2つ目の方が分かりやすいですが, 3つ目の方法はこの定理の一般化であるオイラーの定理の証明に応用…

自己紹介 MMA Contestとは 当日までの話(自分語りなのでスキップ推奨) 当日、会場にて 結果 A B C D E F G H I, J, K, L 乾燥した感想 脚注 自己紹介 はじめまして、電気通信大学Ⅲ類機械システムプログラム所属、とりあえずで決めた名前を引きずっていたらとうとう最近同じ発音の名前の人が後輩に現れてしまってそろそろ改名を考えているしゅん/Сюнという者です。 いろいろやらかして留年してしまい、システム上は4年生ですがまだ研究室に入っていません。頑張らないとですね。 AtCoderではstunniitaとして参加しています。現在は茶色です。 atcoder.jp 電…

WaniCTF 2023 にソロで参加しました。全完して4位でした。

ソロオンライン参加 9完10位 各問題の考察内容 ここでの問題順番はAC順. B: Merge Sequences 個を全て列挙は当然できない. そこで, 大きい 個のみを列挙しなければならない. 列挙する必要がある数のうち, 最小の値が分かっていればそれ以上の値になるものだけを列挙すればよくなり, 判定も構築も二分探索でできる. かなり典型度が高い問題なので実際は考察を挟まず実装に手を付けた. C: Range Same Query 全て等しいことと, 最大値最小値に気づけるかが肝. 前者は基本的には範囲内の全ての要素を確かめなければいけないが, 後者は最大値と最小値の つの値のみを高速に取…

ちょっとだけおさらいから入りましょう。 $p$を素数、$F_p$を 位数$p$の有限体とします。$F_p$の$0$以外の元の集合$F_p^{\times}$は位数$p-1$の巡回群になります。そうするとフェルマーの定理から任意の$x\in F_p$について$x^{p-1}=1$が分かります。両辺に$x$を掛ければ$x^p=x$となります。この式は$x=0$も含めて$F_p$の全ての元で成り立ちます。また$x^p=x$を$F_p$あるいはその拡大体での方程式と見た時、その解の個数は多項式の理論から高々$p$個です。一方、実際に$p$個の要素を持つ有限体$F_p$の元は全てこの方程式の解となってい…

いよいよこのシリーズも核心に入っていきます。今回は平方剰余の定義を与え、平方剰余記号を定義します。また平方剰余の基本的な性質を示した後、平方剰余の相互法則と関連する補充則などを紹介し、簡単なものには証明をつけます。最後に平方剰余の相互法則をより対称な形で表した命題を提示し、それが成り立つことをMaximaで再確認してみます。 定義 \(p\)を奇素数として\(a\)を\(p\)と互いに素な整数とします。\(a\)がある整数\(n\)の平方と法\(p\)で合同である時、\(a\)を\(p\)の平方剰余であるといいます。式で書けば、方程式\(X^2\equiv a\,(mod\,p)\)が解を持つ…

2023/04/08 『数の女王』（川添愛：著／東京書籍）を読んだ。 まずは出版社の紹介文を引く。 人間一人ひとりに「運命の数」が与えられている世界。メルセイン王国の王妃は、呪いで敵を殺しているという噂があった。王妃の娘で１３歳のナジャはある日、数年前に死んだ最愛の姉ビアンカが、実は王妃によって殺されたという話を耳にする。その後、ナジャはあるきっかけで、禁じられた計算を行う妖精たちと出会い、王妃の秘密を知ることになる―「数」が運命を司る、不思議な国の物語。数論とアルゴリズムをテーマにした傑作ファンタジー！ 数の女王 作者:川添愛 東京書籍 Amazon 川添愛氏は初読みである。読んでその独特の…

今回エントリーするのは、山本芳彦『数論入門』岩波書店だ。この本は以前にも、このエントリーで紹介しているが、今回は違う観点から推薦したいと思う。 数論入門 (現代数学への入門) 作者:山本 芳彦 岩波書店 Amazon ゆえあって、最近またこの本を読み始めたのだが、面白くて遂にほぼ全部読んでもうた。そして全体を読破すると、この本がもくろんでいること、この本の特質がひしひしつと伝わってきた。ひとくちに言えば、この本は、「ドラマの優れた総集編を観るようなすばらしい内容」ということなのだ。 ドラマの総集編って、全12話を4話ぐらいでかいつまむ。もちろん、圧縮しているので、カットされたエピソードもあるし…

...あれ、見えてますかね？ こんにちは、抹茶大好きまっちゃラテです！！ え～...すみません、話が苦手なもので、ブログも何を書けばいいかわからんですが... 今回、Mojacoder さんで開かせていただきました、私の単独コンテスト、Matcha Rate's Sakura Contest -MRSC- 🌸🍡 の、裏話やどんなことをやったのかなど、ここに記録していこうと思います！ えーとその前に... 私がコンテスト、または問題作成の際に心がけていることを記します。主に以下の 4 つです。 私としたことが、GTXC のやつも忘れてたので、ここに記します。 ラテ流作問の掟目次 第一: やはり最…

https://kenkoooo.com/atcoder/#/contest/show/b57b32ea-19c0-4724-ab73-f7839e0cae86 ４問目 atcoder.jp（+1, +2）, (+2, +1)★マスの移動は下記のように分解できる。 (+1, +2 ) = (0, 1) + (1, 1) (+2, +1 ) = (1, 0) + (1, 1)n * m の格子点の左下から右上に行く問題に帰着できる。また、一回移動するたびに x + y = +3 移動回数をnとすると 合計でn回移動するため、目標地点（格子の右上の点）は(X-n, Y-n) となる。 これを (A…

昨日の記事に書いた 「ChatGPT」を体験してきました。 文章で何を聞いても とても賢い人間が書いたかのような返答の来るAIです。 質問 「世界経済はどうなっていくのか」 ぶ・・・無難な答えｗ 僕が抽象的に聞きすぎてるのか 他の質問にも 似たような無難な返答になることがありました。 次の質問 「フェルマーの小定理の簡単な証明はある？」 エクセルやプログラミングに強いとの噂を聞いたので 具体的な数学的質問。 「群論で簡単に証明できます」 くらいを期待したら めっちゃ具体的な証明を書いてきた、スゴイ・・・ ただ合ってるかは知らないｗ パッと見た感じ３で定理自体を使ってて 間違ってそうな予感。 最…