【２】平方剰余と原始根

［１］ｘ^2＋１＝０　　　（ｍｏｄ　ｐ）はｐが４ｍ＋１の形をしているとき，そのときに限り解ける．

　合同式が解けるための条件は

　　（－１／ｐ）＝（－１）^(p-1)/2

［２］ｘ^2＋２＝０　　　（ｍｏｄ　ｐ）はｐが８ｍ＋１または８ｍ＋３の形をしているとき，そのときに限り解ける．

　合同式が解けるための条件は

　　（２／ｐ）＝（－１）^(p^2-1)/8

［３］ｘ^2＋３＝０　　　（ｍｏｄ　ｐ）はｐが６ｍ＋１の形をしているとき，そのときに限り解ける．

　合同式は（－３／ｐ）＝１ととき，そのときに限り解ける．

　　（－３／ｐ）＝（ｐ／３）

　　ｐが６ｍ＋１の形のとき１，６ｍ＋５の形のとき－１

［４］３はｐ＝２^n＋１，ｎ＞１という形の任意の素数の原始根である．

　　（ｇ／２^n＋１）＝－１でなければならないが，ｇ＝３はこの要求を満足させる．

［５］２はｐ＝２ｍ＋１，ｍ＝４ｎ＋１という形の任意の素数の原始根である．－２はｐ＝２ｍ＋１，ｍ＝４ｎ＋３という形の任意の素数の原始根である．

　　（ｇ／２ｍ＋１）＝１，ｇ^2＝１（ｍｏｄ２ｍ＋１）となることは許されないが，これらはこの要求を満足させる．

［６］２はｐ＝４ｍ＋１という形の任意の素数の原始根である．

　　（ｇ／４ｍ＋１）＝１，ｇ^4＝１（ｍｏｄ４ｍ＋１）となることは許されないが，ｇ＝２はこの要求を満足させる．

［７］３はｐ＝２^nｍ＋１，ｎ＞１，ｍ＞３^2^(n-1)／２^nという形の任意の素数の原始根である．

　　（ｇ／２^nｍ＋１）＝１，ｇ^2^n＝１（ｍｏｄ２^nｍ＋１）となることは許されないが，ｇ＝３はこの要求を満足させる．

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