ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

;

ab (mod m)פϡa=b+km,kZפƱ̣Ǥ롣δط̲ǰ;residue classȸƤФ롣

[]
\{~b|~b~\equiv~a~\,~(mod\,~m~)~\}~=~a+mZ򡢡a mod mξ;פȸƤ֡

  • 1 mod 3ξ;ס{1,13,123,133,}={1,-2,4,-5,7,10,}
  • 0 mod 2ξ;סֶΤν
  • 1 mod 2ξ;סִΤν

;

mod mξ;ΤνγǰȤС\mathbb{Z}m~\mathbb{Z}ˤ̤ȸ롣Ĥޤꡢ\mathbb{Z}/m\mathbb{Z}Ǥꡢ;ȸƤФ졢\mathbb{Z}_mȤɽ롣

\mathbb{Z}/m\mathbb{Z}~=~\mathbb{Z}_m=~\{A_0,A_1,\cdots,A_{m-1}\}

[]\mathbb{Z}_mͭ½ʤΤǡ䤹

;Ϥ˱黻

;ϤȹƱ

;Ϥϼ¼Ū˹ƱƱ

a+b~\equiv~c~\pmod{n}

ȽҤ٤뤫

\mathbb{Z}/n\mathbb{Z}ˤa+b=c

ȽҤ٤뤫ΰ㤤Ǥ롣

Ʊ;
\mathbb{Z}̵½\mathbb{Z}/n\mathbb{Z}ͭ½

\mathbb{Z}/n\mathbb{Z}θǤƽAi̵½Ǥ롣

[]\mathbb{Z}\mathbb{Z}/n\mathbb{Z}ϰ̣ޤäۤʤ롣黻ȤǤϤȤƤƤ롣

;ෲ

\mathbb{Z}_m\{A_0,A_1,\cdots,A_{m-1}\}=mʤΤǡmĤǤġ

\sharp~(\mathbb{Z}_m)=~\sharp~\{A_0,A_1,\cdots,A_{m-1}\}=m

\mathbb{Z}_mϡʲˡФơ˷¤ĤΤǡ;ෲȸƤФ롣

[];ෲȽ

\mathbb{Z}n~\mathbb{Z}ˤ̡¨;ෲ\mathbb{Z}~/~n~\mathbb{Z}~(=~\mathbb{Z}_n)ϲˡ󷲤Ǥ롣

Ƹ٤黻ơ٤Ƥθ뤳ȤΤФ褤

\mathbb{Z}_3=\{~A_0,A_1,A_2~\}Ȥ(\mathbb{Z}_3;+)ˡ󷲤Ǥ뤳ȤĴ٤롣

ñ̸A_0Ǥ롣

  • 1A_0=A_0
  • 1A_1=A_1,\;~2A_1=A_1+A_1=A_2,\;~3A_1=A_1+A_1+A_1=A_3=A_0
  • 1A_2=A_2,\;~2A_2=A_2+A_2=A_4=A_1,\;~3A_2=A_2+A_2+A_2=A_6=A_0

\mathbb{Z}_3A_1ޤA_2Ȥ󷲤Ǥ롣

ˡǿξ;Ϥ0

[]
pǿȤȤ\mathbb{Z}/p\mathbb{Z}~=~\{~0,1,~\cdots,~p-1~\}0\{1,2,\cdots,p-1\}(\mathbb{Z}/p~\mathbb{Z})^{*}ɽ

ѤˤĤĤƤ

(\mathbb{Z}/p~\mathbb{Z})^{*}ѤˤĤĤƤ롣

\mathbb{Z}/p\mathbb{Z}
a,b~\in~\mathbb{Z}/p\mathbb{Z};~ab=0~\Rightarrow~a=0~\vee~b=0
a,b~\in~\mathbb{Z}/p\mathbb{Z};~a~\not{=}~0~\wedge~b~\not{=}~0~\Rightarrow~ab~\not{=}0ʢж

ǡ(\mathbb{Z}/p~\mathbb{Z})^{*}~\not{\ni}~0a,b~\in~(\mathbb{Z}/p\mathbb{Z})^{*};~ab~\not{=}0

äơab~\in~(\mathbb{Z}/p~\mathbb{Z})^{*}

fañ

a~\in~(\mathbb{Z}/p~\mathbb{Z})^{*}Ȥ롣

ǡa~\in~(\mathbb{Z}/p~\mathbb{Z})^{*}a~\in~(\mathbb{Z}/p~\mathbb{Z})^{*}fa=ax롣

(\mathbb{Z}/p~\mathbb{Z})^{*}ѤˤĤĤƤΤǡfaϼǤ롣

[]
pǿ
\forall~a~\in~(\mathbb{Z}/p~\mathbb{Z})^{*}~;~f_a~:~(\mathbb{Z}/p~\mathbb{Z})^{*}~\rightarrow~(\mathbb{Z}/p~\mathbb{Z})^{*}ñ

[]ˡѤ롣

x_1,x_2~\in~(\mathbb{Z}/p~\mathbb{Z})^{*}~\wedge~x_1~\not{=}~x_2;~f_a(x_1)=f_a(x_2)ΩĤȲꤹ롣

ax_1=ax_2
ax_1-ax_2=0
a(x_1-x_2)=0
x_1-x_2=0ʢZ/pZa0
x_1=x_2

̷⡣

äơx_1,x_2~\in~(\mathbb{Z}/p~\mathbb{Z})^{*}~\wedge~x_1~\not{=}~x_2
f_a(x_1)~\not{=}~f_a(x_2)
fañ͡

[]
pǿ
\forall~a~\in~(\mathbb{Z}/p~\mathbb{Z})^{*}~;~f_a~:~(\mathbb{Z}/p~\mathbb{Z})^{*}~\rightarrow~(\mathbb{Z}/p~\mathbb{Z})^{*}ñ

[]嵭η̤ꡢfañ

ޤfaͭ½(\mathbb{Z}/p~\mathbb{Z})^{*}餽켫ȤؤμǤ롣

äơfañͤǤ롣

ո¸

[]
pǿa~\in~(\mathbb{Z}/p\mathbb{Z})^{*}Ȥ롣 ΤȤ\exists~x~\in~(\mathbb{Z}/p\mathbb{Z})^{*}~\,~s.t.~\,~ax=1

ϼΤ褦ˤ롣

[]
pǿȤ롣 ΤȤ(\mathbb{Z}/p\mathbb{Z})^{*}Ǥϡ(\mathbb{Z}/p\mathbb{Z})^{*}ˤƵոġ

[]A=B=(\mathbb{Z}/p\mathbb{Z})^{*}Ȥ

f_a~:~A~\rightarrow~Bñ

ޤ1Bfa͡פꡢ\exists~x~\in~A~\,~s.t.~\,~f_a(x)=1

ˡfañͤꡢΤ褦xϤĤΤߤǤ롣

եޡξ

եޡξ\mathbb{Z}/p\mathbb{Z}ɽȼΤ褦ˤʤ롣

[]
pǿa~\in~(\mathbb{Z}/p\mathbb{Z})^{*}Ȥȡa^{p-1}~=~1Ωġ

[]fañͤꡢf_a(1),f_a(2),\cdots,f_a(p-1)ϡ(\mathbb{Z}/p\mathbb{Z})^{*}\{~1,2,\cdots,~p-1~\}¤ؤ˲᤮ʤ

f_a(1)~\times~f_a(2)~\times~\cdots~\times~f_a(p-1)~=~1~\times~2~\times~\cdots~\times~(p-1)
(a~\cdot~1)~\times~(a~\cdot~2)~\times~\cdots~\times~(a~\cdot~(p-1))~=~1~\times~2~\times~\cdots~\times~(p-1)
a^{p-1}~\cdot~(p-1)!~=~(p-1)!
a^{p-1}~\cdot~(p-1)!~-~(p-1)!=0
(a^{p-1}~-1)(p-1)!=0
a^{p-1}~-1=0ʢZ/pZעʡ(p-1)!0ס
a^{p-1}~=1

;ϤǤΤˡǤʤΤ򽸤᤿

[]\mathbb{Z}/m\mathbb{Z}ǤΤmȸߤǤʤΤ򽸤᤿(\mathbb{Z}/m\mathbb{Z})^{*}ɽ롣

ȡ(\mathbb{Z}/p\mathbb{Z})^{*}pǿˤΤȤƱͤˡ(\mathbb{Z}/m\mathbb{Z})^{*}mǿ뤤ϹˤѤˤĤĤƤ롣

(\mathbb{Z}/m\mathbb{Z})^{*}ˤĤƤ⡢(\mathbb{Z}/p\mathbb{Z})^{*}Ʊͤʥȡ꡼ǥեޡξޤǼȤǤΤ

1a~\in~(\mathbb{Z}/m\mathbb{Z})^{*}ФơfañͤǤ뤳Ȥ򼨤

2faͭ½礫鼫ȤؤñͤʤΤǡfañ

3\sharp~\{~(\mathbb{Z}/m\mathbb{Z})^{*}~\}~:=~lȤơ(\mathbb{Z}/m\mathbb{Z})^{*}~=~\{~a_1,\cdots,a_l~\}ɽȤˤ롣

fañͤꡢf_a(a_1),\cdots,f_a(a_l)a_1,\cdots,a_l¤Ѥ˲᤮ʤ

K(a^l-1)=0K=a_1~\times~\cdots~\times~a_lȤ

4\mathbb{Z}/m\mathbb{Z}ˤơa^l~=~0Ф褤

ϸȡa^l~\equiv~1~\pmod{m}б롣

Υȡ꡼ˤϥƥå1Ǥ롣ޤƥå1ͻ롣

x_1,x_2~\in~(\mathbb{Z}/m\mathbb{Z})^{*}~\wedge~x_1~\not{=}~x_2~\Rightarrow~f_a(x_1)=f_a(x_2)Ȳꤹ롣

\mathbb{Z}/m\mathb{Z}ˤơax_1=ax_2
a(x_1-x_2)=0
x_1-x_2=0ʤ(a,m)=1ʤС
x_1=x_2

̷⤹Τǡfañͤˤʤ롣

ʾˤꡢ(a,m)=1ʤСa^l=1ΩġȤ

ˡlα硦顼ؿȰפ롣

l~=~\phi~(m)

äơΤ褦˸롣

[]顼
(a,m)=1~\Rightarrow~a^{\phi~(m)}~\equiv~1~\pmod{m}