Proof of multiplicative property of Euler's Totient function
To prove that Euler's totient function \( \phi(n) \) is multiplicative—meaning that if \( \gcd(a,b) = 1 \), then \( \phi(ab) = \phi(a)\phi(b) \)—we can use a structural approach involving a rectangular array of integers.
1. Setting up the Array
Recall that \( \phi(n) \) is the number of integers \( x \) such that \( 1 \le x \le n \) and \( \gcd(x,n) = 1 \). Let \( n = ab \) with \( \gcd(a,b) = 1 \).
We can list the integers from 1 to \( ab \) in an \( a \times b \) matrix: \[ \begin{array}{cccc} \text{Col 1} & \text{Col 2} & \cdots & \text{Col } k \\ 1 & 2 & \cdots & k \\ b+1 & b+2 & \cdots & b+k \\ 2b+1 & 2b+2 & \cdots & 2b+k \\ \cdots & \cdots & \cdots & \cdots \\ (a-1)b+1 & (a-1)b+2 & \cdots & (a-1)b+k \end{array} \]
2. Row and Column Conditions
For an element \( x \) in this table to be counted in \( \phi(ab) \), it must satisfy \( \gcd(x,ab) = 1 \).
This is equivalent to:
1. \( \gcd(x,b) = 1 \)
2. \( \gcd(x,a) = 1 \)
First condition: \( \gcd(x,b) = 1 \)
Since every element in a column is congruent to the top element modulo \( b \) (i.e., \( qb + k \equiv k \ (\mathrm{mod}\ b) \)), an entire column either consists of elements that are all coprime to \( b \), or all not coprime to \( b \).
A. There are exactly \( \phi(b) \) such columns where \( \gcd(k,b) = 1 \).
B. We only need to look at these \( \phi(b) \) columns.
Second condition: \( \gcd(x,a) = 1 \)
Now, let’s look within one of those "valid" columns (column \( k \)). The elements are:
\[ \{k, b+k, 2b+k, \dots, (a-1)b+k\} \] Since \( \gcd(a,b) = 1 \), this set forms a complete residue system modulo \( a \). Note about Complete residue system modulo 'a'.
It means that elements in this set are exactly 0,1,2...a-1 and nothing else. Each element appears exactly once.
Why?
1. There are exactly 'a' values in this column.
2. They are of the form: n*b + k where n goes from 0 to (a-1).
3. Proof by contradiction. Let's say a particular remainder 'p' occurs twice
4. That means n1*b + k = n2*b + k modulo 'a'.
5. So n1*b = n2*b modulo 'a' (subtract 'k' from both sides)
6. So b*(n1-n2) = 0 modulo 'a'. Since n1,n2 both are distinct,positive and less than a => (n1-n2) = 0 is the only solution since gcd(a,b) = 1. Hence the contradiction.
A. This is a consequence of the fact that if \( r_1 b + k \equiv r_2 b + k \ (\mathrm{mod}\ a) \), then \( (r_1 - r_2)b \equiv 0 \ (\mathrm{mod}\ a) \). Since \( \gcd(a,b) = 1 \), we must have \( r_1 \equiv r_2 \ (\mathrm{mod}\ a) \).
B. Because these \( a \) numbers are just the residues \( \{0,1,\dots,a-1\} \) in some order, exactly \( \phi(a) \) of them will be coprime to \( a \).
And if 2 numbers leave same remainder when divided by a, their gcd with 'a' will also be same.
3. Final Count
To satisfy both conditions:
A. We must pick one of the \( \phi(b) \) columns that are coprime to \( b \).
B. In each of those columns, there are exactly \( \phi(a) \) elements coprime to \( a \).
Therefore, the total number of elements \( x \) such that \( \gcd(x,ab) = 1 \) is:
\[ \phi(ab) = \phi(a)\cdot\phi(b) \] Q.E.D.
1. Setting up the Array
Recall that \( \phi(n) \) is the number of integers \( x \) such that \( 1 \le x \le n \) and \( \gcd(x,n) = 1 \). Let \( n = ab \) with \( \gcd(a,b) = 1 \).
We can list the integers from 1 to \( ab \) in an \( a \times b \) matrix: \[ \begin{array}{cccc} \text{Col 1} & \text{Col 2} & \cdots & \text{Col } k \\ 1 & 2 & \cdots & k \\ b+1 & b+2 & \cdots & b+k \\ 2b+1 & 2b+2 & \cdots & 2b+k \\ \cdots & \cdots & \cdots & \cdots \\ (a-1)b+1 & (a-1)b+2 & \cdots & (a-1)b+k \end{array} \]
2. Row and Column Conditions
For an element \( x \) in this table to be counted in \( \phi(ab) \), it must satisfy \( \gcd(x,ab) = 1 \).
This is equivalent to:
1. \( \gcd(x,b) = 1 \)
2. \( \gcd(x,a) = 1 \)
First condition: \( \gcd(x,b) = 1 \)
Since every element in a column is congruent to the top element modulo \( b \) (i.e., \( qb + k \equiv k \ (\mathrm{mod}\ b) \)), an entire column either consists of elements that are all coprime to \( b \), or all not coprime to \( b \).
A. There are exactly \( \phi(b) \) such columns where \( \gcd(k,b) = 1 \).
B. We only need to look at these \( \phi(b) \) columns.
Second condition: \( \gcd(x,a) = 1 \)
Now, let’s look within one of those "valid" columns (column \( k \)). The elements are:
\[ \{k, b+k, 2b+k, \dots, (a-1)b+k\} \] Since \( \gcd(a,b) = 1 \), this set forms a complete residue system modulo \( a \). Note about Complete residue system modulo 'a'.
It means that elements in this set are exactly 0,1,2...a-1 and nothing else. Each element appears exactly once.
Why?
1. There are exactly 'a' values in this column.
2. They are of the form: n*b + k where n goes from 0 to (a-1).
3. Proof by contradiction. Let's say a particular remainder 'p' occurs twice
4. That means n1*b + k = n2*b + k modulo 'a'.
5. So n1*b = n2*b modulo 'a' (subtract 'k' from both sides)
6. So b*(n1-n2) = 0 modulo 'a'. Since n1,n2 both are distinct,positive and less than a => (n1-n2) = 0 is the only solution since gcd(a,b) = 1. Hence the contradiction.
A. This is a consequence of the fact that if \( r_1 b + k \equiv r_2 b + k \ (\mathrm{mod}\ a) \), then \( (r_1 - r_2)b \equiv 0 \ (\mathrm{mod}\ a) \). Since \( \gcd(a,b) = 1 \), we must have \( r_1 \equiv r_2 \ (\mathrm{mod}\ a) \).
B. Because these \( a \) numbers are just the residues \( \{0,1,\dots,a-1\} \) in some order, exactly \( \phi(a) \) of them will be coprime to \( a \).
And if 2 numbers leave same remainder when divided by a, their gcd with 'a' will also be same.
3. Final Count
To satisfy both conditions:
A. We must pick one of the \( \phi(b) \) columns that are coprime to \( b \).
B. In each of those columns, there are exactly \( \phi(a) \) elements coprime to \( a \).
Therefore, the total number of elements \( x \) such that \( \gcd(x,ab) = 1 \) is:
\[ \phi(ab) = \phi(a)\cdot\phi(b) \] Q.E.D.
Comments
Post a Comment