Theorem 11.3. If p and q = 2p+1: primes, then either q | M, or q| M,+2, but are not both.
Theorem 11.3. If p and q = 2p+1: primes, then either q | M, or q| M,+2, but are not both.
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Topic Video
Question
Proof short and simplified with clear letters
![Mersenne numbers are prime or composite. One such test is presented next.
Proof. With reference to Fermat's theorem, we know that
Theorem 11.3. If p and q = 2p+1 are primes, then either q | M, or q | M,+2, but
Whether certain special types of
not both.
29-1 -1=0 (mod q)
and, factoring the left-hand side, that
(2(a-1)/2 – 1)(24-1)/2 + 1) = (2P – 1)(2P + 1)
= 0 (mod q)
What amounts to the same thing:
Mp(Mp+2) = 0 (mod q)
The stated conclusion now follows directly from Theorem 3.1. We cannot have both
a|Mp and q | Mp+2, for then q|2, which is impossible.
A single application should suffice to illustrate Theorem 11.3: if p = 23, then
=2p +1 = 47 is also a prime, so that we may consider the case of M23. The
question reduces to one of whether 47| M23 or, to put it differently, whether 223 =
1 (mod 47). Now, we have
223 = 2°(2°)* = 2°(-15)*(mod 47)
But
(-15)* = (225)? = (-10)² = 6 (mod 47)
Putting these two congruences together, we see that
223 = 23.6 = 48 = 1 (mod 47)
whence M23 is composite.
We might point out that Theorem 11.3 is of no help in testing the primality of
M29, say; in this instance, 59 M29, but instead 59| M29 +2.
Of the two possibilities q| M, or q| Mp+2, is it reasonable to ask: What
found in Theorem 11.4.
Theorem 11.4. If q = 2n + 1 is prime, then we have the following:
ta) q| M, provided that q = 1 (mod 8) or q = 7 (mod 8).
0) 9|M,+ 2, provided that q = 3 (mod 8) or q = 5 (mod 8).
24-1/2
= 2" = 1 (mod q)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa03415f8-38f2-4478-b688-afaca619ca5c%2Fbb8ab401-d64c-4cfa-b350-6b2b870778b1%2Ffdghgz_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Mersenne numbers are prime or composite. One such test is presented next.
Proof. With reference to Fermat's theorem, we know that
Theorem 11.3. If p and q = 2p+1 are primes, then either q | M, or q | M,+2, but
Whether certain special types of
not both.
29-1 -1=0 (mod q)
and, factoring the left-hand side, that
(2(a-1)/2 – 1)(24-1)/2 + 1) = (2P – 1)(2P + 1)
= 0 (mod q)
What amounts to the same thing:
Mp(Mp+2) = 0 (mod q)
The stated conclusion now follows directly from Theorem 3.1. We cannot have both
a|Mp and q | Mp+2, for then q|2, which is impossible.
A single application should suffice to illustrate Theorem 11.3: if p = 23, then
=2p +1 = 47 is also a prime, so that we may consider the case of M23. The
question reduces to one of whether 47| M23 or, to put it differently, whether 223 =
1 (mod 47). Now, we have
223 = 2°(2°)* = 2°(-15)*(mod 47)
But
(-15)* = (225)? = (-10)² = 6 (mod 47)
Putting these two congruences together, we see that
223 = 23.6 = 48 = 1 (mod 47)
whence M23 is composite.
We might point out that Theorem 11.3 is of no help in testing the primality of
M29, say; in this instance, 59 M29, but instead 59| M29 +2.
Of the two possibilities q| M, or q| Mp+2, is it reasonable to ask: What
found in Theorem 11.4.
Theorem 11.4. If q = 2n + 1 is prime, then we have the following:
ta) q| M, provided that q = 1 (mod 8) or q = 7 (mod 8).
0) 9|M,+ 2, provided that q = 3 (mod 8) or q = 5 (mod 8).
24-1/2
= 2" = 1 (mod q)
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, advanced-math and related others by exploring similar questions and additional content below.Recommended textbooks for you
![Advanced Engineering Mathematics](https://www.bartleby.com/isbn_cover_images/9780470458365/9780470458365_smallCoverImage.gif)
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
![Numerical Methods for Engineers](https://www.bartleby.com/isbn_cover_images/9780073397924/9780073397924_smallCoverImage.gif)
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
![Introductory Mathematics for Engineering Applicat…](https://www.bartleby.com/isbn_cover_images/9781118141809/9781118141809_smallCoverImage.gif)
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
![Advanced Engineering Mathematics](https://www.bartleby.com/isbn_cover_images/9780470458365/9780470458365_smallCoverImage.gif)
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
![Numerical Methods for Engineers](https://www.bartleby.com/isbn_cover_images/9780073397924/9780073397924_smallCoverImage.gif)
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
![Introductory Mathematics for Engineering Applicat…](https://www.bartleby.com/isbn_cover_images/9781118141809/9781118141809_smallCoverImage.gif)
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
![Mathematics For Machine Technology](https://www.bartleby.com/isbn_cover_images/9781337798310/9781337798310_smallCoverImage.jpg)
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
![Basic Technical Mathematics](https://www.bartleby.com/isbn_cover_images/9780134437705/9780134437705_smallCoverImage.gif)
![Topology](https://www.bartleby.com/isbn_cover_images/9780134689517/9780134689517_smallCoverImage.gif)