1

Suppose we have a clock with $24$ hours and it's $12$ o'clock. I need to calculate what time it will be after $100^{100}$ hours.

Obviously I just have to calculate $100^{100}=4 \pmod {24}$

So I started by $100=4 \pmod {24}$ but I cannot go anywhere from here.

I also tried typing it as $100=-20 \pmod {24}$ which didn't prove to be helpful either. Could someone help me with this one?

xxxxxxxxx
  • 13,138
  • 3
  • 24
  • 59
nick hanzo
  • 35
  • 3
  • 2
    $a=b\mod n\Rightarrow a^m=b^m\mod n$. – Vercassivelaunos Jul 18 '21 at 10:07
  • @Vercassivelaunos i know that im gonna be using that but i obviously cant calculate such big numbers mod 24 – nick hanzo Jul 18 '21 at 10:10
  • 1
    You can! Try to do the first few powers of $4$ and see if you can spot a pattern. – Vercassivelaunos Jul 18 '21 at 10:14
  • @Vercassivelaunos it makes sense in my mind but how do i actually prove that every power of 4mod24 is 16? – nick hanzo Jul 18 '21 at 10:26
  • I'd do it inductively using $4\cdot16=16\mod24$, but I guess that you could also try something with the prime factorization of $4^n$. – Vercassivelaunos Jul 18 '21 at 10:30
  • After $100^{100}$ years, there will be no one here to say what time it is. The question is moot. – Gerry Myerson Jul 18 '21 at 13:03
  • See the dupe and its many links for most all such methods. Perhaps easiest is that below: $j\ge 2\Rightarrow 8\mid 100^j\Rightarrow 100^j\bmod 24 = 8\left[\dfrac{100^j}8\bmod 3\right] = 8\left[\dfrac{1^j}{-1}\bmod 3\right] = 8[2]\ $ by the [mod Distributive Law](https://math.stackexchange.com/a/2059937/242) – Bill Dubuque Jul 19 '21 at 01:08

1 Answers1

1

Many ways to approach this sort of problem. Mine may be a bit long, but it works.

You want $4^{100} = 2^{200} \pmod{24}$.

First note that $2^7 = 128 \equiv 8 = 2^3 \pmod{24}$

This allows you to write $2^{7k} \equiv 2^{3k} \pmod{24}$.

Now $200 = 7(28)+4$ so you can write $2^{200} \equiv 2^{3(28) + 4} \\= 2^{7(12)+4} \equiv 2^{3(12)+4} \\= 2^{40} \\= 2^{7(5)+5} \equiv 2^{3(5)+5} \\= 2^{20} \\= 2^{7(2)+ 6}\equiv 2^{12} \\= 2^{7+5} \equiv 2^{3+5} \\= 2^8 \\= 2^{7+1} \equiv 2^{3+1} \\= 16 \pmod{24}$

So the answer is $16$ hours after your start point.

Deepak
  • 26,390
  • 1
  • 25
  • 52
  • Similarly $4^{100} = 16^{50}$ and $16^2=256\equiv 16\pmod{24}$... – Daniel Mathias Jul 18 '21 at 12:35
  • @DanielMathias Thanks, I acknowledged mine was probably longer than it needed to be. But it's the first way that came to mind. – Deepak Jul 18 '21 at 12:37
  • Please strive not to add more dupe answers to dupes of FAQs, cf. recent site policy announcement [here](https://math.meta.stackexchange.com/q/33508/242). – Bill Dubuque Jul 19 '21 at 01:09