Difference between revisions of "Wilson's Theorem"
m (organization) |
|||
Line 12: | Line 12: | ||
Finally, multiply this equality by <math>p-1</math> to complete the proof. | Finally, multiply this equality by <math>p-1</math> to complete the proof. | ||
− | == | + | == Problems == |
+ | === 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 === | ||
+ | * If <math>{p}</math> is a prime greater than 2, define <math>p=2q+1</math>. Prove that <math>(q!)^2 + (-1)^q</math> is divisible by <math>{p}</math>. [http://www.mathlinks.ro/Forum/viewtopic.php?&t=21733 Solution] | ||
* Let <math>{p}</math> be a prime number such that dividing <math>{p}</math> by 4 leaves the remainder 1. Show that there is an integer <math>{n}</math> such that <math>n^2 + 1</math> is divisible by <math>{p}</math>. | * Let <math>{p}</math> be a prime number such that dividing <math>{p}</math> by 4 leaves the remainder 1. Show that there is an integer <math>{n}</math> such that <math>n^2 + 1</math> is divisible by <math>{p}</math>. | ||
− | |||
− | |||
− | |||
− | |||
== See also == | == See also == |
Revision as of 01:00, 20 November 2007
Statement
If and only if is a prime, then
is a multiple of
. In other words
.
Proof
Wilson's theorem is easily verifiable for 2 and 3, so let's consider . If
is composite, then its positive factors are among
![$1, 2, 3, \dots, p-1$](http://latex.artofproblemsolving.com/0/d/f/0dfe24d3485a7f19fa17e2195c625959c00dc811.png)
Hence, , so
.
However, if is prime, then each of the above integers are relatively prime to
. So, for each of these integers a, there is another
such that
. It is important to note that this
is unique modulo
, and that since
is prime,
if and only if
is
or
. Now, if we omit 1 and
, then the others can be grouped into pairs whose product is congruent to one,
![$2\cdot3\cdot4\cdots(p-2) \equiv 1\pmod{p}$](http://latex.artofproblemsolving.com/b/6/a/b6a67ca261ea87615017b0a10b367e711c9b801b.png)
Finally, multiply this equality by to complete the proof.
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
. Solution
- 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
.