Proving Wilson's Theorem Using Gauss' Lemma

  • Thread starter mathsss2
  • Start date
  • Tags
    Theorem
In summary, Wilson's theorem is a mathematical theorem discovered by John Wilson in the 18th century. It states that a natural number is prime if and only if (n-1)! + 1 is divisible by n. This theorem is significant because it provides a simple and efficient method for determining prime numbers and has applications in cryptography and number theory. It is always true, but only applies to natural numbers. In cryptography, it is used to generate large prime numbers for secure encryption.
  • #1
mathsss2
38
0
Use:
[tex]2\cdot4\cdot...\cdot(p-1)\equiv(2-p)(4-p)\cdot...\cdot(p-1-p)\equiv(-1)^{\frac{(p-1)}{2}}\cdot1\cdot3\cdot...\cdot(p-2)[/tex] mod [tex]p[/tex]
and
[tex](p-1)!\equiv-1[/tex] mod p [Wilson's Theorem]
to prove
[tex]1^2\cdot3^2\cdot5^2\cdot...\cdot(p-2)^2\equiv(-1)^{\frac{(p-1)}{2}}[/tex] mod [tex]p[/tex]

Relevant equations

Gauss lemma
wilson's theorem [[tex](p-1)!\equiv-1[/tex] mod[tex]p[/tex]]

The attempt at a solution
need assistance

Thanks
 
Physics news on Phys.org
  • #2
Hint:

[tex]2 \cdot 4 \cdot \ldots \cdot (p-1)=\frac{(p-1)!}{1 \cdot 3 \cdot \ldots \cdot (p-2)}=(p-1)! \cdot \left( \frac{1}{1 \cdot 3 \cdot \ldots \cdot (p-2)} \right)[/tex]
 
  • #3
Thanks, this problem is solved.
 

1. What is Wilson's theorem?

Wilson's theorem is a mathematical theorem that states that a natural number n is a prime number if and only if (n-1)! + 1 is divisible by n.

2. Who discovered Wilson's theorem?

Wilson's theorem was discovered by the English mathematician John Wilson in the 18th century.

3. What is the significance of Wilson's theorem?

Wilson's theorem is significant because it provides a simple and efficient method for determining whether a number is prime or not. It also has applications in cryptography and number theory.

4. Is Wilson's theorem always true?

Yes, Wilson's theorem is always true. However, it can only be applied to natural numbers and does not work for all numbers.

5. How is Wilson's theorem used in cryptography?

Wilson's theorem is used in cryptography to generate large prime numbers, which are essential for secure encryption. By using Wilson's theorem, it is possible to efficiently check whether a number is prime, making it easier to find large prime numbers for cryptography purposes.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
270
  • Calculus and Beyond Homework Help
Replies
4
Views
691
  • Calculus and Beyond Homework Help
Replies
1
Views
514
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
849
  • Calculus and Beyond Homework Help
Replies
3
Views
521
  • Precalculus Mathematics Homework Help
Replies
5
Views
981
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
Back
Top