9
$\begingroup$

Calculate without a calculator:

$\left (14^{2014} \right )^{2014} \mod 60$

I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1.

This was my solution so far (also doesn't really work without a calculator):

Prime factorization of 60:
$60 = 2^{2}\cdot 3\cdot 5$

Chinese Remainder Theorem setup:
$\left (14^{2014} \right )^{2014} \mod 4\\$
$\left (14^{2014} \right )^{2014} \mod 3\\$
$\left (14^{2014} \right )^{2014} \mod 5\\$

Euler's Theorem:
$\phi \left ( 4 \right ) = 2$
$\Rightarrow 14^{2}\equiv 1 \mod 4$

Whoops, that's not right because gcd(14,4) is not 1, but 2. Euler's Theorem only works when gcd(a,m) = 1.

I don't know how else to solve this, does anyone have an idea?

$\endgroup$
6
$\begingroup$

$$X=\large (14^{2014})^{2014}=14^{2014^2}$$

Now, $60=3\times 4\times 5$. Now,

$$X\equiv\begin{cases}(-1)^{2014^2}\equiv 1\pmod3\\ (-1)^{2014^2}\equiv 1\pmod5\\ 7^{2014^2}\cdot 4^{(2014^2)/2}\equiv 0\pmod4\end{cases}$$

Now, use Chinese Remainder Theorem.

$\endgroup$
  • 1
    $\begingroup$ You don't need to use CRT, with $X \equiv1 \pmod 3, X \equiv1 \pmod 5 $, i'ts obvious that $ X \equiv 1 \pmod{15} $, find the next number that is a multiple of 4 yields $\boxed{16}$. $\endgroup$ – GohP.iHan May 3 '15 at 8:57
  • 1
    $\begingroup$ Thank you, this helped the best! $\endgroup$ – Thursday Next May 3 '15 at 9:00
  • $\begingroup$ @GohP.iHan, you're absolutely right but I just find using CRT a bit more natural. I'm not that much used to exhaust my brain like you do. :3 There's a reason you're the genius, not me. $\endgroup$ – Prasun Biswas May 3 '15 at 9:00
  • 1
    $\begingroup$ @CGuy, happy to help. :) $\endgroup$ – Prasun Biswas May 3 '15 at 9:01
  • 1
    $\begingroup$ Haha, stop complimenting me man. Somemore, you don't need to split 60 into all prime factors, as long as they are coprime to each other: $60 = 15 \times 4 $. We immediately get $ X \equiv (-1)^\text{even} \equiv 1 \pmod{15} $ $\endgroup$ – GohP.iHan May 3 '15 at 9:07
7
$\begingroup$

$$\left (14^{2014} \right )^{2014}=(14^2)^{1007\times2014}\equiv 16^{1007\times2014} \mod 60$$

Next, notice that $16\times 16\equiv 16\pmod{60}$ to conclude $16^n\equiv 16\pmod{60}$ for all integers $n\ge 1$

$\endgroup$
3
$\begingroup$

With all the powers of $2$, $(14^{2014})^{2014}$ is clearly equivalent to $0\pmod4$. We also have $(14^{2014})^{2014}\equiv[(-1)^{2014}]^{2014}\equiv 1\pmod{15}$. These $2$ conditions combined yield a result equivalent to $16\pmod{60}$.

$\endgroup$
3
$\begingroup$

As $(a^m)^n=a^{mn},$

we need $14^{2014^2}\pmod{60}$

As $(14^n,60)=2^2$ for integer $n\ge2,$

let us compute $14^{2014^2-2}\pmod{15}$

Now $14\equiv-1\pmod{15}\implies14^{2014^2-2}\equiv(-1)^{2014^2-2}\pmod{15}\equiv1$ as $2014^2-2$ is even

$\implies14^2\cdot14^{2014^2-2}\equiv14^2\cdot1\pmod{14^2\cdot15}$

As $60|14^2\cdot15,$
$$14^2\cdot14^{2014^2-2}\equiv14^2\pmod{60}\equiv ?$$

$\endgroup$
  • $\begingroup$ What does (14^n, 60) = 2^2 stand for? There is no operator or anything. Otherwise I think I get it. $\endgroup$ – Thursday Next May 3 '15 at 9:04
  • 1
    $\begingroup$ @CGuy, $(a,b)=\gcd(a,b)$ is the greatest common divisor of $a$ and $b$. $\endgroup$ – Prasun Biswas May 3 '15 at 9:05
  • $\begingroup$ Ah okay I didn't know you could write it like that, thanks. $\endgroup$ – Thursday Next May 3 '15 at 9:06
  • $\begingroup$ @CGuy, I actually prefer the $\gcd$ notation since it's understandable to all. People have different preferences when it comes to notations. $\endgroup$ – Prasun Biswas May 3 '15 at 9:07
2
$\begingroup$

Carmichael's function for $60$ is lcm$(\phi(4),\phi(3),\phi(5))=$ lcm$(2,2,4)=4$, so $a^k \equiv a^{k+4}$ once all possible prime factors of $60$ have been accumulated. So we can quickly square $14$ twice and see where it's going: $$ 14^2 = 196 \equiv 16 \bmod 60 \\ 14^4 \equiv 16^2 = 256 \equiv 16 \bmod 60 $$ So we are fortunate here, and $14^{2k} \equiv 16^k \equiv 16 \bmod 60$. No need to worry about the second exponentiation, except to observe that the resulting exponent is certainly even.

$\endgroup$
0
$\begingroup$

By below $\ 2\mid 15-1\,\ \Rightarrow\,\ 14^{2k}\,\equiv\, 4(4^{-1}\,{\rm mod}\ 15)\equiv 4^2\!\pmod{4^2\!\cdot 15},\,\ j = 2\le 2k$.

Lemma $\,\ a\mid n\!-\!1\,\Rightarrow\,(n\!-\!1)^{2k}\equiv a^j(a^{-j}\ {\rm mod}\ n)\ \pmod{a^jn}\, $ if $\ 0\le \color{#c00}{j\le 2k}$

Proof $\ $ Note $\, {\rm mod}\ n\!:\ (n\!-\!1)^{2k}\equiv (-1)^{2k}\equiv 1\equiv a^j(a^{-j}\ {\rm mod}\ n)$

$a\mid n\!-\!1\!\!\underset{\color{#c00}{j\,\le\, 2k}}\Rightarrow\! {\rm mod}\ a^j\!:\ (n\!-\!1)^{2k}\color{#c00}{\equiv 0}\equiv a^j(a^{-j}\ {\rm mod}\ n).\,$ Being congruent both mod $\,a^j\,$ & $\,n,\,$ they are also congruent mod $\,{\rm lcm}(a^j,n) = a^jn,\,$ by $\,(a,n)=1,\,$ by $\,a\mid n\!-\!1.$

$\endgroup$
  • $\begingroup$ Remark $\,\ a\mid n\!-\!1\,\Rightarrow\, ab = n\!-\!1\,\Rightarrow\, a^{-1}\equiv -b\pmod{n},\,$ so no modular inversion is needed. $\endgroup$ – Bill Dubuque May 3 '15 at 19:20

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.