Congruence mod k

Question

I'm trying to evaluate the following scenario:

$$7^b \equiv 9\pmod {17}$$

Find the smallest value for b in which the equivalence holds true.

I know that we can rewrite this as :

$$17 \mid (7^b - 9)$$

But I'm not sure how to continue, could anyone help me out?

Thanks in advance.

Yes, but you use the reduced (mod 17) value to compute the next power at each step. — paw88789, Sep 11 '14 at 02:36

score 2 · Answer 1 · answered Sep 11 '14 at 02:35

Calculate, reducing modulo $17$ each time. And I like to use negative numbers when they make the arithmetic simpler.

We have $7^2\equiv -2$, and therefore $7^3\equiv -14\equiv 3$. Now do you see it's almost over?

Remark: There is general theory. If you are interested, please look at Wikipedia, Discrete Logarithm. But the general theory in this case would involve much more work than the modified brute force approach that we took.

Congruence mod k

1 Answers1