Question

Zeigen Sie: Die Menge der natürlichen Zahlen zwischen 0 und \(n\) - 1 , die ein multiplikatives Inverses modulo \(n\) haben, ist gleich der Menge der natürlichen Zahlen zwischen 0 und \(n-1\), die mit \(n\) den größten gemeinsamen Teiler 1 haben (zwei natürliche Zahlen, deren ggT gleich 1 ist, nennt man auch teilerfremd) [Hinweis: Benutzen Sie das Lemma von Bézout.].

Short answer

The sets are equivalent: a number has a multiplicative inverse modulo \(n\) if and only if it is coprime with \(n\), as per Bézout's Lemma.

Step-by-step solution

Understand the Problem

The task is to show that the set of natural numbers from 0 to \(n-1\) that have a multiplicative inverse modulo \(n\) is equivalent to the set of natural numbers from 0 to \(n-1\) that are coprime with \(n\).

Define Multiplicative Inverse

A number \(a\) has a multiplicative inverse modulo \(n\) if there exists a number \(b\) such that \(a \cdot b \equiv 1 \pmod{n}\). This inverse exists if and only if \(\gcd(a, n) = 1\), according to number theory.

Apply Bézout's Lemma

Bézout's Lemma states that for any integers \(a\) and \(b\), if \(d = \gcd(a, b)\), then there exist integers \(x\) and \(y\) such that \(ax + by = d\). If \(\gcd(a, n) = 1\), there exist integers \(x\) and \(y\) such that \(ax + ny = 1\). This equation implies that \(ax \equiv 1 \pmod{n}\), which means \(x\) is the multiplicative inverse of \(a\) modulo \(n\).

Identify the Set

We conclude that an element \(a\) in the set \(0\) to \(n-1\) has a multiplicative inverse modulo \(n\) if it is coprime to \(n\). Hence, the set of all such \(a\) is exactly the set of numbers from 0 to \(n-1\) that are coprime with \(n\).

Conclusion

Thus, the set of numbers that have multiplicative inverses modulo \(n\) is the same as the set of numbers that are coprime to \(n\), as both require \(\gcd(a, n) = 1\). Bézout's Lemma confirms that when two numbers are coprime, a linear combination equal to 1 exists, which gives the condition for an inverse.

Key concepts

Bézout's Lemma

Bézout's Lemma is a fascinating result in number theory that connects the greatest common divisor (GCD) of two numbers with a linear combination of those numbers. It states that for any integers \(a\) and \(b\), if \(d = \gcd(a, b)\), then there exist integers \(x\) and \(y\) such that \(ax + by = d\). This lemma provides a way to express the GCD of two numbers as a linear combination of the numbers themselves.
For example, if \(a\) and \(b\) are coprime, meaning their GCD is 1, Bézout's Lemma guarantees the existence of integers \(x\) and \(y\) such that \(ax + by = 1\). This is particularly useful in modular arithmetic, as it provides a method to find multiplicative inverses.

Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two natural numbers is the largest positive integer that divides both numbers without leaving a remainder. It is a fundamental concept in number theory that helps in understanding the relationships between numbers. Mathematically, GCD can be denoted as \(\gcd(a, b)\) and can be found using the Euclidean algorithm, which is an efficient method for computing it.
The Euclidean algorithm involves a series of division steps where the remainder of each division is used as a divisor in the next division. The last non-zero remainder in this process is the GCD. Understanding GCD is crucial when studying problems related to divisibility, such as finding out when two numbers are coprime.

Coprime Numbers

Coprime numbers, also known as relatively prime numbers, are pairs of numbers whose greatest common divisor is 1. In simpler terms, two numbers \(a\) and \(b\) are coprime if they share no common factors other than 1. This concept is essential when discussing the properties of numbers in modular arithmetic.
Finding if two numbers are coprime involves checking if their GCD is 1. This can be quickly performed with the Euclidean algorithm. Coprime numbers are interesting because of their role in guaranteeing the existence of multiplicative inverses in modular arithmetic. Only numbers that are coprime to \(n\) will have such inverses modulo \(n\).

Multiplicative Inverse

The multiplicative inverse of a number modulo \(n\) is another number which, when multiplied by the original, results in 1 under modular arithmetic. In mathematical terms, if \(a\) has a multiplicative inverse modulo \(n\), there exists a number \(b\) such that \(a \cdot b \equiv 1 \pmod{n}\).
A key requirement for a number to have a multiplicative inverse is that it must be coprime to \(n\); in other words, \(\gcd(a, n) = 1\). Bézout's Lemma confirms this condition by providing a method to find numbers \(x\) and \(y\) such that \(ax + ny = 1\), thus making \(x\) the modular inverse of \(a\) modulo \(n\). This concept is especially vital in cryptography and computer algorithms.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers where numbers wrap around upon reaching a certain value, the modulus. A common analogy is how we use hours on a clock, where the numbers reset after reaching 12. In modular arithmetic, calculations are performed with respect to a specified modulus \(n\).
It is written mathematically as \(a \equiv b \pmod{n}\), meaning that \(a\) and \(b\) leave the same remainder when divided by \(n\). One of the critical applications of modular arithmetic is in finding multiplicative inverses, especially in solving linear congruences where Bézout's Lemma is often applied. This arithmetic is foundational in computer science, number theory, and cryptography.