What is the value of $\left\{\frac{3^{1001}}{82}\right\}$

Question

Let $$x=\left\{\frac{3^{1001}}{82}\right\}$$ where $\{\}$ denotes fractional part. What is the value of $x$?

First I noticed that $x=\frac y{82}$ for some $y\in\mathbb{Z}$ and $0\le y\le81$. But what next? Problem is how to solve $3^{1001}\mod82$. Then I noticed that $82=2\cdot41$, so does it mean that $y$ must be odd because $3^{1001}$ and $82$ doesn't have same parity? Also, is there any conguence pattern for $41$ which can be applied here?

Answer 1

We have: $$ 3^{1001}\equiv 3^1 \equiv 3\pmod{41} $$ by Fermat's little theorem, while obviously $3^{1001}\equiv 1\pmod{2}$.

The Chinese theorem hence gives $3^{1001}\equiv 3\pmod{82}$, so your fractional part is just $\color{red}{\frac{3}{82}}$.

Answer 2

Observe that $3^4 \equiv -1 (\mod 82)$ so that $3^{1001} \equiv 3 (\mod 82)$. That is, $\dfrac{3^{1001}}{82} = k + \dfrac{3}{82}$ for some positive integer $k$.

Answer 3

Hint: $3^4\equiv-1\mod82$ and $1001=250\times4+1$