Answered: Combine Fermat’s Little Theorem with…

Name: Combine Fermat’s Little Theorem with the Chinese Remainder Theorem to
Uploaded: 2024-03-20T06:38:58.000Z
Channel: Bartleby
Description: Combine Fermat’s Little Theorem with the Chinese Remainder Theorem to calculate the least residue of 3^1453 modulo 35.

Advanced Engineering Mathematics

10th Edition

ISBN:9780470458365

Author:Erwin Kreyszig

Publisher:Erwin Kreyszig

Chapter2: Second-order Linear Odes

Section: Chapter Questions

Problem 1RQ

See similar textbooks

Related questions

Concept explainers

Topic Video

Question

Combine Fermat’s Little Theorem with the Chinese Remainder Theorem to calculate the least residue of 3^1453 modulo 35.

Expert Solution

Step 1

We have to calculate the least residue of $3^{1453} m o d u l o 35$ .

That is, we have to find an integer r such that $3^{1453} \equiv r (m o d 35)$ .

Note that, 35 is the product of 2 prime numbers 5 and 7.

Here, the base of the number $3^{1453}$ is 3 and the exponent is 1453.

The base 3 is co prime with both 5 and 7.

By the Fermat's little theorem, we know that for a prime number p and an integer a co prime to p, $a^{p - 1} \equiv 1 (m o d p)$ .

Taking a = 3 and p = 5, by the Fermat's little theorem we get $3^{4} \equiv 1 (m o d 5)$ .

Then, ${(3^{4})}^{484} \equiv 1^{484} (m o d 5)$ .

That is, $3^{1452} \equiv 1 (m o d 5)$ .

Then, $3^{1452} \times 3 \equiv 1 \times 3 (m o d 5)$ .

Thus, we get $3^{1453} \equiv 3 (m o d 5)$ .

Step by step

Solved in 4 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

$Sequence$

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.

Similar questions