# Find a $k$ such that $3^k \equiv -6 \pmod{43}$

I have been trying to find this $$k$$, but I am stuck.

The only information I could extract was from the Fermat's Little Theorem:

Since $$43$$ doesn't divide 3 and it is a prime, it follows $$3^{42} \equiv 1 \pmod{43}$$

However, I have no idea how to proceed from now.

All help is appreciated!

• The numbers are so small that trial and error is quite easy.
– lulu
Sep 30, 2019 at 23:39
• @lulu you could just say $k = 7$. Sep 30, 2019 at 23:41
• @WhatsUp Well...my point was that trial and error is the best means of solution. In general, if you replace $43$ by a very large prime, problems like this can be computationally awful. Here, it just takes a few trials.
– lulu
Sep 30, 2019 at 23:43

Notice $$3$$ and $$43$$ are relatively prime. Thos if we hae $$3m \equiv 3n \pmod{43}$$ we can safely conclude that $$m \equiv n\pmod{43}$$

So if $$3^k \equiv -6 \pmod {43}$$ then

$$3^{k-1} \equiv -2\equiv -45\pmod {43}$$

$$3^{k-2} \equiv -15$$

$$3^{k-3}\equiv -5\equiv -48$$

$$3^{k-4} \equiv -16\equiv 27$$

$$3^{k-7} \equiv 1\pmod {43}$$.

So we can let $$k = 7$$.

Another way of looking add it is that as $$43 \equiv 1 \pmod 3$$ we can find a multiple of $$3$$ by adding or subtraction $$43$$.

$$-6 \equiv 3(-2)\equiv$$

$$3(-45)\equiv 3^3(-5)\equiv 3^3(-48)$$

$$3^4(-16)\equiv 3^4(27)\equiv 3^7$$.

I don't think Little Fermat's Theorem is directly relevant here.

What you are asking for is a discrete logarithm.

To quote that wiki page:

The discrete logarithm problem is considered to be computationally intractable. That is, no efficient classical algorithm is known for computing discrete logarithms in general.

A general algorithm for computing $$\log_b a$$ in finite groups $$G$$ is to raise $$b$$ to larger and larger powers $$k$$ until the desired $$a$$ is found. This algorithm is sometimes called trial multiplication.

So for such a small number, you'd better just do what @lulu suggested: trial multiplication.

It turns out that $$3$$ is a primitive root mod $$43$$. Given that $$3^7 \equiv -6 \mod 43$$ (found by trial multiplication), one concludes that all $$k$$ satisfying that identity are given by $$k = 7 + 42 t$$ for $$t\in\mathbb{Z}$$.

Note on the fact that $$3$$ is a primitive root mod $$43$$:

A standard verification is to factorise $$42 = 2 \times 3 \times 7$$, then test whether any of $$3^{42/2}, 3^{42/3}, 3^{42/7}$$ is congruent to $$1$$ mod $$43$$.

• I see your point. Now I think the question that was given to me is just about using trial multiplication in order to find $k$. I appreciate your answer, thanks. Oct 1, 2019 at 0:14
• You are welcome! Oct 1, 2019 at 0:17