← Topic 2 · Number Theory
AMC 10/12 · Cheatsheet
Topic 2 · Number Theory
Chapter 3 · Advanced: Fermat, Euler & CRT
🖨 Print / PDF
📋 Reference · always available
Fermat
a
p
−
1
≡
1
(
m
o
d
p
)
(
p
∤
a
)
a^{p-1}\equiv 1 \pmod p\;(p\nmid a)
a
p
−
1
≡
1
(
mod
p
)
(
p
∤
a
)
Euler
a
ϕ
(
n
)
≡
1
(
m
o
d
n
)
(
gcd
(
a
,
n
)
=
1
)
a^{\phi(n)}\equiv 1 \pmod n\;(\gcd(a,n)=1)
a
ϕ
(
n
)
≡
1
(
mod
n
)
(
g
cd
(
a
,
n
)
=
1
)
Totient
ϕ
(
p
e
)
=
p
e
−
1
(
p
−
1
)
\phi(p^e)=p^{e-1}(p-1)
ϕ
(
p
e
)
=
p
e
−
1
(
p
−
1
)
CRT
Coprime moduli
⇒
\Rightarrow
⇒
unique solution mod their product.