Combinatorics Number Theory - The Inclusion

DO MY ASSIGNMENT
SUBMIT
Sample: Combinatorics Number Theory - The Inclusion-Exclusion Principle
Task 1.
Let n be a positive integer and p1 , . . . , pk be all the different prime numbers that divide
n. Consider the Euler function φ defined by
φ(n) = {k : 1 ≤ k, GCD{k, n} = 1}.
Use the inclusion-exclusion principle to show that
φ(n) = n
k
Y
(1 −
1
).
pi
i=1
Proof. The number n has the following form:
n = pa11 · pa22 · · · pakk ,
where p1 , . . . , pk are mutually distinct prime numbers, and ai ≥ 1.
We will use induction on k.
1) Suppose k = 1, so n = pa , where p is a prime number and a ≥ 1. Then formula
φ(n) = n
k
Y
(1 −
1
)
pi
i=1
reduces to
1
= pa − pa−1 .
p
Let A = {1, . . . , pa }, and B be the subset consisting of all numbers k that are not
relatively prime with n = pa , that is
φ(n) = φ(pa ) = pa (1 − p1 ) = pa − pa ·
B = {k | 1 ≤ k ≤ pa , GCD{k, n} 6= 1}.
Hence
A \ B = {k | 1 ≤ k ≤ pa , GCD{k, n} = 1},
and so, by definition of the function φ we have that
φ(n) = |A \ B|.
Thus we should to prove that
|A \ B| = pa − pa−1 .
Notice that GCD(k, pa ) 6= 1, i.e. k ∈ B, if and only if GCD(k, p) 6= 1 that is k is
divided by p.
Let C = {1, 2, . . . , pa−1 }. We claim that k ∈ B if and only if k = pm, where m ∈ C.
Indeed, if k ∈ B, so k is divided by p, then k = pm for some m. Since k = pm ≤ pa , it
follows that m ≤ pa−1 , that is m ∈ C.
Conversely, if m ∈ C, then k = pm ∈ B. This implies that |B| = |C| = pa−1 . Since
|A| = pa , we obtain that
|A \ B| = |A| − |B| = pa − pa−1 .
2) Suppose we have proved formula
k
Y
φ(n) = n (1 −
1
).
pi
i=1
for some k. Let us prove it for k + 1.
Thus assume that
n = xpa ,
1
W W W . A S S I G N M E N T E X P E R T. C O M
DO MY ASSIGNMENT
where x = pa11 · pa22 · · · pakk , p is a prime number distinct from p1 . . . , pk , and
k
Y
φ(x) = x (1 −
1
).
pi
i=1
We should prove that
φ(n) = n(1 −
1
)
p
k
Y
(1 −
1
)
pi
a
= xp (1 −
1
)
p
i=1
=x
k
Y
(1 −
1
)
pi
k
Y
(1 −
1
)
pi
=
i=1
· pa (1 − p1 ) = φ(x)(pa − pa−1 ).
i=1
Let A = {0, . . . , xpa − 1}, and B ⊂ A be the subset consisting of all numbers that
are not relatively prime with xpa . Notice that GCD(k, xpa ) 6= 1 if and only if either
GCD(k, x) 6= 1 or GCD(k, p) 6= 1.
Let also X ⊂ A be the subset consisting of all numbers that are not relatively prime
with x, and P ⊂ A be the subset consisting of all numbers that are not relatively prime
with P .
Then A \ (X ∪ P ) is the set of all k ∈ A which are relatively prime with n = xpa
|A \ (X ∪ P )| = {k : 1 ≤ k ≤ n, GCD(k, n) = 1},
so, by definition of the function φ we have that
φ(n) = |A \ (X ∪ P )|.
Thus we need to prove that
|A \ (X ∪ P )| = φ(x)(pa − pa−1 ).
Notice that
|A \ (X ∪ P )| = |A| − |X| − |P | + |X ∩ P |.
We have that
|A| = n = xpa .
Let us compute |X|. Notice that every k ∈ A can be uniquely written in the following
form:
k = αx + β,
a
where α ∈ {0, 1, . . . , p − 1} and β ∈ {0, . . . , x − 1}. Moreover, GCD(k, x) 6= 1, i.e. k ∈ X
if and only if GCD(β, x) 6= 1. But for such β we have x − φ(x) possibilities. Therefore
|X| = {0, 1, . . . , pa − 1} · (x − φ(x)) = pa (x − φ(x)).
Similarly, every k ∈ A can be uniquely written in the following form:
k = γpa + δ,
where γ ∈ {0, 1, . . . , x − 1} and δ ∈ {0, . . . , pa − 1}. Moreover, GCD(k, pa ) 6= 1, i.e. k ∈ P
if and only if GCD(δ, pa ) 6= 1. But for such β we have pa − φ(pa ) = pa−1 possibilities.
Therefore
|P | = {0, 1, . . . , x − 1} · pa−1 = xpa−1 .
Finally, suppose k ∈ X ∩ P , so GCD(k, p) 6= 1 and GCD(k, x) 6= 1. Thus k = mp for
some m ∈ {0, . . . , xpa−1 }, and GCD(m, x) 6= 1 since GCD(x, p) = 1. Then similarly to
computations of |X| we have that
|X ∩ P | = pa−1 (x − φ(x)).
Hence
φ(n) = |A \ (X ∪ P )| = |A| − |X| − |P | + |X ∩ P | =
2
W W W . A S S I G N M E N T E X P E R T. C O M
SUBMIT
DO MY ASSIGNMENT
= xpa − pa (x − φ(x)) − xpa−1 + pa−1 (x − φ(x))
= xpa − xpa + pa φ(x) − xpa−1 + xpa−1 − pa−1 φ(x)
= pa φ(x) − pa−1 φ(x) = φ(x)(pa − pa−1 ).
Thus by induction on k we obtain that formula
φ(n) = n
k
Y
(1 −
1
)
pi
i=1
hold for all n.
3
W W W . A S S I G N M E N T E X P E R T. C O M
SUBMIT

Download Report