Let G be a cyclic group of order n, and let d | n, d ≥ 1. (a) Prove that G has φ(d) elements of order d. (b) Prove that G has a unique subgroup of order d. (c) Prove that X d|n φ(d) = n.

(a) Let's denote the generator of the cyclic group G as g. Since G is a cyclic group of order n, we know that g^n = e (the identity element). Now, let's consider an element g^k of G. The order of g^k is n/gcd(n,k). We want to find the number of elements of order d, so we need to find the number of k such that n/gcd(n,k) = d. This is equivalent to finding the number of k such that gcd(n,k) = n/d. Since d divides n, we can write n = dm for some integer m. So we need to find the number of k such that gcd(dm,k) = d. This is the number of integers k between 1 and n that are relatively prime to m, which is given by Euler's totient function φ(m). But since m = n/d, this is the same as φ(n/d). Therefore, G has φ(n/d) elements of order d.

(b) Let's denote the subgroup of G of order d as H. Since G is a cyclic group, any subgroup H of G is also cyclic. Therefore, H can be generated by an element of G of order d. From part (a), we know that there are φ(d) such elements. However, all these elements generate the same subgroup H, because they all have the same order d. Therefore, G has a unique subgroup of order d.

(c) This is a well-known result in number theory, known as the sum formula for Euler's totient function. It states that the sum of φ(d) over all divisors d of n is equal to n. This can be proven by considering the fraction a/b in lowest terms, where a and b are integers between 1 and n. The number of such fractions is φ(d) for each divisor d of n, and the total number of such fractions is n. Therefore, the sum of φ(d) over all divisors d of n is equal to n.