2
$\begingroup$

How do I prove $4^n\equiv 4\pmod 6$ where $n \in \Bbb Z_+$?

I was always doing it by checking $n \in \{1,2,3,4,5 \}$ and if there was a pattern then I assume that it is correct.

So I was wondering if there is a easier and faster way to prove it with modular arithmetics.

$\endgroup$
  • 2
    $\begingroup$ Perhaps use induction $\endgroup$ – JohnColtraneisJC Aug 25 '17 at 12:08
  • 1
    $\begingroup$ $4^n - 4 = 4(4^{n-1} - 1)$. Note that $x^m - y^m = (x-y)(x^{m-1} + x^{m-2}y + \cdots + xy^{m-2} + y^{m-1})$, so $4^{n-1} -1 = (4-1) (4^{n-2} + \cdots + 1)$ is divisible by $3$. Conclusion? $\endgroup$ – Cauchy Aug 25 '17 at 12:10
  • $\begingroup$ Use $\in$ for $\in$. $\endgroup$ – Shaun Aug 25 '17 at 12:11
4
$\begingroup$

Proof by induction for $n>1$ $$4^1 = 4 \mod 6$$

No assume its true for some $n$ $$4^n = 4 \mod 6$$ $$4^{n+1} = 16 \mod 6 $$ $$4^{n+1} = 4 \mod 6$$

So its true for $\mathbb Z^+$

$\endgroup$
4
$\begingroup$

First check mod $3$ and then mod $2$. Since both $2$ and $3$ divide $4^n-4$, then so must $6.$

$\endgroup$
4
$\begingroup$

Proof by induction is the easiest way.

$\left[4^{n} \equiv 4\ \mathrm{(mod\ 6)} \implies 4^{n+1} \equiv 16\ \mathrm{(mod\ 6)}\equiv 4\ \mathrm{(mod\ 6)}\right] \land \left[4^{1} \equiv 4\ \mathrm{(mod\ 6)}\right]\\\implies 4^{n} \equiv 4\ \mathrm{(mod\ 6)}\ \forall n\in\mathrm{N^{*}}$

$\endgroup$
1
$\begingroup$

Because $4^n = 2^{2n} = (2^n)^2$, this is always a square number. There are only $3$ possible values of $m^2\bmod 6$: $\{0,1,4\}$. Since $4^n$ is not divisible by $6$ and is not odd, it must be that $4^n\equiv 4 \bmod 6$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.