ab (mod m)פϡa=b+km,kZפƱ̣Ǥ롣δط̲ǰ;residue classȸƤФ롣
[]
a mod mξ;פȸƤ֡
㡧
mod mξ;ΤνγǰȤСˤ̤ȸ롣Ĥޤꡢ
Ǥꡢ;ȸƤФ졢
Ȥɽ롣
[]ͭ½ʤΤǡ䤹
;Ϥϼ¼Ū˹ƱƱ
ȽҤ٤뤫
ˤ
ȽҤ٤뤫ΰ㤤Ǥ롣
Ʊ | ; | |
θǤƽAi̵½Ǥ롣
[]ϰ̣ޤäۤʤ롣黻ȤǤϤȤƤƤ롣
ʤΤǡmĤǤġ
ϡʲˡФơ˷¤ĤΤǡ;ෲȸƤФ롣
[];ෲȽ
ˤ̡¨;ෲ
ϲˡǤ롣
Ƹ٤黻ơ٤Ƥθ뤳ȤΤФ褤
㡧Ȥ
ˡǤ뤳ȤĴ٤롣
ñ̸Ǥ롣
ꡢޤ
ȤǤ롣
[]
pǿȤȤ0
ɽ
ѤˤĤĤƤ롣
ʢж
ǡꡢ
äơ
Ȥ롣
ǡfa=ax롣
ѤˤĤĤƤΤǡfaϼǤ롣
[]
pǿ
ñ
[]ˡѤ롣
ΩĤȲꤹ롣
ʢZ/pZa0
̷⡣
äơ
fañ͡
[]
pǿ
ñ
[]嵭η̤ꡢfañ
ޤfaͭ½餽켫ȤؤμǤ롣
äơfañͤǤ롣
[]
pǿȤ롣
ΤȤ
ϼΤ褦ˤ롣
[]
pǿȤ롣
ΤȤǤϡ
ˤƵոġ
[]Ȥ
ñ
ޤ1Bfa͡פꡢ
ˡfañͤꡢΤ褦xϤĤΤߤǤ롣
եޡξɽȼΤ褦ˤʤ롣
[]
pǿȤȡ
Ωġ
[]fañͤꡢϡ
¤ؤ˲ʤ
ʢZ/pZעʡ(p-1)!0ס
[]ǤΤmȸߤǤʤΤ
ɽ롣
ȡpǿˤΤȤƱͤˡ
mǿ뤤ϹˤѤˤĤĤƤ롣
ˤĤƤ⡢
ƱͤʥȡǥեޡξޤǼȤǤΤ
1ФơfañͤǤ뤳Ȥ
2faͭ½礫鼫ȤؤñͤʤΤǡfañ
3Ȥơ
ɽȤˤ롣
fañͤꡢ¤Ѥ˲ʤ
Ȥ
4ˤơ
Ф褤
ϸȡб롣
Υȡˤϥƥå1Ǥ롣ޤƥå1ͻ롣
Ȳꤹ롣
ˤơ
ʤ
ʤС
̷⤹Τǡfañͤˤʤ롣
ʾˤꡢʤС
Ωġ顼Ȥ
ˡlα硦顼ؿȰפ롣
äơΤ褦˸롣
[]顼