I've been tasked with finding what indication a clock has $7^{19}$ hours after 1:00AM.
I've found $\phi (24) =8$. How do I use this to find the answer to my question?
Asked
Active
Viewed 32 times
0
-
1Maybe this will help: https://en.m.wikipedia.org/wiki/Euler%27s_theorem – user722227 Feb 24 '20 at 14:58
1 Answers
0
Hint: Euler's Theorem states that if $a$ and $n$ are coprime, then $a^{\varphi(n)} \equiv 1 \mod n$. Since $7$ and $24$ are coprime, we have $7^8 \equiv 1 \mod 24$. Hence, $7^{16} \equiv 1 \mod 24$, so $7^{19} \equiv 7^3 \mod 24$.
Edit: We also have $7^2 \equiv 49 \equiv 1 \mod 24$ just by simple computation.
DWe1
- 669
-
In fact, $a^2\equiv1\bmod24$ for all $a$ relatively prime to $24$ – J. W. Tanner Feb 24 '20 at 15:09