Difference between revisions of "Wilson's Theorem"
Line 18: | Line 18: | ||
Let <math>p</math> be a prime. Consider the [[field]] of integers modulo <math>p</math>. By [[Fermat's Little Theorem]], every nonzero element of this field is a root of the [[polynomial]] | Let <math>p</math> be a prime. Consider the [[field]] of integers modulo <math>p</math>. By [[Fermat's Little Theorem]], every nonzero element of this field is a root of the [[polynomial]] | ||
− | <cmath> P(x) = x^ | + | <cmath> P(x) = x^p - 1 . </cmath> |
Since this field has only <math>p-1</math> nonzero elements, it follows that | Since this field has only <math>p-1</math> nonzero elements, it follows that | ||
− | <cmath> x^ | + | <cmath> x^p - 1 = \prod_{r=1}^{p-1}(x-r) . </cmath> |
Now, either <math>p=2</math>, in which case <math>a \equiv -a \pmod 2</math> for any integer <math>a</math>, | Now, either <math>p=2</math>, in which case <math>a \equiv -a \pmod 2</math> for any integer <math>a</math>, | ||
or <math>p-1</math> is even. In either case, <math>(-1)^{p-1} \equiv 1 \pmod{p}</math>, so that | or <math>p-1</math> is even. In either case, <math>(-1)^{p-1} \equiv 1 \pmod{p}</math>, so that | ||
− | <cmath> x^ | + | <cmath> x^p - 1 = \prod_{r=1}^{p-1}(x-r) = \prod_{r=1}^{p-1}(-x + r) . </cmath> |
If we set <math>x</math> equal to 0, the theorem follows. <math>\blacksquare</math> | If we set <math>x</math> equal to 0, the theorem follows. <math>\blacksquare</math> | ||
== Problems == | == Problems == | ||
− | === Introductory === | + | === Introductory === |
+ | * Let <math>a</math> be an integer such that <math>\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{23}=\frac{a}{23!}</math>. Find the remainder when <math>a</math> is divided by <math>13</math>. | ||
=== Advanced === | === Advanced === | ||
Line 41: | Line 42: | ||
* [[Factorial]] | * [[Factorial]] | ||
* [[Wilson Prime]] | * [[Wilson Prime]] | ||
+ | |||
+ | Category: [[Number Theory]] |
Revision as of 10:43, 7 April 2019
In number theory, Wilson's Theorem states that if integer , then is divisible by if and only if is prime. It was stated by John Wilson. The French mathematician Lagrange proved it in 1771.
Contents
[hide]Proofs
Suppose first that is composite. Then has a factor that is less than or equal to . Then divides , so does not divide . Therefore does not divide .
Two proofs of the converse are provided: an elementary one that rests close to basic principles of modular arithmetic, and an elegant method that relies on more powerful algebraic tools.
Elementary proof
Suppose is a prime. Then each of the integers has an inverse modulo . (Indeed, if one such integer does not have an inverse, then for some distinct and modulo , , so that is a multiple of , when does not divide or —a contradiction.) This inverse is unique, and each number is the inverse of its inverse. If one integer is its own inverse, then so that or . Thus we can partition the set into pairs such that . It follows that is the product of these pairs times . Since the product of each pair is conguent to 1 modulo , we have as desired.
Algebraic proof
Let be a prime. Consider the field of integers modulo . By Fermat's Little Theorem, every nonzero element of this field is a root of the polynomial Since this field has only nonzero elements, it follows that Now, either , in which case for any integer , or is even. In either case, , so that If we set equal to 0, the theorem follows.
Problems
Introductory
- Let be an integer such that . Find the remainder when is divided by .
Advanced
- If is a prime greater than 2, define . Prove that is divisible by . <url>Forum/viewtopic.php?&t=21733 Solution</url>
- Let be a prime number such that dividing by 4 leaves the remainder 1. Show that there is an integer such that is divisible by .
See also
Category: Number Theory