Csdrhrt

As title, how do you find the reminder of $2^{62}$ with 85?

Since (85,2) = 1, from FLT I know that $2^{84} equiv 1 mod(85)$, but after this I don't know how to proceed because 62 < 85 and I don't know how to use this theorem.

$2^{84}$ is actually equal to $16$ mod $85$.

$85$ is not prime, so you need Euler's Theorem, not Fermat's. This says that if $n$ and $a$ are co-prime, then $a^{varphi(n)}equiv 1$ mod $n$, where $varphi(n)$ is the number of integers between $1$ and $n-1$ that are relatively prime to $n$. Note that if $n$ is prime, then $varphi(n)=n-1$, which gives us Fermat's Little Theorem.

If $n=pq$ is a product of two primes, then $varphi(n)=(p-1)(q-1)$ (this is the basis of RSA cryptography). So we have $varphi(85)=4cdot 16=64$, which means that $2^{64}equiv 1$ mod $85$.

So $2^{62}equiv 1/4$ mod $85$. And $4cdot 64equiv 1$ mod $85$, so $1/4equiv 64$ mod $85$.

$85$ is not prime, FLT is not applicable directly

Use http://mathworld.wolfram.com/CarmichaelFunction.html

$lambda(85)=16$

$implies2^{64}equiv1^4pmod{85}$

$implies2^{62}equiv2^{-2}equiv-21equiv-21+85$

as $-21cdot4equiv1pmod{85}$

As noticed we can't apply FLT, to solve by elementary methods note that

$$2^{8}=256 equiv 1 pmod{85}$$

then

$$2^{62} equiv 2^{7cdot 8}cdot 2^{6}equiv 2^{6}equiv 64 equiv -21 pmod{85}$$

$begin{align}{rm Note}qquad
85 &= 4^{large 3}!+4^{large 2}!+4+1\
Rightarrow (4!-!1)85 &= 4^{large 4}-1 Rightarrow color{#c00}{4^{large 4}equiv 1}!!!pmod{!85}end{align}$

So $bmod 85!:, 2^{large 62}equiv 4^{large 31}equiv 4^{large 3}(color{#c00}{4^{large 4}})^{large 7}equiv 4^{large 3} color{#c00}1^{large 7}equiv 64$

$begin{align}{bf Or}qquadqquad
85&= (16!+!1)cdot 5\
Rightarrow 85cdot 3 &= (16!+!1)(16!-!1) = 16^{large 2}-1,Rightarrow,color{#c00}{16^2equiv 1}pmod{!85}
end{align}$