同余：
兩個整數
a
,
b
a,b
a,b，若它們除以整數
m
m
m所得的余數相等，則稱
a
a
a同余于
b
b
b模
m
m
m，
記作：
a
≡
b
(
m
o
d
??
m
)
a≡b (\mod m)
a≡b(modm)
歐拉定理：
如果
n
n
n和
a
a
a互質，則有
a
φ
(
n
)
≡
1
(
m
o
d
??
n
)
a^{\varphi(n)}\equiv 1(\mod n)
aφ(n)≡1(modn)
證明：
在
1
～
n
1\sim n
1～n中，所有與
n
n
n互質的數為
a
1
,
a
2
,
.
.
.
,
a
φ
(
n
)
?
?
?
?
?
①
a_1,a_2,...,a_{\varphi(n)}·····①
a1?,a2?,...,aφ(n)??????①
∵
∵
∵
a
a
a與
n
n
n互質
∴
a
?
a
1
,
a
?
a
2
,
.
.
.
,
a
?
a
φ
(
n
)
均
與
n
互
質
?
?
?
?
?
②
∴a*a_1,a*a_2,...,a*a_{\varphi(n)}均與n互質·····②
∴a?a1?,a?a2?,...,a?aφ(n)?均與n互質?????②
①
①
①式與
②
②
②式
%
n
\%n
%n相同，順序可能不同，
證明：
假設
a
?
a
i
≡
a
?
a
j
(
m
o
d
??
n
)
,
i
≠
j
a*a_i\equiv a*a_j(\mod n),i≠j
a?ai?≡a?aj?(modn),i?=j
消去
a
a
a,得
a
i
≡
a
j
(
m
o
d
??
n
)
,
與
①
矛
盾
a_i\equiv a_j(\mod n),與①矛盾
ai?≡aj?(modn),與①矛盾
證畢，
令
①
①
①的所有數乘積
=
②
=②
=②的所有數乘積：
a
1
?
a
2
?
?
?
a
φ
(
n
)
=
a
φ
(
n
)
?
a
1
?
a
2
?
?
?
a
φ
(
n
)
(
m
o
d
??
n
)
a_1·a_2···a_{\varphi(n)}=a^{\varphi(n)}·a_1·a_2···a_{\varphi(n)}(\mod n)
a1??a2????aφ(n)?=aφ(n)?a1??a2????aφ(n)?(modn)
消去
a
1
?
a
2
?
?
?
a
φ
(
n
)
a_1·a_2···a_{\varphi(n)}
a1??a2????aφ(n)?得
a
φ
(
n
)
≡
1
(
m
o
d
??
n
)
a^{\varphi(n)}\equiv 1(\mod n)
aφ(n)≡1(modn)
證畢，
費馬小定理：
在歐拉定理中，若
n
n
n為質數
p
p
p,即
a
φ
(
p
)
≡
1
(
m
o
d
??
p
)
a^{\varphi(p)}\equiv 1(\mod p)
aφ(p)≡1(modp)
∵
φ
(
p
)
=
p
?
1
∵\varphi(p)=p-1
∵φ(p)=p?1
∴
a
p
?
1
≡
1
(
m
o
d
??
p
)
∴a^{p-1}\equiv 1(\mod p)
∴ap?1≡1(modp)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/257853.html
標籤：區塊鏈