If 3^1993 =100k + n, where n < 100 is a nonnegative integer, what is n?

Question

If 3^1993 =100k + n, where n < 100 is a non-negative integer, what is n?

Is there a simple solution for this?

Note that $3^m\pmod {100}$ is periodic as a function of $m$. — lulu, Oct 14 '21 at 22:52
$1993 \equiv -7 \pmod{40}$ so $3^{1993} \equiv \frac{1}{3^7} \equiv \frac{1}{2187} \equiv -\frac{1}{13} \equiv -\frac{1001}{13}\equiv-77\equiv23 \pmod{100}$ — Evariste, Oct 14 '21 at 22:57
Worth remarking: it may be easier to solve the problem $\pmod {4}$ and $\pmod {25}$ and then use the Chinese Remainder Theorem. — lulu, Oct 14 '21 at 23:02
@VSPuzzler $3$ and $100$ are coprime so $3^{\varphi(100)} = 3^{40} \equiv 1 \pmod{100}$, so this allows reducing the exponent. To get $-7$, notice that e.g. $25 \times 40 = 1000$ — Evariste, Oct 14 '21 at 23:02
@Evariste Is there a theorem that says that if two numbers are coprime that gives you that? — VS Puzzler, Oct 14 '21 at 23:05
Solve the problem for remainders $\pmod 4$ and $\pmod {25}$, then use the CRT to find the unique remainder $\pmod {100}$ that matches those solutions. $4$ is effortless. $25$ takes a minute. — lulu, Oct 14 '21 at 23:06
Of course not. You should read about the Chinese Remainder Theorem. It's one of the most important tools in arithmetic. — lulu, Oct 14 '21 at 23:13
$3^{20}\equiv1\bmod1000$ by Carmichael, so $3^{1993}\equiv3^{13}\equiv3\cdot9^6$ $\equiv3\cdot(10-1)^6$ $\equiv3\cdot(1-6\cdot10)=3-180=-177\equiv23\bmod100$ — J. W. Tanner, Oct 14 '21 at 23:29
@VSPuzzler: $40$ is the Euler totient function $\varphi(100)$ — J. W. Tanner, Oct 14 '21 at 23:39

Aaa Lol_dude · Answer 1 · 2021-10-14T22:59:28.983

1

Note that a cycle appears, $03,09,27,81,43,29,87,61,83,49,47,41,23,69,07,21,63,89,67,01,03...$ Cycle length of 20.

Another thing to notice is that $3^{100}$ mod 100 = 1.

edited Oct 14 '21 at 22:59

answered Oct 14 '21 at 22:51

Aaa Lol_dude

Would there be an easier way to go about this without going through each value? Thanks – VS Puzzler Oct 14 '21 at 22:57
@VSPuzzler Use $\varphi(100)=40$ so you know it's at least periodic a divisor of $40$. The exponent reduces to $-7$ either way, then check my comment. – Evariste Oct 14 '21 at 23:00

1 Answers1