In this article, we explore how to prove that for every number in the set ({1, 2, ldots, p-1}), there exists another number within the same set such that their product is congruent to 1 modulo (p), where (p) is a prime number. This is a fundamental concept in elementary number theory and modular arithmetic. We will present two proofs using basic results from elementary number theory to emphasize the mathematical reasoning behind this property.

Proof 1: Using Properties of Prime Numbers

Let (a) be any number in the set ({1, 2, ldots, p-1}). We will consider the numbers (a cdot 0, a cdot 1, a cdot 2, ldots, a cdot (p-1) mod p). We need to show that these numbers are all distinct and cover all numbers from (0) to (p-1). If (a cdot i equiv a cdot j mod p) for some (i, j) where (0 leq i, j leq p-1), then we have:

(a cdot i - a cdot j equiv 0 mod p)

This simplifies to:

(a(i - j) equiv 0 mod p)

Since (a) is not congruent to 0 modulo (p) (because (a) is in ({1, 2, ldots, p-1})), (p) cannot divide (a). Therefore, (p) must divide (i - j), implying (i equiv j mod p). Since (0 leq i, j leq p-1), the only possibility is (i j). Hence, the list of numbers (a cdot 0, a cdot 1, a cdot 2, ldots, a cdot (p-1) mod p) contains (p) distinct values, which must be the numbers from (0) to (p-1).

Specifically, there exists some (k) such that:

(a cdot k equiv 1 mod p)

This shows that (k) is the modular multiplicative inverse of (a) modulo (p).

Incidentally, this idea also proves Fermat's theorem: if we exclude (a cdot 0) from the list, the remaining numbers are still a permutation of the numbers from (1) to (p-1). Multiplying everything yields:

(a^{p-1} cdot (p-1)! equiv (p-1)! mod p)

By simplifying, we get:

(a^{p-1} equiv 1 mod p)

Proof 2: Using Properties of the Greatest Common Divisor (gcd)

Given (a, b in mathbb{Z}) not both zero, with (g gcd(a, b)), it is well known that:

(amathbb{Z} bmathbb{Z} gmathbb{Z})

This can be written as:

({ax by: x, y in mathbb{Z}} {gz: z in mathbb{Z}})

Since (g) is in the set on the right-hand side of the above equation, there exist (r, s in mathbb{Z}) such that (g ar bs). If (p) is prime and (a in {1, 2, ldots, p-1}), then (gcd(a, p) 1). Hence, there exist (m, n in mathbb{Z}) such that (am pn 1), so that (am equiv 1 mod p).

Fermat's ``little” theorem provides another direct proof. The statement is:

If (p) is a prime and (p mid a), then (a^{p-1} equiv 1 mod p).

Since (a in {1, 2, ldots, p-1}) and (p mid a), we have that (a cdot a^{p-2} equiv 1 mod p). Therefore, (a^{p-2}) plays the same role as (m) in the first proof.

In conclusion, we have shown that for every number (a) in the set ({1, 2, ldots, p-1}), there exists an integer (k) such that (a cdot k equiv 1 mod p). This proof not only reinforces the fundamental principles of elementary number theory but also highlights the elegant and structured nature of modular arithmetic.