Remainder of division of ${6}^{7^n}$ to $43$

Question

What is the Remainder of the division of ${6}^{7^n}$ to $43$?

I've tried with Fermat's little theorem, but it haven't work.

Update : lab bhattacharjee gave a nice proof. But I want to know if this proof is correct.

${6^7}^n = ({6^7})^{7^{n-1}}$

$6^7 = ({6^3})^2$ * 6

$6^3 = 216 = 1(mod 43) => ({6^3})^2 = 1^2 = 1 (mod 43) => 6^7 = 6 (mod 43) => ({6^7})^{7^{n-1}} = 6^{7^{n-1}} (mod 43) <=> {6^7}^n = {6^7}^{n-1} (mod 43)$

The same way we obtain $6^{7^{n-1}} = 6^{7^{n-2}} (mod 43)$

$6^{7^{n-2}} = 6^{7^{n-3}} (mod 43)$

...

${6^7}^2 = {6^7}^1 (mod 43)$

${6^7}^1 = {6^7}^0 = 6 (mod 43)$

So ${6^7}^n = 6 (mod 43)$

Answer 1

As $\phi(43)=42$

$\implies6^{(7^n)}\equiv6^{7^n\pmod{42}}\pmod{43}$

let use find $7^n\pmod{42}$

Now as $(7^n,42)=7$ for integer $n\ge1$

we shall find $7^{n-1}\pmod6$

$7\equiv1\pmod6\implies7^{n-1}\equiv1^{n-1}\equiv1$

$\implies7^n\equiv7\cdot1\pmod{6\cdot7}\equiv7$

$\implies6^{(7^n)}\equiv6^7\pmod{43}$

Now use $6^3\equiv1\pmod{43}$ and $6^7=(6^3)^2\cdot6\equiv?\pmod{43}$

Answer 2

As $6^3\equiv1\pmod{43}$ $$6^{(7^n)}\equiv6^{(7^n)\pmod3}\pmod{43}$$

and $7\equiv1\pmod3\implies7^n\equiv1^n\equiv1$

$$6^{(7^n)}\equiv6^1\pmod{43}$$