Ć n " N
Ć(n) = #{k : NW D(k, n) = 1, 1 d" k d" n - 1}
a, n " N NW D(a, n) = 1
aĆ(n) a" 1
a, p " N p
NW D(a, p) = 1
ap-1 a" 1
n = p Ć(p) = p - 1
ax + by = c
a, b, c, x, y " Z
g = NW D(a, b) a, b = 0 g

ax + by x, y " Z
S = {ax + by : x, y " Z} S
l = ax0 + by0 x0, y0 " Z
x, y " N ax + by e" 0
S )" N = " l = g NW D(a, b)

l|a
 a = kl + r 0 d" r < l
r = a - lk = a - k(ax0 + by0) = a(1 - kx0) + b(-ky0)
r " S l S
l|b
b = sl + r 0 d" r < l
r = a - ls = a - s(ax0 + by0) = a(1 - sx0) + b(-sy0)
r " S l S
l a b
g a b a = gc b = gd c, d " Z
l = ax0 + by0 = gcx0 + gdy0 = g(cx0 + dy0)
g|l g = NW D(a, b)
a b g = l
ax + by = c
c = NW D(a, b) x, y " Z
S = ax + by : x, y " Z
NW D(a, b)
ax + by = c
x, y " Z NW D(a, b)|c
NW D(a, b)|c ax + by = c
c = NW D(a, b)k k " Z
ax + by = NW D(a, b)
x0, y0 " Z ax0 + by0 = NW D(a, b)
k kx0, ky0 ax + by = c
ax+by = c NW D(a, b)|c
NW D(a, b) c
ax + by = c
x , y " Z ax + by = c c = (NW D(a, b))k + r
0 < r < NW D(a, b)
ax + by = kNW D(a, b) x0, y0
ax0 + by0 = kNW D(a, b)
ax + by = c ax0 + by0 = kNW D(a, b)
a(x - x0) + b(y - y0) = r
r " S = ax + by : x, y " Z
NW D(a, b) S
a, b " Z NW D(a, b)|c
ax + by = c
b
x = x0 + t
NW D(a, b)
a
y = y0 - t
NW D(a, b)
t " Z x0, y0
ax + by = c
x, y
x0, y0 ax+by = c ax0+by0 =
c x , y ax + by = c
ax + by = ax0 + by0
a(x - x0) = b(y0 - y )
NW D(a, b)|a NW D(a, b)|b
a b
(x - x0) = (y0 - y )
NW D(a, b) NW D(a, b)
a b
NW D(NW D(a,b), ) = 1
NW D(a,b)
a b
b
( )|(x - x0)
NW D(a, b)
a
( )|(y0 - y )
NW D(a, b)
t " Z
b
x - x0 = t
NW D(a, b)
a
y0 - y = t
NW D(a, b)
x , y
b
x = x0 + t
NW D(a, b)
a
y = y0 - t
NW D(a, b)
ax+by = c
ax a" b a, b, n "
Z x
ax1 a" b
ax2 a" b
x1 x2 x1 a" x2
ax a" b a, b, n " Z NW D(a, n)|b
NW D(a, n)
ax0 a" b x0 0 d" x0 d" n - 1
n n
M = {x0, x0 + , . . . , x0 + (NW D(a, n) - 1) }
NW D(a, n) NW D(a, n)
ax a" b
ax + ny = b
NW D(a, n)|b x0, y0
ax + ny = b
n
x = x0 + t
NW D(a, n)
a
y = y0 - t
NW D(a, n)
n
t " Z x a" x0
NW D(a,n)
n
x 0 d" x d" - 1 NW D(a, n)
NW D(a,n)
n
x = x + k
NW D(a, n)
k = 0, 1, . . . , NW D(a, n) - 1 {0, 1, . . . , n -
1}
n n
x + k a" x + l
NW D(a, n) NW D(a, n)
n n
k a" l
NW D(a, n) NW D(a, n)
n
n| (k - l)
NW D(a, n)
n
(k - l) = ns
NW D(a, n)
s " Z 0 d" k, l d" NW D(a, n) - 1 0 d" (k - l) d"
NW D(a, n) - 1 k e" l
n
ns " Z (k - l) k = l
NW D(a,n)
NW D(a, n)
ax a" 1 NW D(a, n) = 1
x 0 d" x d" n - 1
a " Z
NW D(a, n) = 1 b " Z 0 d" b d" n - 1
ab a" 1
b ax a"
1
R = {a1, . . . , aĆ(n)}
" NW D(ai, n) = 1 i = 1, . . . , Ć(n)
" ai a" aj =Ò! i = j
R Ć(n)
a, n " Z R = {a1, . . . , aĆ(n)
NW D(a, n) = 1
Ra = {aa1, . . . , aaĆ(n)}
Ra
 NW D(aai, n) = 1 i = 1, . . . , phi(n)
aai a" aaj NW D(a, n) = 1
NW D(ai, n) NW D(aai, n) = 1
NW D(c, n) = 1
ac a" bc =Ò! a a" b
a = ai, b = aj, c = a ai a" aj R
i = j
R
{x : NW D(x, n) = 1, 1 d"
x d" n - 1} NW D(a, n) = 1
R = {aa1, . . . , aaĆ(n)}
R = Ra
a1 · a2 · . . . aĆ(n) a" aa1 · aa2 · . . . aaĆ(n)
a1 · a2 · . . . aĆ(n) a" aĆ(n)a1 · a2 · . . . aĆ(n)
NW D(ai, n) = 1 i = 1, . . . , Ć(n) NW D(a1 · . . . · aĆ(n)) = 1
1 a" aĆ(n)
aĆ(n) a" 1