How to Calculate the Sum of All Co-Primes Less Than n of Number n

In mathematics, particularly in number theory, the concept of co-prime numbers is fundamental. This article will explore the method to calculate the sum of all co-prime numbers less than a given number n, denoted as {sigma}^{prime}n. The solution involves the use of Euler's totient function, denoted as φ(n).

The Co-Prime Set

Let n be a positive integer from the set of natural numbers, denoted as mathbb{N}. The set of all positive integers that are less than or equal to n and coprime to n is denoted as S^{prime}n.

S^{prime}n Big{ a: 1 le a le n, gcd(a, n) 1 Big}

This set includes all integers a between 1 and n that share no common divisors with n, except 1. For instance, if n 8, then the co-prime numbers less than 8 are 1 and 3, 5, and 7, making the set S^{prime}8 {1, 3, 5, 7}.

Note that for n 1, the set S^{prime}1 {1} and the sum σ^{prime}1 1.

The Sum of All Co-Primes Less Than n

Let σ^{prime}n denote the sum of all integers in the set S^{prime}n.

σ^{prime}n displaystyle sum_{substack{1 le a le n, gcd(a, n) 1}} a

For example, for n 8, σ^{prime}8 1 3 5 7 16.

A Property of Co-Primes

A key property of co-prime numbers is that if a is in S^{prime}n, then n - a is also in S^{prime}n. This can be mathematically expressed as:

1 le a le n if and only if 1 le n - a le n and gcd(a, n) gcd(n - a, n)

This property allows us to pair the elements in S^{prime}n, such that each pair sums to n. For n 8, the pairs are (1, 7), (3, 5), and each pair sums to 8.

Deriving the Formula for σ^{prime}n

Using the property mentioned above, we can derive the formula for σ^{prime}n. According to the property, the pairs (a, n-a) each sum to n. Thus:

2 cdot σ^{prime}n displaystyle sum_{substack{1 le a le n, gcd(a, n) 1}} a displaystyle sum_{substack{1 le a le n, gcd(a, n) 1}} n - a n cdot displaystyle sum_{substack{1 le a le n, gcd(a, n) 1}} 1 n cdot φ(n)

This simplifies to:

σ^{prime}n frac{1}{2} n cdot φ(n)

Where φ(n) is Euler's totient function, representing the count of numbers less than n that are co-prime to n.

Examples and Practical Applications

This formula can be applied to various scenarios. For example, to find the sum of all co-primes less than 9 for n 9:

φ(9) 6 (since the numbers less than 9 that are co-prime to 9 are 1, 2, 4, 5, 7, 8)

σ^{prime}9 frac{1}{2} cdot 9 cdot 6 27

The formula is particularly useful in cryptography and number theory applications where the properties of co-prime numbers are essential.

Conclusion

The sum of all co-primes less than n of number n can be calculated using the formula σ^{prime}n frac{1}{2} n cdot φ(n). This method leverages the property that if a is in S^{prime}n, then n - a is also in S^{prime}n and the cardinality of S^{prime}n, which is φ(n).