剰余が同じになること。 通常は「≡」という関係演算子を用い、 a ≡ b (mod p) という形で表現する。
上記の式は「『a = p * n + b』なる整数nが存在する」という意味である。
問題.自然数 に対し, を で表す. たとえば, である. (1) を 0 以上の整数とする. は で割り切れるが, では割り切れないことを示せ. (2) が 27 で割り切れることが, が 27 で割り切れるための必要十分条件であることを示せ. 方針.(1) について は 1 が 個並んだ数で, は 1 が 個並んだ数なので, が 3 個並んだ数とみなすこともできます. このことに気がつけば, についての帰納法で証明できそうであると分かります. (2) についてこちらは (1) と比べて難しいですが, まず最初に が 9 で割り切れることが, が 9 で割り切れるための必要十分条件であること…
オイラーの定理(Euler's theorem)自然数 に対して, と が互いに素であるとき, 次の式が成り立つ.但し, はオイラーの関数.オイラーの名前を冠した定理は沢山ありますが, これもそのうちの一つです. オイラーのφ関数オイラーのφ関数 は, 以下の自然数で と互いに素であるものの個数を表します. 例として, (1, 3, 7, 9が10と互いに素) (1, 5, 7, 11が12と互いに素)特に, 素数 に対しては, より小さい自然数はすべて と互いに素なので,となります.上で紹介しているオイラーの定理の として素数 を与えると, フェルマーの小定理となることが分かります. 証明こ…
ウィルソンの定理定理: 2以上の正整数 が素数であることと, 次の合同式が成り立つことは同値です.\begin{align*} (p-1)!\equiv-1 \pmod{p}\tag{1} \end{align*}合同式が関係する有名な定理の一つです. (合同式についてはこちら. ) 証明 が素数なら式(1)が成り立つことの証明は1通り, 逆の証明は2通り紹介します. 前半の証明は分かりにくいかもしれませんが, 対偶を示しています. 逆の証明は, フェルマーの小定理と合同式における剰余の定理を用いる方法. ～ を積の剰余が1になる組に分けられることを示す方法. です.対偶をとって, が素数でな…
合同式における剰余の定理 の整数係数多項式 が\begin{align*} f(a)\equiv 0 \pmod{m} \end{align*}を満たす ( は整数) 任意の に対して\begin{align*} f(x)\equiv (x-a)Q(x) \pmod{m} \end{align*}となる整数係数多項式 が存在する. の次数は よりもひとつ下がっている.等式の剰余の定理は高校でも学習する範囲に入っていますが, 合同式でも同様の定理がなあり立ちます. この定理はウィルソンの定理の証明などで使います.合同式についてはこちら. 証明 を前提する.\begin{align*} f(x) …
フェルマーの小定理(Fermat's little theorem)フェルマーといえば, 360年間もの間証明されなかったことで有名な「フェルマーの最終定理」があります. まず, フェルマーの小定理の内容を紹介します.素数 と自然数 が互いに素であるとき,\begin{align*} a^{p-1}\equiv 1 \pmod{p} \end{align*}が成り立つ.つまり, を で割ると1余る, という意味です. (合同式についてはこちら). 証明ここでは証明を3通り挙げておきます. 1つ目, 2つ目の方が分かりやすいですが, 3つ目の方法はこの定理の一般化であるオイラーの定理の証明に応用…
合同式(congruence) は整数, は正の整数として, が で割り切れるとき\begin{align*} a\equiv b \pmod{c} \end{align*}と書き, この形の式を合同式といいます. また, このときの を合同式の法といいます. また, 上の式を以下のように書くこともあります. \begin{align*} a \bmod c = b \end{align*} プログラム経験のある人なら, という記号を使うと思いますが, 数学では を使います.合同式の両辺の , は整数であることに注意してください. この部分が分数の形になる計算をする場合は, 割り切れているかを…
以前紹介したものを少し修正したものです. スポンサーリンク // 前回の投稿 描画ルールを変更 p=37までの図表 p=5 p=7 p=11 p=13 p=13 p=19 p=23 p=29 p=31 p=37 前回の投稿 blog.thetheorier.com 前回と言ってももう4年以上前ですね. 原始根や指数の定義はもはや割愛しますが, 指数表を図式化することで何か特徴を見いだせないか…と思ったのがことの始まりでした. 描画ルールを変更 前回は素数pに対して単位円をp等分して隣り合う指数の値を繋げました. ある程度の傾向は評価できましたが互いに平行に近い, しかし平行でない組があってなん…
恵方巻といえば、節分の日に決まった方角（恵方）を向いて無言で食べると良いとされる巻き寿司のことです。恵方は毎年変わり、以下のようにして決まるそうです： 西暦年の1の位 恵方 24方位 方位角*1 16方位 東基準反時計周り 4・9 甲 075° 東北東やや東 015° 0・5 庚 255° 西南西やや西 195° 1・63・8 丙 165° 南南東やや南 285° 2・7 壬 345° 北北西やや北 105° （歳徳神 - Wikipediaより一部引用） 例えば2021年の恵方は「南南東やや南」ですね。 16方位だと「南寄りの南東のやや南（7.5°）」と聞こえてややこしいので、個人的には「南…
非負の整数 𝒏 にたいし, 線型漸化式によって定義される多項式列, \begin{align} (L_n)=2,\ x,\ x^2+2,\ x^3+3x,\ \ldots\\ A,\ B,\ xB+A,\ \ldots \end{align} に関して, 素数の法 𝒑 の下で, 𝑳𝒑 ≡ 𝒙ᵖ が成りたつ.
RareTEC受講生のリュウです。 RareTECH（レアテック）| 希少型エンジニア育成スクール 私は最近、NHKの「笑わない数学」という番組を見ており、つくづく世界は数学でできていると思う。今週は第９回「暗号理論」についてまとめる。（NHKとは仲良くないし法に触れたくないので写真はない。） 途中の計算を飛ばすのがイヤだったため自分でチャレンジしてみたら、やたら時間がかかってしまった。せっかくなのでその辺も読んでもらえたら嬉しい。 現代はPCやスマホなどでメッセージ、個人情報をやり取りする機会が多く、それには暗号が使われている。どうして安全にそれが出来ているのか？そしてどんな数学が利用されて…
CakeCTF 2022 に、一人チームrotationで参加しました。そのwrite-up記事です。問題等は https://github.com/theoremoon/cakectf2022-public で公開されています。
目次へ余り演算とは次のようなもの a%b=aをbで割った余り 数学ではこの演算子よりも合同式を使われがちですが、コンピューター分野ではバリバリこっちです。 ただ、この％演算は処理しづらく、一度に複数組み込むと式が汚くなってしまいます。(処理すると可読性は下がります。注釈しましょう) しかし、調べてみると便利な性質を持つようなのでまとめました。結論から言うと次のような性質があります。 (名前は勝手につけました。ご指摘があればコメントよりお願い致しますm(_ _)m) 目次 基本則 a=[a/b]×b+a%b 周期性 (a+kb)%b=a%b 和の冪等性 (a+b)%c={(a%c)+b}%c 積…
〔 Hasse-Minkowski の定理, 局所大域原理〕 有理数を係数とする (斉次対角) 二次方程式が非自明有理数解を持つことは, それがあらゆる素数 𝒑 について非自明 𝒑 進数解を有し, かつ非自明実数解を有することと同値である.
〔 Ostrowski の定理〕あらゆる有理数上の絶対値は, 自明なる絶対値か, 符号無視の絶対値か, または或る素数に対応する 𝒑 進絶対値に同値である.
〔 Gauss-Legendre の三平方和定理〕正の整数 𝒏 が三つの平方数の和に表されるための必要充分条件は, 𝒏 から 4 を成るべく多く抽出して 𝒏 = 4ᵏℓ と書いたときに, \begin{align} \ell\not\equiv7\ \ (\mathrm{mod}.8) \end{align} になることである.
【問題】配列{"ドド","スコ"}からランダムに要素を標準出力し続け、『その並びが「ドドスコスコスコ」を3回繰り返したもの』に一致したときに「ラブ注入♡」と標準出力して終了するプログラムを作成せよ(配点:5点)— ((🐑++)) (@Sheeeeepla) 2022年8月1日 このプログラムにおいて, 配列{"ドド","スコ"}からランダムに要素を標準出力する回数の期待値を求めました. また, そのあと「ドド」の出る確率をとしたときの出力回数の期待値を求め, 「ドド」の出る確率を何にしたら期待値を最小にできるかを調べました.
"蔚来杯"2022牛客暑期多校训练营3_ACM/NOIP/NOI/CCPC/ICPC算法编程基础集训_牛客竞赛OJ 注（検索用）：Multi-Universities Campとか、TwitterではNowCoderとか呼ばれている中国の合宿の問題です。 問題概要 長さの順列に対し、をなる（）の個数として定めます。をランダムに決めたときのの期待値をで求めてください。 解法 準備 まずの場合は自明なので除きます。また素因数分解するとなので、素数についてで求めることができれば、中国剰余定理より答えが求まります。以降はこれらのことを前提にして解きます。 を求める 解説スライドによれば、を固定して完全…
余り演算とは次のようなもの a%b=aをbで割った余り 数学ではこの演算子よりも合同式を使われがちですが、コンピューター分野ではバリバリこっちです。 ただ、この％演算は処理しづらく、一度に複数組み込むと式が汚くなってしまいます。(処理すると可読性は下がります。注釈しましょう) しかし、調べてみると便利な性質を持つようなのでまとめました。 結論から言うと次のような性質があります。 (名前は勝手につけました。ご指摘があればコメントよりお願い致しますm(_ _)m) 目次 基本則 a=[a/b]×b+a%b 周期性 (a+kb)%b=a%b 和の冪等性 (a+b)%c={(a%c)+b}%c 積の冪…
入試において、説明が施された上で “ガウス記号” を用いた問題が時々出題されることがあります。記号は大カッコを用い、 「[x]=xを超えない最大の整数」 となります。負の数である場合は若干戸惑うこともあるかもしれませんが、当然ルールは同じです。「整数・小数部分」問題の際には、ガウス記号を用いると簡単に扱える場合があります。 【問題】 「nと[(3n+2)/2]の積が6の倍数（n:奇数）」(*1) となるとき、 「nはaで割ったときの余りがb」(*2) となり、 「(*2)となるとき(*1)となる」 とする。 このとき、a,bにあてはまる整数を求めよ。 但し、「0≦b＜a」とする。 ※[x]とは…
ツイート 西田和史(k.bigwheel) 開発基盤EM @ Speee ⌨️🖊️ @k_bigwheel ジルベールの事件、懐かしいなあ。 23:53 西田和史(k.bigwheel) 開発基盤EM @ Speee ⌨️🖊️ @k_bigwheel Git チュートリアル - .gitignoreファイル | Atlassian Git Tutorial https://www.atlassian.com/ja/git/tutorials/saving-changes/gitignore .git/info/exclude こんな機能があったのか。これは便利。 22:44 西田和史(k.bi…
アルゴリズムを学ぶのにPythonの学習も兼ねてＰｙｔｈｏｎで学ぶアルゴリズムとデータ構造 (データサイエンス入門シリーズ)作者:辻真吾講談社Amazonを参照していく。 前回 https://power-of-awareness.com/entry/2022/07/11/120000power-of-awareness.com 前回 9. 乱択アルゴリズムと数論 9.1 アルゴリズムと乱数 9.1.1 乱択アルゴリズムの例：クイックソート 9.1.2 乱択アルゴリズムの種類 9.1.3 例：面接試験 9.2 数論 9.2.1 合同式 9.2.2 フェルマーの小定理 9.2.3 冪乗と余り 9…
というのが一番やるべきことなわけで、いかにも出て来るやつらと言えば、 ・行列 ・整数(合同式とかも) ・ベクトル(内積外積とか面からの距離とか) ・指数対数 ・確率 ・微積(微分方程式、重積分とかも) あたりだが、行列の単純計算とか固有方程式使って固有値出すとかはだいぶ慣れた。 合同式もわりと覚えられるやつ。 ベクトルも難易度低い得点源。 指数対数もボーナス地域だ。 確率は時々普通の教科書に書いてないポアソン分布とかみたいな専門用語が出て来て目を眩まされる分野だが、実のとこただ単にそこに書いてある公式に数値を入れて計算してやればいいだけだったりする。 微積が一番難度の高い問題が出る確率高いが、…
manabitimes.jp
www.mkamimura.com
oto-suu.seesaa.net
