4
$\begingroup$

Find the remainder when $$3!^{{{5!}^{...}}^{2013!}}$$ is divided by 11.

My answer is 5, but the answer given by the answer sheet is 1. How did this happen?

I tried getting the remainders when several powers of 6 is divided by 11 since $3!=6.$ I actually got a pattern: 6, 3, 7, 9, 10, 5 and restarts to 6. Since the immediate exponent raising 6 is 120 which is divisible by 6, I reasoned that the remainder should be 5.

I know my solution does not make sense. I really do not know what to do. Can anyone help?

$\endgroup$
  • 1
    $\begingroup$ The actual pattern of powers of $6$ is $$ 6,3,7,9,10,5,8,4,2,1$$ Then it repeats $\endgroup$ – Omnomnomnom Sep 1 '16 at 11:11
  • $\begingroup$ Thank you for the correction. $\endgroup$ – Carl Terence Valdellon Sep 1 '16 at 11:46
1
$\begingroup$

Your approach is fine, you just made a calculation mistake: $6\cdot 5=30\equiv 8\bmod 11$, not $6$.

You can also consider Fermat's Little Theorem: $a^{p-1}\equiv 1\bmod p$ for any prime number $p$ and any integer $a$ relatively prime to $p$. Since is $6$ is relatively prime to $11$, we have $6^{10}\equiv 1\bmod 11$, and therefore $6$ raised to any power divisible by $10$ is also equivalent to $1$ modulo $11$.

$\endgroup$
  • 1
    $\begingroup$ @CarlTerenceValdellon: In this case, yes. Generally, two integers $m$ and $n$ are relatively prime to each other when $\gcd(m,n)=1$, so for example, $6$ and $35$ are relatively prime to each other, but $6$ and $34$ are not since $\gcd(6,34)=2$. When $p$ is a prime number, it's easy to see that $$a\text{ is relatively prime to }p\iff \gcd(a,p)=1\iff a\text{ is not divisible by }p$$ $\endgroup$ – Zev Chonoles Sep 1 '16 at 11:43
  • $\begingroup$ Thank you very much for your help. $\endgroup$ – Carl Terence Valdellon Sep 1 '16 at 11:47
1
$\begingroup$

Hint: The key insight is that $(5!)^{\cdots}$ is a multiple of $10$.

$\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.