# Show that $11^n ≡ 6 \pmod{5}$ for every natural number $n$

This is what I have : By induction

Base case: $n=1$ where it is true Inductive hypothesis: Assume there exists a natural number k where this is true for $k<n$ Show for $k+1$, $11^{k+1} ≡ 6 \pmod{5}$ implies $11^{k}\cdot 11 ≡ 6\cdot 6 \pmod{5} =36\pmod{5}$ Therefore it is true for all natural numbers. Is this true. I find this too easy

• Hint: what is $11$ congruent to mod $5$? Now use your induction hypothesis. – Alex Wertheim Nov 12 '14 at 2:40
• I'm sorry it won't let me post my solution. But I wanna know if what I have is correct, please check . – Jessy White Nov 12 '14 at 2:41
• Base case: n=1 where it is true Inductive hypothesis: Assume there exists a natural number k where this is true for k<n Show for k+1, 11^(k+1) ≡ 6 mod 5 implies 11^(k)*11 ≡ 6 *6 mod 5 =36 mod 5 Therefor it is true for all natural numbers. Is this true. I find this too easy – Jessy White Nov 12 '14 at 2:41
• Looks just fine to me! (Although just for clarity's sake, you may want to remark at the end that $36 \equiv 6 \pmod 5$.) – Alex Wertheim Nov 12 '14 at 2:44
• Is it stated anywhere that you need to use induction? Because it's as simple as $11^n \equiv 1^n \equiv 1 \equiv 6 \pmod 5$. A simple (almost trivial) direct proof. Why use induction? – Deepak Nov 12 '14 at 4:09

Since $6 \cong 1\pmod{5}$, thus we prove: $11^n \cong 1\pmod{5}$, but $11^n - 1 = (11-1)(10^{n-1} + 10^{n-2} + .... + 1) \cong 0\pmod{5}$
You have $$11^n = 6^n = 1^n = 1 \text{mod} 5.$$
$$11^n=(10+1)^n= 1 \mod 5$$