Find the remainder when 67^99 is divided by 7.a)4 b)1 c)6 d)2Correct a...
Solution:
To find the remainder when 67^99 is divided by 7, we can use the concept of modular arithmetic.
- Modular Arithmetic: In modular arithmetic, we find the remainder when a number is divided by another number. It is denoted by the symbol ‘mod’. For example, if we want to find the remainder when 10 is divided by 3, we can write it as 10 mod 3 = 1, which means the remainder is 1.
- Euler's Theorem: Euler's theorem states that if a and n are coprime (i.e., they have no common factors), then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function, which gives the number of positive integers less than or equal to n that are coprime to n. In other words, if we raise any number a to the power of φ(n) and divide it by n, the remainder will be 1.
- Fermat's Little Theorem: Fermat's Little Theorem is a special case of Euler's theorem when n is a prime number. It states that if p is a prime number and a is any integer not divisible by p, then a^(p-1) ≡ 1 (mod p). In other words, if we raise any number a to the power of p-1 and divide it by p, the remainder will be 1.
Using Fermat's Little Theorem, we can simplify the expression 67^99 as follows:
67^99 ≡ (67^6)^16 * 67^3 (mod 7) [since 67 ≡ 4 (mod 7)]
≡ 1^16 * 4^3 (mod 7) [since 67^6 ≡ 1 (mod 7) by Fermat's Little Theorem]
≡ 64 (mod 7)
≡ 1 (mod 7)
Therefore, the remainder when 67^99 is divided by 7 is 1. Hence, the correct option is (b).
Note: We can also use the concept of repeated squaring to calculate 67^99 mod 7, but it is a bit more time-consuming.
Find the remainder when 67^99 is divided by 7.a)4 b)1 c)6 d)2Correct a...
Base 6 = 2×3
(12÷3)+(12÷9)=4+1=5