Find the remainder when 2108 is divided by 31.
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
Question
![The problem presented involves modular arithmetic:
**Question**: Find the remainder when \(2^{108}\) is divided by 31.
To solve this problem, we can use Fermat's Little Theorem, which states that if \(p\) is a prime number and \(a\) is an integer not divisible by \(p\), then \(a^{p-1} \equiv 1 \pmod{p}\).
In this case, since 31 is a prime number, let \(a = 2\), then:
\[2^{30} \equiv 1 \pmod{31}\]
We need to express 108 in terms of multiples of 30:
\[108 = 30 \times 3 + 18\]
Thus,
\[2^{108} = 2^{30 \times 3 + 18} = (2^{30})^3 \times 2^{18}\]
By Fermat's Little Theorem:
\[(2^{30})^3 \equiv 1^3 \equiv 1 \pmod{31}\]
Therefore:
\[2^{108} \equiv 2^{18} \pmod{31}\]
Now we only need to find \(2^{18} \mod 31\). Using successive squaring:
\[2^1 = 2\]
\[2^2 = 4\]
\[2^4 = 16\]
\[2^8 = (2^4)^2 = 256 \equiv 8 \pmod{31}\]
\[2^{16} = (2^8)^2 = 64 \equiv 2 \pmod{31}\]
Hence:
\[2^{18} = 2^{16} \times 2^2 = 2 \times 4 = 8 \equiv 8 \pmod{31}\]
Thus, the remainder when \(2^{108}\) is divided by 31 is 8.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F30761ad5-6d22-4ff4-adb6-4f166a7ab52a%2Fcc84036f-8edf-4c7a-8265-476d682a5bbf%2Fmnzrjt_processed.jpeg&w=3840&q=75)
Transcribed Image Text:The problem presented involves modular arithmetic:
**Question**: Find the remainder when \(2^{108}\) is divided by 31.
To solve this problem, we can use Fermat's Little Theorem, which states that if \(p\) is a prime number and \(a\) is an integer not divisible by \(p\), then \(a^{p-1} \equiv 1 \pmod{p}\).
In this case, since 31 is a prime number, let \(a = 2\), then:
\[2^{30} \equiv 1 \pmod{31}\]
We need to express 108 in terms of multiples of 30:
\[108 = 30 \times 3 + 18\]
Thus,
\[2^{108} = 2^{30 \times 3 + 18} = (2^{30})^3 \times 2^{18}\]
By Fermat's Little Theorem:
\[(2^{30})^3 \equiv 1^3 \equiv 1 \pmod{31}\]
Therefore:
\[2^{108} \equiv 2^{18} \pmod{31}\]
Now we only need to find \(2^{18} \mod 31\). Using successive squaring:
\[2^1 = 2\]
\[2^2 = 4\]
\[2^4 = 16\]
\[2^8 = (2^4)^2 = 256 \equiv 8 \pmod{31}\]
\[2^{16} = (2^8)^2 = 64 \equiv 2 \pmod{31}\]
Hence:
\[2^{18} = 2^{16} \times 2^2 = 2 \times 4 = 8 \equiv 8 \pmod{31}\]
Thus, the remainder when \(2^{108}\) is divided by 31 is 8.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps with 3 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
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…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
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…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
