Totien-Sum: why GCD( {n}/d, q/d) = 1; implies Sum{Totient(d/q) } = q

Question

Have seen answer to this question. still don't understand..

Totient sum is defined: q = Sum(Totient (d) ); sum on all d : d|q

More specific; The proof has these steps:
1. If d is a divider of q so is q/d.
2. If GCD([n1, n2, ..], q) = [d d, .., d] then
GCD([n1, n2, ..]/d, q/d) = [1, 1,.. 1];
3. Sum{ Totient(d) } = Sum{Totient(q/d) } = q;
The sum is over all the set d - dividers of q

1, 2, above are fairly simple. However i failed to understand why 2. implies 3

Answer 1

The set {n}/d - that is to say, the set {n} divided by its GCD d - is co-prime to q/n. It is the complete set (other wise it implies that {n} is not complete). By definition, totient(q/d) counts the number of co-primes to q/d

Since 1:q are partitioned into non overlapped groups the sum(totient({q/d) ) = q.

Answer 2

On The Euler (Totient) Function Multiplicity

Define theTotient function as Eu(.). To prove Eu(N∙M) = Eu(N)∙Eu(M). The set 1:N∙M is partitioned into set of columns. Each column is a sum of a base column: C0 = [ 0, M, .. (N-1)M]’; and an offset - k; k: 1,2,..M; A column Ck is: Ck= C0 + k.

An element of a column Ck is the sum: s = nM + k. Columns are different by their offset k only. The following lemma is used: For a, b and c natural numbers greater than zero we have:
If c = a + b; then: GCD(a, b) = GCD(a, c) = GCD(b,c);

Therefore It is sufficient that the offset k alone be “free” of any divider d > 1 - that divides M - to guarantee that the entire column Ck doesn’t have d as a divider.

Next: How many elements in the selected columns fulfill: GCD(Ck, N) == 1?.

To this end the following is proposed:
a. Cr = rem(Ck, N); rem(.) is the remainder modulo N. Cr(.) is a column of remainders
b. CrM = GCD(Cr, N) == 1; Crm is a mask of zeros column with one at n: GCD(Cr(n), N) =1;
c. Number of elements{ GCD(Ck,N) == 1 } = Sum(CrM) ;

In step a. an element Ck(n) is written: Ck(n) = N∙q(n) + Cr(n); we know (Euclid GCD algorithm): GCD(Ck(n), N) = GCD(Cr(n), N);

Recall that a column Ck is: Ck = C0 + k = (0:N-1)’∙M + k; k = 1:M; The Modulo N operation transforms the column Ck into the elements 1:N. Note that gcd(N, M) =1. therefore rem(C0, N) is the set: 0:N-1 with No repetition. Only the order is permutated depends on the value of the offset k.

Consequently: Sum(CrM) = Eu(N); is identical to all columns.

Eu(N)∙Eu(M) = (elements in Ck: GCD(Ck,N) =1) x (number of column: GCD(Ck, M)=1) = total elements in 1:NM that don’t divide NM. Therefore: Eu(N)∙Eu(M) = Eu(NM);