Problem 29 - Algebra: Pure and Applied

Question

Prove that if \(p\) is prime, then \((p-1) ! \underline{=}-1 \bmod p\).

Step-by-Step Solution

Answer

By Wilson's Theorem, \((p-1)!\equiv -1 \pmod{p}\) for prime \(p\).

Step 1: Understanding the Problem

The problem asks us to prove that for a prime number \(p\), the factorial of \((p-1)\), when divided by \(p\), gives a remainder of \(-1\). In modular arithmetic, this is expressed as \((p-1)! \equiv -1 \pmod{p}\). This is known as Wilson's Theorem.

Step 2: State Wilson's Theorem

Wilson's Theorem states that if \(p\) is a prime number, then \((p-1)! \equiv -1 \pmod{p}\). This is the exact statement that we are asked to prove for any prime \(p\).

Step 3: Understanding Factorials and Modular Arithmetic

The factorial of a number \(n\), denoted \(n!\), is the product of all positive integers less than or equal to \(n\). Modular arithmetic involves finding the remainder when an integer is divided by \(p\). We aim to show that \((p-1)!\) leaves a remainder of \(-1\) when divided by \(p\).

Step 4: Use Fermat's Little Theorem

Fermat's Little Theorem states that if \(p\) is a prime and \(a\) is an integer not divisible by \(p\), then \(a^{p-1} \equiv 1 \pmod{p}\). This implies \((p-1)! \equiv (-1)^{p-1} \equiv -1 \pmod{p}\) as every non-zero integer modulo \(p\) has an inverse.

Step 5: Analyze Inverses in Modular Arithmetic

Since \(p\) is prime, for each integer \(a\) in the set \{1, 2, ..., p-1\}, there is a unique integer \(b\) in this set such that \(a \cdot b \equiv 1 \pmod{p}\). The integers from 1 to \(p-1\) can thus be paired off into these inverse pairs, except for 1 and \(p-1\).

Step 6: Simplify Using Inverses

In the product \((p-1)! = 1 \times 2 \times 3 \times \ldots \times (p-1)\), each term from 1 to \(p-1\) has an inverse except \(p-1\) and 1. Here, \((p-1)\) is its own inverse modulo \(p\), so the product simplifies to \((-1)\).

Step 7: Conclude with Wilson's Theorem

Combining our analyses, we've shown that the product of all numbers from 1 to \(p-1\) when divided by \(p\) leaves a remainder of \(-1\), thus proving Wilson's Theorem that \((p-1)! \equiv -1 \pmod{p}\).

Key Concepts

Factorials

The concept of factorial is integral to understanding problems involving number theory and algebra. A factorial, denoted by an exclamation mark following a number, represents the product of all positive integers up to that number. For example, the factorial of 4, written as \(4!\), is \(4 \times 3 \times 2 \times 1 = 24\).

Factorials grow very quickly due to this cumulative product. As such, they are used in a variety of mathematical contexts, such as permutations, combinations, and sequences.

In the context of Wilson's Theorem, we specifically deal with \((p-1)!\), where \(p\) is a prime number. This factorial involves multiplying all integers from 1 to \(p-1\), and it plays a critical role in establishing the relationship described by Wilson's Theorem.

• Factorials are multiplicative sequences.
• They are often used in combinatorial mathematics.
• In Wilson's Theorem, the factorial of \(p-1\) helps determine properties of primes.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" upon reaching a certain value, the modulus. Consider a regular clock where hours cycle from 1 to 12—this is a simple example of mod 12 arithmetic.

In mathematical terms, modular arithmetic involves division of numbers and examining the remainder. When expressed, it often looks like this: \(a \equiv b \pmod{n}\), meaning the remainder of \(a\) divided by \(n\) is equal to the remainder of \(b\) divided by \(n\).

In the case of Wilson's Theorem, the focus is on how \((p-1)!\) behaves when divided by a prime \(p\). Here, modular arithmetic helps us establish that the remainder is \(-1\).

• It simplifies number problems within a fixed range of integers.
• Useful for problems involving cycles and periodicity.
• Essential in proving properties related to factorials and prime numbers.

Fermat's Little Theorem

Fermat's Little Theorem is a fundamental result in number theory that deals with properties of prime numbers. The theorem asserts that if \(p\) is a prime and \(a\) is an integer not divisible by \(p\), then \(a^{p-1} \equiv 1 \pmod{p}\).

This theorem illustrates an intrinsic property of powers and primes showing that when raised to the power of \(p-1\), a number essentially "resets" to 1 modulo \(p\). This concept is pivotal in simplifying expressions involving large exponents.

In relation to Wilson's Theorem, Fermat's Theorem is utilized to demonstrate that each number in \((p-1)!\) has an inverse, thereby contributing to the final product ending in \(-1\) modulo \(p\).

• It showcases the cyclical nature of powers in modular arithmetic.
• Plays crucial role in cryptography and computer algorithms.
• Serves as an intermediary step to understanding advanced number theory concepts.