モジュラー算術では

　　ａ＝ｂ　（ｍｏｄｍ），ｃは整数

→ａ＋ｃ＝ｂ＋ｃ　（ｍｏｄｍ），ａｃ＝ｂｃ　（ｍｏｄｍ）

　　ａ＝ｂ　（ｍｏｄｍ），ｃ＝ｄ　（ｍｏｄｍ）

→ａ＋ｃ＝ｂ＋ｄ　（ｍｏｄｍ），ａｃ＝ｂｄ　（ｍｏｄｍ）

　　ａ＝ｂ　（ｍｏｄｍ）

→ａ^2＝ｂ^2，ａ^3＝ｂ^3，・・・，ａ^n＝ｂ^n　（ｍｏｄｍ）

ｍが大きい場合の計算例を掲げたい。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［Ｑ］１９ｘ＝１　　（ｍｏｄ１４０）の解を求めよ．

［Ａ］法１４０の素因子２に関して，ｘ＝１　（ｍｏｄ２）であるから，ｘ＝２ｙ＋１を１９ｘ＝１　　（ｍｏｄ１４０）に代入すると

　　３８ｙ＋１９＝１　　（ｍｏｄ１４０）

　　３８ｙ＝－１８　　（ｍｏｄ１４０）

　　１９ｙ＝－９　　（ｍｏｄ７０）

法７０の素因子２に関して，ｙ＝１　（ｍｏｄ２）であるから，ｙ＝２ｚ＋１を３８ｙ＝－１８　　（ｍｏｄ１４０）に代入すると

　　７６ｚ＋３８＝－１８　　（ｍｏｄ１４０）

　　７６ｚ＝－５６　　（ｍｏｄ１４０）

　　１９ｚ＝－１４　　（ｍｏｄ３５）

法３５の素因子５に関して，ｚ＝４　（ｍｏｄ５）であるから，ｚ＝５ｗ＋４を１９ｚ＝－１４　　（ｍｏｄ３５）に代入すると

　　９５ｗ＋７６＝－１４　　（ｍｏｄ３５）

　　９５ｗ＝－９０　　（ｍｏｄ３５）

　　１９ｗ＝－１８　　（ｍｏｄ７）

法７は素数で，すぐにｗ＝２　　（ｍｏｄ７）がみつかる．ｗ＝７ｕ＋２

　　ｘ＝２ｙ＋１

　　ｙ＝２ｚ＋１

　　ｚ＝５ｗ＋４

　　ｗ＝７ｕ＋２

ｘ＝２ｙ＋１＝２（２ｚ＋１）＋１＝４ｚ＋３＝４（５ｗ＋４）＋３

＝２０ｗ＋１９＝２０（７ｕ＋２）＋１９＝１４０ｕ＋５９

　以上より，ｘ＝５９　　（ｍｏｄ１４０）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝