Introduction
Number theory is a field rich with elegant theorems, among which Fermat's Little Theorem plays a pivotal role. This theorem states that for any integer ( x ) and a prime number ( n ), if ( n ) and ( x ) are coprime (i.e., gcd(( n, x )) 1), then ( x^n equiv x pmod{n} ). In this article, we will explore how to prove this theorem and its generalization using methods such as Fermat's Little Theorem, group theory, and combinatorial arguments.
Proving ( x^n - x ) is Divisible by a Prime ( n ) with Fermat's Little Theorem
Let's start with the given conditions: ( n ) is a prime and ( x ) is an integer such that ( n ) and ( x ) are coprime. According to Fermat's Little Theorem, we have:
[x^n equiv x pmod{n}]This means:
[x^n - x equiv 0 pmod{n} quad text{or} quad x^n - x kn quad text{for some integer } k.]Thus, ( x^n - x ) is divisible by ( n ).
Handling Non-Coprime Cases
If ( n ) and ( x ) are not coprime, then ( x ) must be a multiple of ( n ). Hence, ( x^n - x ) is also divisible by ( n ):
[x kn quad Rightarrow quad x^n (kn)^n k^n n^n quad Rightarrow quad x^n - x k^n n^n - kn quad text{is clearly divisible by } n.]Therefore, we have shown that:
[x^n - x text{ is divisible by } n text{ for any integer } x text{ and prime } n.]Proof by Induction
To prove ( p^p - p ) is divisible by ( p ) for any prime ( p ), we use mathematical induction:
Base Case
For ( x 0 ):
[p^0 - 0 1 quad text{and } 1 pmod{p} equiv 0]Hence, the base case holds.
Inductive Hypothesis
Assume that for some integer ( x ), ( x^p - x ) is divisible by ( p ). That is, there exists an integer ( k ) such that:
[x^p - x kp.]Inductive Step
We need to show that ( (x 1)^p - (x 1) ) is divisible by ( p ). Using the binomial expansion, we have:
[(x 1)^p sum_{i0}^{p} binom{p}{i} x^i.]The expression can be written as:
[(x 1)^p x^p sum_{i1}^{p-1} binom{p}{i} x^i 1.]Subtract ( (x 1) ) from this equation:
[(x 1)^p - (x 1) x^p - x sum_{i1}^{p-1} binom{p}{i} x^i.]By Fermat's Little Theorem, (binom{p}{i} equiv 0 pmod{p}) for ( 1 leq i leq p-1 ). Therefore:
[(x 1)^p - (x 1) x^p - x 0 kp.]By the inductive hypothesis, ( x^p - x kp ). Thus:
[(x 1)^p - (x 1) kp kp 2kp,]which is divisible by ( p ). Therefore, by induction, ( p^p - p ) is divisible by ( p ) for any prime ( p ).
Application of the Freshman's Dream in Modular Arithmetic
The "freshman's dream" theorem states that in a field of characteristic ( p ) (where ( p ) is a prime), the equation ( (ab)^p equiv a^p b^p pmod{p} ) holds true. This can be applied here since we are working modulo a prime ( n ).
For example, consider ( 32^3 - 2 ) and ( 4(2^4 - 2) ) and ( 5(2^5 - 2) ). These expressions can be evaluated as follows:
[32^3 - 2 2^5 - 2 30, quad 4(2^4 - 2) 4 cdot 14 56 equiv 0 pmod{3},]and
[5(2^5 - 2) 30,]all of which are divisible by their respective primes.
The Role of Group Theory in Proving ( x^n - x )
In group theory, integers modulo ( n ) form a multiplicative group of order ( n-1 ) if ( n ) is a prime. Consider the subgroup generated by ( x ). This subgroup has an order ( k ) such that ( x^k 1 ) (by Fermat's Little Theorem). The smallest ( k ) for which this holds is the order of the element in the group.
By Lagrange's Theorem, the order of the subgroup divides the order of the group, so ( n-1 jk ). Therefore:
[x^{n-1} x^{jk} (x^k)^j 1^j 1 pmod{n}.]Multiplying both sides by ( x ), we get:
[x^n equiv x pmod{n}.]Thus, ( x^n - x equiv 0 pmod{n} ), confirming the statement.
Conclusion
Through the lens of number theory and group theory, we have explored the proof of the statement ( x^n - x ) being divisible by a prime ( n ). This theorem is foundational in cryptography and number theory, with applications in various areas such as coding theory and computer science.