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

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)$

• $6^3=216\equiv 1(mod 43)$ Aug 12, 2015 at 13:16
• @lab bhattacharjee Is it correct (the proof)? Aug 13, 2015 at 6:36
• @user3313320 sorry, writting mistake Aug 13, 2015 at 10:05

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}$

• I can't get the second line with 6^(7^n) = 6^7^n (mod 42) (mod 43)... Aug 12, 2015 at 13:24
• @scummy, As $6^{42}\equiv1\pmod{43}$ Aug 12, 2015 at 13:25
• I can undersant this, but still can't get the second line. Aug 12, 2015 at 13:28
• @scummy, If $7^n=42m+r,$ $$6^{(7^n)}\equiv6^{42m+r}=(6^{42})^m\cdot6^r\equiv1^m\cdot6^r\pmod{43}$$ Aug 12, 2015 at 13:30
• Sorry - just didn't see it. Thanks! Aug 12, 2015 at 13:32

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}$$