4
$\begingroup$

I was re-practicing some number theory and I came across this question that I had previously solved and it seems like... I can't solve it anymore. My thoughts are that $18^6 \equiv 1 \text{ mod } 7$ by Euler's formula so I am looking to express the power $20^{19}$ as some $6k + r$ to simplify the system. Doing this I get: $$20 \equiv 2 \text{ mod } 6\\ 20^2 \equiv 4\text{ mod } 6\\ 20^3 \equiv 2 \text{ mod } 6$$ ...and there seems to be no end as they repeat in 2, 4, 2 cycles. I can't seem to simplify this equation any other way though.. Could someone please enlighten me and suggest ways of viewing (or improving) on my problem solving skills when attacking problems like these?

$\endgroup$
4
  • $\begingroup$ the fact that it is $2,4,2,\dots$ cycle simplifies the problem greatly, in fact $\endgroup$
    – user160738
    Commented Dec 15, 2016 at 10:10
  • $\begingroup$ Are repeating mod cycles necessarily closed and if a loop is detected once, does that imply that loop holds infinitely? $\endgroup$
    – q.Then
    Commented Dec 15, 2016 at 10:11
  • $\begingroup$ @Ephemeral I explain a nice way to do these problems in my answer (which gives the complete solution). $\endgroup$ Commented Dec 16, 2016 at 16:20
  • $\begingroup$ Do you want to find the quotient or the remainder? $\endgroup$
    – GFauxPas
    Commented Dec 16, 2016 at 16:44

3 Answers 3

3
$\begingroup$

It seems like you have done enough to answer the question without very much more work.

You have effectively determined that $20^{19} \equiv 2 \bmod 6$, so $18^{\large{20^{19}}} \equiv 18^{2} \bmod 7$ and the rest is simple.


Added a note on the cycles:

If you have $n>m$ and $a^n \equiv a^m \bmod b$, then clearly $a^{n+1} \equiv a^{m+1} \bmod b$ etc. and the sequence of equivalent values for $a^k \bmod b$ seen between $n$ and $m$ will repeat again (and again) above $n$.

$\endgroup$
6
  • $\begingroup$ I think that the repeating $2, 4, 2$ cycles is more of a "guess" from my side, so I didn't use it as an end result to compute $20^{19} \equiv 2 \text{ mod } 6$....is there an intuitive/easy proof that says if a cycle repeats, then it is closed? $\endgroup$
    – q.Then
    Commented Dec 15, 2016 at 10:10
  • 1
    $\begingroup$ @Ephemeral $20\equiv 2\;\;\text{and}\;\; 20^2\equiv 4 \implies 20^3=20\cdot 20^2 \equiv 20\cdot 4\equiv 2$ and so on (essentially an inductoin argument) $\endgroup$
    – user160738
    Commented Dec 15, 2016 at 10:12
  • 1
    $\begingroup$ @Ephemeral What does a cycle repeating mean? Ignore the left hand side of your calculations, what you showed is that $2\times 20\equiv 4\mod 6$, and $4\times 20\equiv 2\mod 6$. So, if we have to compute $2\times 20\mod 6$ again, what else could it be but $4$? $\endgroup$ Commented Dec 15, 2016 at 10:12
  • $\begingroup$ Wow...both of you just made that proof so much more obvious than I expected... $\endgroup$
    – q.Then
    Commented Dec 15, 2016 at 10:15
  • $\begingroup$ @Ephemeral you have determined the cycle perfectly adequately (as the other commenters have mentioned). Once this kind of cycle starts, it must inevitably continue, because there are no new inputs to change it. $\endgroup$
    – Joffan
    Commented Dec 15, 2016 at 10:16
3
$\begingroup$

Since $\gcd(18,7)=1$, by Euler's theorem, $18^{\phi(7)}\bmod{7}=1$.

Since $7$ is prime, $\phi(7)=7-1=6$.

Therefore $18^{6}\bmod{7}=1$.


There exists a positive integer $n$ such that:

$20^{19}=$

$6n+(20^{19}\bmod{6})=$

$6n+((20\bmod{6})^{19}\bmod{6})=$

$6n+(2^{19}\bmod{6})$


Therefore:

$18^{20^{19}}\bmod{7}=$

$18^{6n+(2^{19}\bmod{6})}\bmod{7}=$

$18^{6n}\cdot18^{(2^{19}\bmod{6})}\bmod{7}=$

$(18^{6})^{n}\cdot18^{(2^{19}\bmod{6})}\bmod{7}=$

$(\color\red{18^{6}\bmod{7}})^{n}\cdot18^{(2^{19}\bmod{6})}\bmod{7}=$

$\color\red{1}^{n}\cdot18^{(2^{19}\bmod{6})}\bmod{7}=$

$18^{(2^{19}\bmod{6})}\bmod{7}$


Let's prove by induction that if $n$ is odd then $2^{n}\bmod{6}=2$:

First, show that this is true for $n=1$:

$2^{1}\bmod{6}=2$

Second, assume that this is true for $n=2k+1$:

$2^{2k+1}\bmod{6}=2$

Third, prove that this is true for $n=2k+3$:

$2^{2k+3}\bmod{6}=$

$2^{2k+2+1}\bmod{6}=$

$2^{2+2k+1}\bmod{6}=$

$2^2(2^{2k+1})\bmod{22}=$

$2^2(\color\red{2^{2k+1}\bmod{6}})\bmod{6}=$

$2^2(\color\red{2})\bmod{6}=$

$8\bmod{6}=$

$2$

Therefore, since $19$ is odd, $2^{19}\bmod{6}=2$.


From all of the above, we can conclude:

$\begin{align} 18^{20^{19}}\bmod{7} &= 18^{(20^{19}\bmod{6})}\bmod{7} \\ &= 18^{(2^{19}\bmod{6})}\bmod{7} \\ &= 18^{2}\bmod{7} \\ &= 324\bmod{7} \\ &= 2 \end{align} $

$\endgroup$
1
  • $\begingroup$ @Joffan: No, I like it just fine (and it's good to learn a new LaTex feature). Thanks :) $\endgroup$ Commented Dec 15, 2016 at 10:49
1
$\begingroup$

${\rm Recall\ that\ \ } ca\bmod cn\,=\, c\,(a\bmod n)\, =\, $ mod Distributive Law

$\!{\begin{align}{\rm Therefore}\ \ \color{#c00}{20^{\large 19}}\!\bmod\color{#0a0}{\bf 6}&=\, 2\,(10\,\cdot\, 20^{\large 18}\bmod 3)\\ &=\, 2\,(1\cdot (-1)^{\large 18}\!\bmod 3)\\ &=\, \color{#c00}2\end{align}} $

So $\smash[t]{\, {\rm mod}\ 7\!:\ 18^{\Large\color{#c00}{20^{\LARGE 19}}}\! \equiv\, 18^{\Large\color{#c00}{\Large 2}}\equiv 4^{\large 2}\equiv 2},\ $ by $\,18^{\Large\color{#0a0}{\bf 6}}\!\equiv 1\,$ by Fermat.

$\endgroup$

You must log in to answer this question.

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