Determine, with justi�cation, the value of the remainder when 2^314 is divided by 91.
(Hint: 91 = 13 * 7.)
To determine the value of the remainder when 2^314 is divided by 91, we can use the property of modular arithmetic.
First, note that 91 can be factored as the product of 13 and 7. This means we can solve the problem by finding the remainders of 2^314 when divided by 13 and 7 separately.
To find the remainder when 2^314 is divided by 13, we can use Euler's Totient Theorem. According to this theorem, if a and n are coprime (meaning they have no common factors), then a^φ(n) ≡ 1 (mod n), where φ(n) denotes Euler's totient function.
In this case, since 2 and 13 are coprime (they have no common factors), we can use Euler's Totient Theorem to find the remainder when 2^314 is divided by 13. The totient of 13, denoted as φ(13), is 12 since all numbers from 1 to 13 are coprime with 13. So, we have:
2^12 ≡ 1 (mod 13)
Now, we can divide the exponent 314 by 12 and keep the remainder:
314 ÷ 12 = 26 remainder 2
So, we can rewrite 2^314 as (2^12)^26 × 2^2. But since 2^12 ≡ 1 (mod 13), we have:
(2^12)^26 × 2^2 ≡ 1^26 × 2^2 ≡ 4 (mod 13)
Therefore, the remainder when 2^314 is divided by 13 is 4.
Similarly, we can calculate the remainder when 2^314 is divided by 7. Since 2 and 7 are coprime, we can directly use modular exponentiation:
2^314 ≡ 2^312 × 2^2 ≡ (2^6)^52 × 2^2 ≡ 1^52 × 2^2 ≡ 4 (mod 7)
Therefore, the remainder when 2^314 is divided by 7 is also 4.
Now that we have obtained the remainders for dividing 2^314 by 13 and 7, we need to find a number that satisfies both congruences. This can be done using the Chinese Remainder Theorem.
Since we are looking for a number x such that x ≡ 4 (mod 13) and x ≡ 4 (mod 7), we can write:
x ≡ 4 (mod 13)
x ≡ 4 (mod 7)
Using the Chinese Remainder Theorem, we can find that the solution to this system of congruences is:
x ≡ 4 × 7 × 7^(-1) (mod 91)
To solve for 7^(-1) (the modular inverse of 7), we need to find a number y such that 7 × y ≡ 1 (mod 91). In this case, y = 13 is a solution because 7 × 13 ≡ 1 (mod 91).
Therefore, we have:
x ≡ 4 × 7 × 13 (mod 91)
x ≡ 364 ≡ 25 (mod 91)
Hence, the value of the remainder when 2^314 is divided by 91 is 25.