• ゲーム類
  • 漫画書評
  • 物情報材
  • 思想評論
  • 統計推論
  • 二次創作
  • 馬鹿企画
  • 数論入門
  • 歴史入門
  • 日々雑感
中国人の剰余定理から合同方程式の単純な解法まで

ゲヲログ2.0

ホーム
数論入門

中国人の剰余定理から合同方程式の単純な解法まで

2018/6/23 2020/6/25 数論入門

シェアする

  • LINE!

「中国人の剰余定理」ではこんな例がある。

x≡2 (mod3)
x≡3 (mod5)
を満たすxを求めよ。

このとき3*5を法とするただひとつのxの値を求められる。

3X+5Y=1を満たすX・Yはユークリッド互除法によれば…(勘を頼りに)
X=2,Y=-1
よって、求めるx=2*5*(-1)+3*3*2=8 これは3*5=15を法としてただ一つである。

すなわちmod15としてその範囲(15未満)にてただ一つである。だがちょっと待ってほしい、さらに深めていこう。ではこれをさらに深く追い求めて、変数を活用して、合同連立式として解を得ることにしてみると…

x≡2 (mod3)のとき、x=3y+2と表せる。・・・(1)
変形してx≡3(y-1) (mod5)
x=5z+3 従って x≡3 (mod5)・・・これは条件を満たしている。さらに変形して…
x=3(y-1)+5従ってy=5z+2・・・(1)
(1)に(2)を代入して…
x=3(5z+2)+2=15z+8
x≡8 (mod15)

ついでに言っておくとこいつもこう整理できる。

x≡2 (mod3)のとき、x=3n+2 and n∈Z (nは整数の集合Zに属する)

https://www.wolframalpha.com/input/?i=solve+x%E2%89%A12+(mod3)より確認

合わせて読みたい:

  1. ランチェスターの法則【戦略シミュレーションと実戦】 フレデリック・ランチェスターがオペレーションズリサーチの鏑矢として打ち立てた法則がある。これがいわゆる「ランチェスターの法則」である。法則は......
  2. 合同式・ユークリッドの互除法・オイラーの定理 整数論の序論は暗号理論にとって大切である。今回は特に古典的整数論によって、ユークリッドの互除法を証明するあたりから、オイラーの定理を簡潔に解......
  3. 初期の暗号―シーザー暗号と多表式暗号 一番有名な古典的な暗号はシーザー暗号であり、これは平文と鍵および暗号文を単一の文字に対応させたものである。いうなれば多表式暗号に対して単表式......
  4. 公開鍵暗号の主流方式RSA暗号の数論的解説 公開鍵暗号は複雑な経緯があるが、話をはしょってしまえば簡単だ。要するに共通の鍵ではなく、二つの鍵を使い、また公開鍵方式だから一方の鍵を公開し......
  5. ゼロ知識証明の定義と簡単な説明―「洞窟の問題」 ゼロ知識証明(zero-knowledge proof)は簡単に洞窟の問題として語り継がれている。子供にゼロ知識証明を教えるにあたって、ハミ......
  6. 協力ゲームと非協力ゲームから考える男女の付き合い方 A(映画館好き男) B(美術展好き女) 映画館 美術展 映画館 (2,1) (-1,-1) 美術展 (-1,-1) (1,2)...
  7. 「囚人のジレンマ」非協力ゲームにおけるナッシュ均衡かつ非パレート最適の選択 囚人A/囚人B 協力(妥協) 裏切り(自白) 協力(妥協) (1,1) (3,0) 裏切り(自白) (0,3) (2,2) ゲーム理論におけ......
  8. ミニマクス戦略およびフォークの定理の一歩目 ゼロサムゲームにおいて、次のような意思決定マトリックスを考える(このとき展開ゲームであり、このゲームはさらに完全情報ゲームである)。完全情報......

AyanoJun

合同式・ユークリッドの互除法・オイラーの定理
初期の暗号―シーザー暗号と多表式暗号

ご説明

ワチャワチャ騒ぎながらワチャワチャ勉強する秘密基地サイト(機械学習のための教師データサイト)。ご連絡は下記渉外課まで☟

管理人:綾野純
Tweet to @metta2tubuyak71
副管理人:fame(ファメルス)...ゲヲログ(1.0)管理人兼任
Tweet to @hanbun_bot

人気の投稿

  • synctam氏、BG3日本語化情報をブログに掲載
  • Steamerに「Hades」よりも「Curse of the Dead Gods」をお勧めする理由
  • 放送大学大学院はレベルが高い
  • 「ADOM」ローグライク最高傑作、アルティメットverになり”帰還”…
  • synctam氏、BG3日本語化情報をブログに掲載 続き(3)
  • 世界最強の射撃系ローグライト「SYNTHETIK」の正当な続編「SYNTHETIK 2」EAリリースアナウンス
  • Steamゲームレビュー「Nigate Tale」完成度を極限まで上げてほしいEAタイトル
  • カードデッキ系RPG「Chrono Ark」詳解プレイレポート 序盤~中盤の攻略『修行の章』
  • Steamerに「Hades」よりも「Dreamscaper」をお勧めする理由
  • Steamで『圧倒的に好評』タイトルの傾向を”主観的に”読み解く

最近の投稿

  • radikoによるインターフェース革命
  • 神々による神々しい神ゲー「Godstrike」ゲームレビュー
  • 「MotoGP 21」発売直前にシリーズ前四作のデータを振り返る
  • 世界で最も面白そうなデッキビルド型2Dシューター「マナザレイヲ」蓮太(ばすたー)氏によって鋭意開発情報報告中…
  • 国立夜間主コースも含めて夜間大学の社会的評価は低い
  • 漫画レビュー「ダンベル何キロ持てる?」
  • 『タクティカルベース戦略ゲーム』の憂鬱
  • 世界最強の射撃系ローグライト「SYNTHETIK」の正当な続編「SYNTHETIK 2」EAリリースアナウンス
  • Steamゲームレビュー「Nigate Tale」完成度を極限まで上げてほしいEAタイトル
  • 「DigiPen Institute of Technology(デジペン工科大学)」とは何者か?

カウンター

訪問者数:

現在の閲覧者数:

Public Domain ゲヲログ2.0 No Rights Reserved.