2
$\begingroup$

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

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

2 Answers 2

2
$\begingroup$

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

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

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

$\endgroup$
3
  • $\begingroup$ @scummy, Please clarify your question. $\endgroup$ Aug 12, 2015 at 16:23
  • $\begingroup$ Could we speak at chat? It's quite hard here 'cause you can edit a comment every 5 minutes. $\endgroup$
    – scummy
    Aug 12, 2015 at 16:30
  • $\begingroup$ I've sent it here $\endgroup$
    – scummy
    Aug 12, 2015 at 16:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .