Solve for b when $44 \equiv 7 ^ b \pmod{71}$

Question

How do I solve for $b$?

$$44 \equiv 7 ^ b \pmod{71}$$

I can only get as far as: $$44 \cdot7^{-1} \equiv b\pmod{71}$$

Although I'm not even sure that that's right.

Answer 1

You have $7^{43} \equiv 44 \pmod{71}$, and it's the only solution for powers less than $70$.

Since $71$ is prime, $7^{70} \equiv 1 \pmod{71}$ (see Fermat's little theorem), and here it's also the only $k<71$ such that $7^k \equiv 1 \pmod{71}$ (see below), so the general solution is $7^{43+70k} \equiv 44 \pmod{71}$.

Here $43$ is found by computing all powers up to $70$, as this is the simplest way for small modulii. For more serious algorithms, see discrete logarithm.

---

Even with Fermat's little theorem, you may have smaller solutions to $7^k \equiv 1 \pmod{71}$, so you still need to check. For example, with another prime number, $73$, the equation $7^k \equiv 1 \pmod{73}$ has solutions $k \in \{ 24,48,72\}$.