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.
Asked
Active
Viewed 108 times
2
-
2It isn't. But you can calculate $1,7,7^2,7^3,\dots$, reducing modulo 71 at each step, until you hit 44. – Gerry Myerson May 06 '14 at 07:49
-
Just to be sure, as you are trying to simply divide by $7$, is your equation $$44 \equiv 7b \pmod{71}$$ instead of $$44 \equiv 7 ^ b \pmod{71}$$? – Jean-Claude Arbaut May 06 '14 at 08:02
1 Answers
2
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\}$.
Jean-Claude Arbaut
- 23,277
-
"Here 43 is found by computing all powers up to 70, as this is the simplest way for small modulii." So if I wanted to show how I got to the answer, would I literally have to show 42 failed attempts before the 43rd, 44 = 7^43 (mod 71), actually worked? – Jimbo May 06 '14 at 08:01
-