1
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ The numbers are so small that trial and error is quite easy. $\endgroup$
    – lulu
    Sep 30, 2019 at 23:39
  • $\begingroup$ @lulu you could just say $k = 7$. $\endgroup$
    – WhatsUp
    Sep 30, 2019 at 23:41
  • $\begingroup$ @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. $\endgroup$
    – lulu
    Sep 30, 2019 at 23:43

2 Answers 2

2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Oct 1, 2019 at 0:14
  • $\begingroup$ You are welcome! $\endgroup$
    – WhatsUp
    Oct 1, 2019 at 0:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .