91Ó°ÊÓ

The concept of a multiplicative group modulo, symbolized as \( Z_m^* \), is fundamental in number theory. This group consists of all integers that are less than a given number \( m \) and are also coprime to \( m \). Importantly, these numbers can be multiplied together and reduced modulo \( m \) while still remaining within the group.
Each element in \( Z_m^* \) has an inverse within the set. This means that for every element \( a \) in \( Z_m^* \), there exists another element \( b \) such that \( a \times b \equiv 1 \pmod{m} \).

When working with different values of \( m \), you'll find that the size of \( Z_m^* \) is given by Euler's Totient function, \( \varphi(m) \).
Examples include:

• For \( m = 11 \), \( Z_{11}^* = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} \)
• For \( m = 16 \), \( Z_{16}^* = \{1, 3, 5, 7, 9, 11, 13, 15\} \)

Understanding and identifying these elements is crucial for deeper insights into number theory topics like cryptography.

Prime numbers are the building blocks of number theory. They are numbers greater than 1 that have no positive divisors other than 1 and themselves.

When a number \( m \) is a prime, the task of determining \( \varphi(m) \) becomes straightforward. If \( m \) is prime, every number less than \( m \) is coprime to \( m \).

• For instance, with \( m = 11 \), which is prime, \( \varphi(11) \) is simply \( 11 - 1 = 10 \).
• This means all numbers from 1 to 10 are part of \( Z_{11}^* \).

However, not all numbers are prime. When \( m \) is not a prime, finding coprime numbers requires more effort. But this simple property of primes simplifies calculations in many mathematical situations.

Two numbers are considered coprime, or relatively prime, if their greatest common divisor (GCD) is 1. In other words, they have no common divisors except for 1.

Suppose you want to find coprime numbers to \( m \). You would generally check each number less than \( m \) to verify if their GCD with \( m \) is 1.
For example:

• For \( m = 16 \), the numbers in \( Z_{16}^* \) are \{1, 3, 5, 7, 9, 11, 13, 15\}. Each of these numbers is coprime to 16, as none share a common factor with it besides 1.

This property is crucial in modular arithmetic, particularly when generating multiplicative groups and calculating the Euler's Totient function.

Factorization is the process of breaking down a number into its prime components. It's a cornerstone for working with \( \varphi(m) \) when \( m \) is not prime.

To apply Euler's Totient function correctly, factor \( m \):

• For \( m = 33 \), the factorization is \( 3 \times 11 \).
• For \( m = 42 \), the factorization is \( 2 \times 3 \times 7 \).

Once you have the prime factors, you can use the formula:
\[ \varphi(m) = m \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \dots \text{ for each prime } p \text{ in the factorization}. \]

This simplification through factorization allows for easy computation of \( \varphi(m) \) which is vital when working with larger composite numbers.