Method 1 :
2 ÷ 7, the remainder is 2
2² ÷ 7, the remainder is 4
2³ ÷ 7, the remainder is 1
2⁴ ÷ 7, the remainder is 2
2⁵ ÷ 7, the remainder is 4
2⁶ ÷ 7, the remainder is 1
2⁷ ÷ 7, the remainder is 2
……….. and so on
Hence,
2³ⁿ⁺¹ ÷ 7, the remainder is 2
2³ⁿ⁺² ÷ 7, the remainder is 4
2³ⁿ ÷ 7, the remainder is 1
2²²⁰
= 2²¹⁹⁺¹
= 2³˟⁷³⁺¹
When 2²²⁰ = 2³˟⁷³⁺¹ is divided by 7, the remainder is 2.
====
Method 2 :
2²²⁰
= 2²¹⁹⁺¹
= 2²¹⁹ × 2¹
= (2³)⁷³ × 2¹
= (7 + 1)⁷³ × 2
= [7⁷³ + C(73,1)*7⁷² + C(73,2)*7⁷¹ + C(73,3)*7⁷⁰ + …… C(73,72)*7 + 1] × 2
= {[7⁷³ + C(73,1)*7⁷² + C(73,2)*7⁷¹ + C(73,3)*7⁷⁰ + …… C(73,72)*7}] + 1] × 2
= {7 * [7⁷² + C(73,1)*7⁷¹ + C(73,2)*7⁷⁰ + C(73,3)*7⁶⁹ + …… C(73,72)] + 1] * 2
Let N = 7⁷² + C(73,1)*7⁷¹ + C(73,2)*7⁷⁰ + C(73,3)*7⁶⁹ + …… C(73,72)
then, N is a positive integer.
2²²⁰
= {7 * [7⁷² + C(73,1)*7⁷¹ + C(73,2)*7⁷⁰ + C(73,3)*7⁶⁹ + …… C(73,72)] + 1} * 2
= {7N + 1} * 2
= 14N + 2
When (14N + 2) is divided by 7, the remainder is 2.
When 2²²⁰ is divided by 7, the remainder is 2.
(solution for 12 year olds)
Remainder when divided by 7
2^1......2
2^2......4
2^3......1
2^4......2
2^5......4
2^6......1
2^7......2
2^8......4
2^9......1
Get the the picture? So the remainders are always 2 or 4 or 1. So which one is it for 2^220?
Now if you do 73 3-steps (73 x 3 = 219) you are going to land on the 2^219 term with a remainder of 1. The next term will have 2^220 on the left, and this will be a remainder 2 line.
(The solution for above age 12 is the other solution given here. It is mathematically rigorous, unlike my noddy one)
2^220 mod 7
To do these problems compute the residues of lower powers then use the rules of exponents.
2^1 = 2
2^2 = 4
2^3 = 8 = 7+1 ≡ 1 mod 7
220 mod 3 = 1, 220=73*7+1
so 2^220 ≡ 2*2^219
≡ (2^3)^73 * 2
≡ 1^73 * 2
≡ 1*2
≡ 2 mod 7
Remainder is 2
edited:
2^220 mod 17
2^4 = 16 ≡ -1
2^8 ≡ (-1)^2 ≡ 1
220 mod 8 = 4
2^4 ≡ -1 ≡ 16 mod 17
2^220 ≡ 16 mod 17
remainder is 16