Show that $76^{2019} \equiv 45 \pmod{101}$

Question

Using Euler's theorem I see that $76^{2019} = 76^{19} \pmod{101}$, how do I proceed?

Answer 1

$101$ is prime, so $76^{100}\equiv1\pmod{101}$ by Fermat's little theorem, so $76^{2019}\equiv76^{19}\pmod{101}$.

$76^2\equiv19\pmod{101}$. $76^4\equiv58\pmod{101}$. $76^8\equiv 31\pmod{101}$. $76^{16}\equiv 52\pmod{101}$.

Therefore $76^{19}\equiv76^{16}76^2 76^1\equiv52\times19\times76\equiv45\pmod{101}$.

Answer 2

Here is an approach that requires minimum computation. We have: $$76^{19} \equiv (-25)^{19} \equiv -5^{38} \pmod{101}$$ How we have that by quadratic reciprocity: $$\left( \frac{5}{101} \right)=\left( \frac{5}{101} \right) \cdot \left( \frac{1}{5} \right) = \left( \frac{5}{101} \right) \cdot \left( \frac{101}{5} \right)=(-1)^{\frac{101-1}{2} \cdot \frac{5-1}{2}}=1$$ So $5$ is the quadratic residue modulo $101$ and therefore $5^{50} \equiv 1 \pmod{101}$. So we can write: $$-5^{38} \equiv -5^{-12} \equiv -25^{-6}\pmod{101}$$ And since $25 \cdot (-4) \equiv -100 \equiv 1 \pmod{101}$ we have $25^{-1} \equiv -4 \pmod{101}$ and therefore: $$-25^{-6} \equiv -(-4)^6 \equiv -4^6 \equiv -4096 \equiv 45\pmod{101}$$

Answer 3

$101$ is prime so $\mathbb Z_{101}$ is a field.

$76\equiv -25 \equiv -100\cdot\frac 14\equiv \frac 14$

So $76^{19} \equiv (\frac 14)^{19}\equiv (\frac 14)^{20}*4$

$4^5 \equiv 1024 \equiv 14$

$4^{10} \equiv 14^2 \equiv (10 + 4)^2 \equiv 100 +80 + 16 \equiv -1-21+16 \equiv 6$.

$4^{20} \equiv 6^2 \equiv 36$.

So $76^{19} \equiv \frac 1{36}*4 = \frac 19$.

$9*11 \equiv 99 \equiv -2$

$9*11*50 \equiv -100 \equiv 1$.

So $76^{19} \equiv \frac 19 \equiv 550\equiv 45 \pmod {101}$.

=======

Old method:

So we know $76^{100}\equiv 1 \pmod {101}$

And we know that the order of $76$ will divide $100$.

$19$ is one less than $20$ and $20|100$ and that gives me a really strong hunch that $76^{20}$ may be congruent to $1$ or a "fifth root" of $1$. In any event my gut says it's worth calculating $76^{20}$.

$76^2\equiv (-25)^2 \equiv 625 \equiv 606 + 19\equiv 19 \pmod{101}$

$19^5 = (20-1)^5 = 20^5 - 5*20^4 + 10*20^3 - 10*20^2 + 5*20 - 1$.

Now note $100 \equiv -1$ so

$10^3 \equiv -10$, $10^4 \equiv 1$ and $10^5\equiv 10$.

So

$76^{10}\equiv 19^5 \equiv 20^5 - 5*20^4 + 10*20^3 - 10*20^2 + 5*20 - 1\equiv$

$32*10 -5*16 +10*8*(-10) - 10*(-4) + 100 - 1\equiv$

$320 - 80 +8 +40 -1 -1 \equiv$

$17 + 21 + 8 + 38 \equiv 84\pmod {101}$

So $76^{20} \equiv 84^2 \equiv (-17)^2 \equiv (20-3)^2 \equiv 400 - 120 +9\equiv 289 = 303 - 14\equiv -14\equiv 87\pmod {101}$

So we need to find the inverse of $76$.

$76 = 50 + 25 + 1$.

$2*76 = 100 + 50 + 2\equiv -1 + 50 + 2 \equiv 51$.

$4*76 \equiv 2(50 + 1) \equiv 100 + 2 \equiv 102 \equiv 1\pmod {101}$ so

$76^{-1}\equiv 4 \pmod {101}$.

So $76^{19} \equiv 76^{20}*76^{-1} \equiv 87*4 \equiv 348 \equiv 45 \pmod{101}$