Ask Singapore Homework?
Upload a photo of a Singapore homework and someone will email you the solution for free.
Question
junior college 2 | H3 Maths
One Answer Below
Anyone can contribute an answer, even non-tutors.
I need help for part 4
Date Posted: 3 years ago
Views: 556
See 1 Answer
We need to find the remainder when 47^2020 is divided by 17. This is basically 47^2020 mod 17 .
Now 47 and 17 are coprime. (Both are prime numbers so this is quite obvious)
This in turn implies that 47ⁿ and 17 are also coprime. 47ⁿ just means multiplying by 47 many times and since 47 itself already does not have a higher common divisor with 17 other than 1, neither will multiplying by many 47s yield any higher common divisor.
Since we want to divide by 17, we should let p = 17
Then using Fermat's Little Theorem,
a^(17-1) ≡ 1 (mod 17)
a^16 ≡ 1 (mod 17)
Now we have 47^2020, and 2020 isn't exactly divisible by 16, so we can't immediately rewrite it into something with a power of 16.
But we can break it into factors.
47^2020 = 47^(2016 + 4) = 47^2016 • 47⁴
= (47^(126x16)) • 47⁴ = (47^126)^16 • 47⁴
Since 47^126 is a positive integer and is coprime with 17 (as explained above), we can let 47^126 = a.
Using the theorem we can state that (47^126)^16 ≡ 1 (mod 17) ①
Now we look at 47⁴.
47⁴ = 4879681 and 47⁴ ÷ 17 = 287040 R 1
So 47⁴ ≡ 1 (mod 17) ②
Lastly,we need to use the multiplication rule for modular arithmetic, whereby :
a ≡ b (mod n) and c ≡ d (mod n) ⇒ ac ≡ bd (mod n)
① × ② gives us :
(47^126)^16 • 47⁴ ≡ 1 × 1 (mod 17)
47^2020 ≡ 1 (mod 17)
∴ The remainder is 1
Now 47 and 17 are coprime. (Both are prime numbers so this is quite obvious)
This in turn implies that 47ⁿ and 17 are also coprime. 47ⁿ just means multiplying by 47 many times and since 47 itself already does not have a higher common divisor with 17 other than 1, neither will multiplying by many 47s yield any higher common divisor.
Since we want to divide by 17, we should let p = 17
Then using Fermat's Little Theorem,
a^(17-1) ≡ 1 (mod 17)
a^16 ≡ 1 (mod 17)
Now we have 47^2020, and 2020 isn't exactly divisible by 16, so we can't immediately rewrite it into something with a power of 16.
But we can break it into factors.
47^2020 = 47^(2016 + 4) = 47^2016 • 47⁴
= (47^(126x16)) • 47⁴ = (47^126)^16 • 47⁴
Since 47^126 is a positive integer and is coprime with 17 (as explained above), we can let 47^126 = a.
Using the theorem we can state that (47^126)^16 ≡ 1 (mod 17) ①
Now we look at 47⁴.
47⁴ = 4879681 and 47⁴ ÷ 17 = 287040 R 1
So 47⁴ ≡ 1 (mod 17) ②
Lastly,we need to use the multiplication rule for modular arithmetic, whereby :
a ≡ b (mod n) and c ≡ d (mod n) ⇒ ac ≡ bd (mod n)
① × ② gives us :
(47^126)^16 • 47⁴ ≡ 1 × 1 (mod 17)
47^2020 ≡ 1 (mod 17)
∴ The remainder is 1
Thank you
360 Tutoring Program