Since 2⁵ = 32, and
2⁵ ≡ 32 ≡ 10 (mod 22),
we have
2⁵¹ ≡ 2 • 2⁵⁰ ≡ 2 • (2⁵)¹⁰ ≡ 2 • 10¹⁰ (mod 22)
Now consider 10¹⁰ (mod 22):
10 = 2 • 5
10¹⁰ ≡ 2¹⁰ • 5¹⁰ ≡ (2⁵)² • 5¹⁰ ≡ 10² • 5¹⁰ ≡ 2² • 5¹² (mod 22)
so that
2⁵¹ ≡ 2³ • 5¹² (mod 22)
Now consider 5¹² (mod 22):
5 and 22 are coprime, and ɸ(22) = 10 (where ɸ(<em>n</em>) is the Euler totient function). By Euler's theorem,
5¹² ≡ 5² • 5¹⁰ ≡ 5² • 1 ≡ 25 ≡ 3 (mod 22)
and so
2⁵¹ ≡ 2³ • 3 ≡ 24 ≡ 2 (mod 22)
Another, more tedious method: Start with smaller powers of 2 and look for a pattern.
2 ≡ 2 (mod 22)
2² ≡ 4 (mod 22)
2³ ≡ 8 (mod 22)
2⁴ ≡ 16 (mod 22)
2⁵ ≡ 32 ≡ 10 (mod 22)
2⁶ ≡ 2 • 32 ≡ 2 • 10 ≡ 20 (mod 22)
2⁷ ≡ 2 • 20 ≡ 40 ≡ 18 (mod 22)
2⁸ ≡ 2 • 18 ≡ 36 ≡ 14 (mod 22)
2⁹ ≡ 2 • 14 ≡ 28 ≡ 6 (mod 22)
2¹⁰ ≡ 2 • 6 ≡ 12 (mod 22)
2¹¹ ≡ 2 • 12 ≡ 24 ≡ 2 (mod 22)
2¹² ≡ 2 • 2 ≡ 4 (mod 22)
and so on, with a cyclic pattern of length 10. That is, for any integer <em>k</em> ≥ 0. So 2⁵¹ ≡ 2 (mod 22).