2018年11月12日 / 最終更新日時 : 2018年11月12日 arq 数学 ユークリッドの互除法 世界最古に発見されたアルゴリズムのひとつとして知られるユークリッドの互除法は, 歴史上の価値のみならず, 公約数という素因数が絡む計算を素因数分解せずに効率的に求めることができるという点で非常に有用な手法となっています. […]
2018年11月11日 / 最終更新日時 : 2018年11月11日 arq 数学 モジュラ逆数について 個人的メモ 法 m における整数 a のモジュラ逆数 a-1 (mod m) とは, aa-1≡1 (mod m) を満たす a-1≡x (mod m) なる整数 x の合同類である. 法 m における整数 a のモジュ […]
2018年11月11日 / 最終更新日時 : 2018年11月11日 arq 数学 合同式に関する諸性質 個人的なメモ フェルマーの小定理とは次の関係を言う: 素数 p と p とは互いに素な整数 a について ap-1≡1 (mod p) が成り立つ. 数論におけるオイラーの定理とは次の関係を言う: 任意の正の整数 n と […]