a ≡ b (mod n) m|n a ≡ b (mod m)

a ≡ b (mod n) c>0 ca ≡ cb (mod cn)

a b n
a ≡ b (mod n) a, b, n d>0 ≡ (mod )
d d d

a ≡ b (mod n) =⇒ a − b = kn k
m|n =⇒ n = rm r
∴ a − b = krm =⇒ a − b = sm
∴ a ≡ b (mod m)

a ≡ b (mod n)
a − b = kn k
∴ ca − cb = kcn
∴ ca ≡ cb (mod cn)

a ≡ b (mod n)
a − b = kn, k.

a = k1 d
a
∴ = k1
d

b = k2 d
b
∴ = k2
d

n = k3 d
n
∴ = k3
d

k1 d − k2 d = k(k3 d)
k1 − k2 = kk3 d
a b n
− =k
d d d
 a b n
∴ ≡ (mod ).
d d d
a ≡ b (mod n1 ) a ≡ b (mod n2 ) a ≡ b (mod n)
n= (n1 , n2 ) n1 n2 a ≡ b (mod n1 n2 )

a ≡ b (mod n1 ) a ≡ b (mod n2 ) a ≡ b (mod (n1 , n2 ))

a ≡ b (mod n1 ) a ≡ b (mod n2 ) a ≡ b (mod n1 n2 ) gcd(n1 , n2 ) = 1

k1 a ≡ b (mod n1 )
a − b = k1 n1
k2 a ≡ b (mod n2 )
a − b = k2 n2
d = gcd(n1 , n2 ) n1 = dr n2 = ds r, s gcd(r, s) = 1
n1
n1 = dr =⇒ =1
dr

a − b = k2 n2
a − b = k2 n2 · 1
n1
a − b = k2 n2 ·
dr
k2 n1 n2
a−b=
r d
gcd(a, b) = g (a, b) = l gl = ab gcd(a, b) (a, b) = ab

gcd(n1 , n2 ) (n1 , n2 ) = n1 n2
n1 n2
(n1 , n2 ) =
gcd(n1 , n2 )
n1 n2
∴ (n1 , n2 ) =
d

k2
a−b= (n1 , n2 )
r

a − b = k1 n1 = k2 n2
k1 n1 = k2 n2
k1 dr = k2 ds
k1 r = k2 s

k2
gcd(r, s) = 1 r|k2
r
a ≡ b (mod (n1 , n2 ))
a b gcd(a, b) = d = 1
k2 n1 n2
a−b=
r d
 k2 n1 n2
a−b=
r 1
k2
a − b = p · (n1 n2 ) [ =p ]
r
∴a≡b (mod n1 n2 )

x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 3 (mod 4)
x ≡ 4 (mod 5)
x ≡ 5 (mod 6)
x ≡ 0 (mod 7)

x ≡ 1 (mod 2) x ≡ 3 (mod 4)
x ≡ 3 (mod 4)
∴ x ≡ 3 (mod 2) [∵ a≡b (mod n) m|n, a≡b (mod m).]
x ≡ 1 (mod 2)
x ≡ 3 (mod 4) x ≡ 1 (mod 2) x ≡ 1 (mod 2)

x ≡ 2 (mod 3) x ≡ 5 (mod 6)
x ≡ 5 (mod 6)
∴ x ≡ 5 (mod 2) [∵ a≡b (mod n) m|n, a≡b (mod m).]
x ≡ 1 (mod 2)
x ≡ 5 (mod 6) x ≡ 2 (mod 3) x ≡ 2 (mod 3)
 x ≡ 3 (mod 4)
x ≡ 4 (mod 5)
x ≡ 5 (mod 6)
x ≡ 0 (mod 7)
gcd(4, 6) = 1
(4, 6) = 12
x ≡ 3 (mod 4)
3x ≡ 9 (mod 12) [ a≡b (mod n), c > 0, ca ≡ cb (mod cn).]
x ≡ 5 (mod 6)
2x ≡ 10 (mod 12) [ a≡b (mod n), c > 0, ca ≡ cb (mod cn).]

x ≡ −1 (mod 12)
∴ x ≡ 11 (mod 12)

x≡4 (mod 5)
x ≡ 11 (mod 12)
x≡0 (mod 7)
a1 = 4, a2 = 11 a3 = 0
M = 5 × 12 × 7 = 420

5 × 12 × 7
M1 = = 84
5
5 × 12 × 7
M2 = = 35
12
5 × 12 × 7
M3 = = 60
7

M1 x ≡ 1 (mod 5)
84x ≡ 1 (mod 5)
4x ≡ 1 (mod 5)
4x ≡ 16 (mod 5)
∴ x ≡ 4 (mod 5)

M2 x ≡ 1 (mod 12)
35x ≡ 1 (mod 12)
−x ≡ 1 (mod 12)
x ≡ −1 (mod 12)
∴ x ≡ 11 (mod 12)
 M3 x ≡ 1 (mod 5)
42x ≡ 1 (mod 5)
2x ≡ 1 (mod 5)
2x ≡ 6 (mod 5)
∴ x ≡ 3 (mod 5)

M4 x ≡ 1 (mod 7)
60x ≡ 1 (mod 7)
4x ≡ 1 (mod 7)
4x ≡ 8 (mod 7)
∴ x ≡ 2 (mod 7)
s1 = 4, s2 = 11 s3 = 2

x = a1 s1 M1 + a2 s2 M2 + a3 s3 M3 (mod M )
x = 4 × 4 × 84 + 11 × 11 × 35 + 0 × 2 × 42 + 0 × 3 × 60 (mod 420)
x = 1344 + 4235 + 0 (mod 420)
x = 5579 (mod 420)
∴ x = 119 (mod 420)

x ≡ 1 (mod 2)
x ≡ 1 (mod 3)
x ≡ 1 (mod 4)
x ≡ 1 (mod 5)
x ≡ 1 (mod 6)
x ≡ 0 (mod 7)

x ≡ 1 (mod 2) x ≡ 1 (mod 4)
x ≡ 1 (mod 4)
∴ x ≡ 1 (mod 2) [∵ a≡b (mod n) m|n, a≡b (mod m).]
x ≡ 1 (mod 4) x ≡ 1 (mod 2) x ≡ 1 (mod 2)
 x ≡ 1 (mod 3) x ≡ 1 (mod 6)
x ≡ 1 (mod 6)
∴ x ≡ 1 (mod 2) [∵ a≡b (mod n) m|n, a≡b (mod m).]
x ≡ 1 (mod 6) x ≡ 1 (mod 3) x ≡ 1 (mod 3)

x ≡ 1 (mod 4)
x ≡ 1 (mod 5)
x ≡ 1 (mod 6)
x ≡ 0 (mod 7)
gcd(4, 6) = 1
(4, 6) = 12
x≡1 (mod 4)
3x ≡ 3 (mod 12) [ a≡b (mod n), c > 0, ca ≡ cb (mod cn).]
x≡1 (mod 6)
2x ≡ 2 (mod 12) [ a≡b (mod n), c > 0, ca ≡ cb (mod cn).]

∴x≡1 (mod 12)

x ≡ 1 (mod 5)
x ≡ 1 (mod 12)
x ≡ 0 (mod 7)
a1 = 1, a2 = 1 a3 = 0
M = 5 × 12 × 7 = 420

5 × 12 × 7
M1 = = 84
5
5 × 12 × 7
M2 = = 35
12
5 × 12 × 7
M3 = = 60
7

M1 x ≡ 1 (mod 5)
84x ≡ 1 (mod 5)
4x ≡ 1 (mod 5)
4x ≡ 16 (mod 5)
∴ x ≡ 4 (mod 5)

M2 x ≡ 1 (mod 12)
 35x ≡ 1 (mod 12)
−x ≡ 1 (mod 12)
x ≡ −1 (mod 12)
∴ x ≡ 11 (mod 12)

M3 x ≡ 1 (mod 5)
42x ≡ 1 (mod 5)
2x ≡ 1 (mod 5)
2x ≡ 6 (mod 5)
∴ x ≡ 3 (mod 5)

M4 x ≡ 1 (mod 7)
60x ≡ 1 (mod 7)
4x ≡ 1 (mod 7)
4x ≡ 8 (mod 7)
∴ x ≡ 2 (mod 7)
s1 = 4, s2 = 11 s3 = 2

x = a1 s1 M1 + a2 s2 M2 + a3 s3 M3 (mod M )
x = 1 × 4 × 84 + 1 × 11 × 35 + 0 × 2 × 42 + 0 × 3 × 60 (mod 420)
x = 336 + 385 + 0 (mod 420)
x = 721 (mod 420)
∴ x = 301 (mod 420)

x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 5 (mod 6)
x ≡ 5 (mod 12)
 x ≡ 1 (mod 2) x ≡ 5 (mod 1)2
x ≡ 5 (mod 12)
x ≡ 5 (mod 2)
∴ x ≡ 1 (mod 2) [∵ a≡b (mod n) m|n, a≡b (mod m).]
x ≡ 5 (mod 12) x ≡ 1 (mod 2) x ≡ 1 (mod 2)

x ≡ 2 (mod 3) x ≡ 5 (mod 1)2

x ≡ 5 (mod 12)
x ≡ 5 (mod 3)
∴ x ≡ 2 (mod 3) [∵ a≡b (mod n) m|n, a≡b (mod m).]
x ≡ 5 (mod 12) x ≡ 2 (mod 3) x ≡ 2 (mod 3)

x ≡ 5 (mod 6) x ≡ 5 (mod 12)

x ≡ 5 (mod 12)
∴ x ≡ 5 (mod 6) [∵ a≡b (mod n) m|n, a≡b (mod m).]
x ≡ 5 (mod 12) x ≡ 5 (mod 6) x ≡ 5 (mod 6)

x ≡ 5 (mod 12)
 p k 1 ≤ k ≤ p−1

p−1
≡ (−1)k (mod p).
k

p−1 (p − 1)!
=
k k!(p − 1 − k)!
(p − 1)!
=
k!(p − (k + 1))!
1 · 2 · 3 · · · (p − (k + 1))(p − k)(p − (k − 1))(p − (k − 2)) · · · (p − 3)(p − 2)(p − 1)
=
1 · 2 · 3 · · · (p − (k + 1))
(p − 1)(p − 2) · · · (p − k)
=
k!
p−1
∴ K! = (p − 1)(p − 2) · · · (p − k)
k

(p − 1)(p − 2) · · · (p − k) ≡ (−1)(−2) · · · (−k) (mod p)

p−1
K! ≡ (−1)k K! (mod p)
k
1 ≤p−1 ≥k p−1 >1 p>k
∴ p 1, 2, 3, . . . , k gcd(p, k!) = 1
p−1
∴ ≡ (−1)k (mod p).
k