Question No 01 | Part A | Exercise 5.3 | Wilson's Theorem | Elementary Number Theory
Question No 01 | Part A | Exercise 5.3 | Wilson's Theorem | Elementary Number Theory
Book Name : Elementary Number Theory
By : David M. Burton
Chapter Number : 05
Chapter Name : Fermat's Theorem
Lecture Number : 40
By (Name) : Awais Rasool
Exercise Number : 5.3
Problems Number: 5.3
Question Number : 01
Part Number : A
Example Number : 00
Awais Rasool Shah
Topics Name : Wilson's Theorem
5.1 Pierre de Fermat
5.2 Fermat's Little Theorem and Pseudoprimes
5.3 Wilson's Theorem
5.4 The Fermat-Kraitchik Factorization Method
..........................................................| |........................................................
📲 Facebook Profile Link:
https://www.facebook.com/awaisrasoolshah786/
📲 Instagram Profile Link:
https://www.instagram.com/awaisrasoolshah
📲 Linkedin Profile Link:
https://www.linkedin.com/in/
📲 WhatsApp contact:
+923160600073
..........................................................| Thanks |........................................................
Question No: 01
Part: A
Find the remainder when 15! is divided by 17.
Find the remainder when 15! is divided by 17.
Sol:
We want to find the remainder when 15! is divided by 17.Since 17 is a prime number,
we can use Wilson's Theorem, which states
(𝑝−1)!≡−1 (𝑚𝑜𝑑 𝑝)
For 𝑝=17, applying Wilson's Theorem:
(17−1)!≡−1 (𝑚𝑜𝑑 17)
16!≡−1 (𝑚𝑜𝑑 17)
16×15!≡−1 (𝑚𝑜𝑑 17)
Next, we find the remainder of 16 when divided by 17:
16≡16−17 (𝑚𝑜𝑑 17)
16≡−1 (𝑚𝑜𝑑 17)
Thus, the remainder when 16 is divided by 17 is −1. Substituting this back:
(−1)×15!≡−1 (𝑚𝑜𝑑 17)
Multiply both sides by −1.
(−1)×(−1)×15!≡(−1)×(−1) (𝑚𝑜𝑑 17)
1×15!≡1 (𝑚𝑜𝑑 17)
15!≡1 (𝑚𝑜𝑑 17) Therefore, the remainder when 15! is divided by 17 is 1.