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

© Copyright 2018 ExploreDoc