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

Question

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!

Answer 1

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$.

Answer 2

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$.